1

私はコーメンらの本から勉強してきましたが、彼らが提供したアルゴリズムについて少し混乱しています。Prim のアルゴリズムの概念がウィキペディアでどのように機能するかを理解しましたが、私の本で提供されているアルゴリズムを使用してその動作を模倣することはできません。

章の次のオンライン コピーを参照して ください。

アルゴは上記リンクの 13 ページに記載されており、図の例は前のページにあります。

ここで、最初のステップで、例のケースでアルゴリズムを使用します。

u <--- ExtractMin(Q) を介したノード A。次に、図のように、Adj[u] にノード b とノード h の 2 つのエントリがあります。

最初に v <---- ノード b を設定します。次に、v が Q に属しているかどうかを確認します。そうです。w(u,v) < key[v] かどうかを確認します。真実。したがって、PI[v] <--- u およびキー [v] <--- w(u, v) です。こんなに取れました。これは 12 ページの図の (b) に示されています。

しかし、アルゴリズムは「Adj[u]の各vに対して」と言います。

したがって、次のステップでは v <--- ノード h を設定する必要があります。次に、v が Q に属しているかどうかを確認します。そうです! w(u,v) < key[v] ですか? です！key[v] = 無限だから! しかし、この図では (c) の部分で別のステップが示されています。

あああああ！なんで？

4

2 に答える 2

4

MO の担当者の 1 人が親切にもメールで回答してくれました。問題は、ExtractMin(Q) 操作によってツリー ノードが一度に 1 つずつ追加されることに気付かなかったことです。

これが彼の答えです：

*あなたの分析は実際には完全に正しいですが、キー[v] と pi(v) の更新が何を意味するのかについて、あなた (および私) は混乱していました。特に、pi(v) を更新するとき、それをツリーに追加しません。ノード u は、Q から抽出された場合にのみ (親 pi(u) に接続するエッジに沿って) ツリーに追加されます。 (a)、ステップ (c) ではありません。その場合のプログラムの動作の概要は次のとおりです。

  • (行 1 ～ 3) すべてのノードは Q (ツリーにないノードのセット) に配置され、それらの親は NIL であると宣言され、それらのキー (つまり、単一のエッジに沿った既存のツリーまでの最小距離) は に設定されます。無限大
  • (4行目) ルートノード(ノードa)のキーを0に設定
  • (6 行目) 最小キー (ルート ノード a) を持つノード u が Q から削除され、ツリーに追加されます。
  • (行 8-11) ノード b と h のキーが 4 と 8 に更新され、pi(b) と pi(h) が u に設定されます (ただし、b と h はQ から抽出されません)。これでステップ (a) は完了です
  • (6 行目) 最小キー (現在はノード b、キー = 4) を持つノード u は Q から削除され、その親 (pi(b)=a) を介してツリーに追加されます。
  • (行 8-11) ノード c のキーは 8 に更新され、pi(c) は b に設定されます。key(h)=8 は 11=w(b,h) よりも小さいため、h のキーと親は更新されません。これでステップ (b) は完了です
  • (6 行目) 最小のキーを持つノード u (キー = 8 を持つノード c ですが、キー = 8 を持つノード h である可能性もあります) は Q から削除され、その親を介してツリーに追加されます (これはパイ(c)=b)
  • (行 8 ～ 11) ノード d、i、および f のキーと親を更新し、ステップ (c) を完了します。
  • 等。*
于 2009-12-20T05:09:23.870 に答える