1

問題を（グラフで）解決するためにベルマンフォードアルゴリズムを実装しましたが、この解決策は遅すぎたため、ベルマンフォードのキューをヒープ（std :: set）に置き換えたため、最短の解決策になりましたパスがより速く見つかります。（ダイクストラアルゴリズムはどういうわけか近い）

ここで、ノード番号をヒープに挿入します。これにより、デフォルトのstd :: setは、コストではなく番号を使用してノードを並べ替えます。すべてが順調であり、アルゴリズムは正しい答えを与えます。

std :: setのカスタム比較関数を実装すると、ノードは番号ではなく距離で並べ替えられ、アルゴリズムは残りのノードまでの最短距離を提供しなくなります。

これは私の比較関数です：

 struct cmp{

    bool operator() (const int &a,const int &b) const{
        return (d[Q][a] < d[Q][b] );
    }
  };
 set <int,cmp> q;

したがって、BFアルゴリズムであるため、アルゴリズムは改善ができなくなるまで実行されます。比較関数はどういうわけかstd::setを「混乱」させることができますか？これが、この比較関数を追加すると間違った答えが得られる理由がわかる唯一の理由です...

つまり、ノードが完全にランダムな順序である場合は機能するのに、コスト順に並べられている場合は機能しないのはなぜですか...

4

1 に答える 1

2

Bellman-Ford アルゴリズムを思い出す限り、それはノードの距離を更新します。したがって、重みを のキーとして使用するのstd::set<T>は簡単ではありませんstd::set<T>。距離を変更しただけでは、 の検索でそれぞれの値が見つかりません。この方向を追求するために必要なことは、更新するノードを削除し、ノードの距離を変更し、後で再挿入することです。また、オブジェクトには一意のキーが必要であることに注意してくださいstd::set<T>。既に存在するキーを挿入すると失敗します。

あなたはstd::set<int>ある種の優先キューとして使用していると言いました。ご覧になりましたstd::priority_queue<T>か？これはまさにこれを行っていますが、を使用するよりも効率的である傾向がありますstd::set<T>。問題std::priority_queue<T>は、オブジェクトの優先度を変更できないことです。現在のトップにしかアクセスできません。ずっと前に、オブジェクトの優先度を変更できる優先度キューのバージョンを含む優先度キュー (ヒープ) のコレクションを作成しました (これらは Boost の初期ライブラリの一部でしたが、レビュープロセスを通過することはありませんでした)。あなたがプライオリティ キューをどのように使用しているかはわかりません。したがって、これが妥当な方向性であるかどうかもわかりません。

std::set<T>とはいえ、とにかくベルマンフォードアルゴリズムを使いたい理由がわかりません。私の理解では、アルゴリズムはグラフを繰り返し通過し、新しい最短距離でノードを更新します。Boost のBellman-Ford アルゴリズムの実装をご覧になりましたか?

于 2012-02-12T19:17:07.743 に答える