問題タブ [minimum-spanning-tree]

この質問が少し広範である場合は申し訳ありませんが、最小コストのスパニング ツリーを作成する方法を理解するのに苦労しています。これは、問題がある場合は C++ にあります。

私が理解していることから、クラスカルを使用して、スパニング ツリーを構築するための最小コスト エッジを選択します。私の考えは、エッジを最小ヒープに読み込むことです。そうすれば、最小コストでエッジを取得するためにトップから削除できます。

これまでのところ、minheap と union-find のセットしか実装できませんでした。union-find の目的と、スパニング ツリーを作成するためのソート アルゴリズムについてはまだわかりません。

アドバイスをいただければ幸いです。

編集: ユニオンの検索、minheap、kruskals、および並べ替えアルゴリズムに限定されているわけではなく、何もする必要もありません。これらは講師が提案した項目にすぎません。

http://en.wikipedia.org/wiki/Minimum_spanning_tree

最小スパニング ツリー アルゴリズムを最高のものと比較してベンチマークすることを検討しています。これらのアルゴリズムの C++ 実装がどこにあるか知っている人はいますか? 私はどんちゃん騒ぎしてグーグルで検索しましたが、何も見つかりませんでした。これらのアルゴリズムが最高の場合、C++ の実装がどこかにあるに違いありません。

これまでで最速の最小スパニング ツリー アルゴリズムは、David Karger、Philip Klein、Robert Tarjan によって開発され、Borůvka のアルゴリズムと逆削除アルゴリズムの組み合わせに基づく線形時間ランダム化アルゴリズムを発見しました.[2][3] Bernard Chazelle による最速の非ランダム化アルゴリズムは、おおよその優先順位キューであるソフト ヒープに基づいています。[4][5] その実行時間は O(m α(m,n)) です。ここで、m はエッジの数、n は頂点の数、α はアッカーマン関数の古典的な逆関数です。関数 α は非常にゆっくりと成長するため、すべての実用的な目的では、4 を超えない定数と見なすことができます。したがって、チャゼルのアルゴリズムは線形時間に非常に近くなります。エッジの重みがビット長が制限された整数の場合、次に、実行時間が線形である決定論的アルゴリズムが知られています[6]。一般的な重みの実行時間が線形である決定論的アルゴリズムが存在するかどうかは、まだ未解決の問題です。しかし、Seth Petie と Vijaya Ramachandran は、証明可能な最適な決定論的最小スパニング ツリー アルゴリズムを発見しましたが、その計算の複雑さは不明です [7]。

私はすでに Boost C++ のグラフ アルゴリズムに対してテストを行っています。

Kruskal の最小スパニング ツリーのアルゴリズムの逆は機能しますか? つまり、すべてのステップで最大の重み (エッジ) を選択するということですか?

最大スパニングツリーを見つけるための他のアイデアはありますか?

A* アルゴリズムを考えてみましょう。

Google では、適切な疑似コードを見つけることができます。

よくわからないことが 1 つあります。次のような状況を考えてみてください。

A* はどのようにして a->b->c から a->d... に変更できますか? ??? つまり、A* はノードから開始し、ノード間を移動します。ある時点で、ノードには複数の隣接ノードがあり、A* は隣接ノードによって生成されたパスをたどることができますが、ある時点で切り替えることができます...そして、前のステップから始まるそのステップに戻ることができます放棄された道がその道を横切らなかったとしても...

コードでは、この環境を有効にする条件は何ですか?

こんにちは素晴らしい人！

allEdges.add(newEdge);問題があります...テストケースがconnectNodesメソッドに到達すると、NullPointerExceptionが発生します。

Edge newEdge = new Edge( n1, n2, weight );同じ方法で以前と関係があると思います。

私がEdgeクラスでジェネリックを使用しているのは問題ですか？Edge newEdge = new Edge( n1, n2, weight );以前、「クラスが見つかりません」などのエラーが発生しました。allEdges.add(newEdge);しかし今、私は何も変更せずに代わりにNullPointerExceptionを取得しているようです。

あらゆる助けにとても感謝しています！

}

私はこれをじっと見つめていましたが、それは私を怒らせています。

e = pq.poll( );大きな最小スパニング ツリーのテスト ケース中に、どうにかして e の値を null にします。小さな最小スパニング ツリーが機能します。

この問題に関するすべてのヒントと、そのような問題を解決する方法に非常に感謝しています.

ご協力ありがとうございました！

編集:優先キューが空のようです。それがなぜなのか理解できません:/

edit2:さらなる洞察のためにここに DisjSet クラスを追加しました

クラス宣言といくつかのメンバー:

DisjSet クラス:

失敗のトレースが役立つ場合:

Gを、明確なエッジの重みを持つ無向グラフとします。TをGのMSTとします。（u、v）をTの任意のエッジとします。（u; v）がこのカットの最小重みエッジであるようなカット（S; VS）があることを示します。

最小全域木の一部ではないエッジeを含む最小全域木の一般的な形式について混乱しています。私の質問は：

Gを、すべてのエッジの重みが1に等しい重み付きグラフとします。GのMSTには、エッジeは含まれません。エッジeを含むという制約でMSTをいくつ作成できますか？

私はダイクストラのアルゴリズムを理解し、実装するために一日中戦ってきましたが、重要な結果はありませんでした。私は都市とその距離のマトリックスを持っています。私がやりたいのは、出発地と目的地を指定して、都市間の最短経路を見つけることです。

例：

これを解決する他の方法があるかどうか疑問に思い始めました。プリムのアルゴリズムを起点から適用し、作成されたツリー全体をループして、終点が見つかるとどうなりますか？

ユークリッド重みの隣接行列として表される無向グラフがあります。これを使用して、より大きな完全なグラフの最小スパニング ツリーを表します。

私が見つけたいのは、グラフ内の単一のノードであり、ルート ノードとして使用すると、可能な限り短いツリーの高さを作成します。私が思いついたのは、すべてのノードをルートとして使用して深さ優先のトラバーサルを実行し、見られる最短の高さを追跡することです。これを達成するためのより速い方法はありますか？