1

aからまでdを最短ルート（最安）で行きたい

  1    15
a--->b---->d
|        /\
|2       /
|       /1
|      /
|     /
|    /
|   /
|  /
| /
\/
c

aはb1 のコストで、またはc2 のコストで b行くことができますd。 15 のコストで c行くことができます。 1 のコストで行くことができdます。

アルゴリズムのコストは 1 であるのに対し、どちらのコストが 2 であるかa->bという理由でアルゴリズムは開始されませんか? a->cしかし、それは15のコストでしか行くことができませんb->d。これは、から行った場合よりもコストがかかりますa->c->d

私はこのアルゴリズムを一新しようとしているので、私のロジックに欠陥があるかどうか教えてください.

4

4 に答える 4

1

「最初の方法が最善の方法」と考えるのは間違いであり、そうではありません。このアルゴリズムでは、頂点に到達するコストを更新できます (より低いコストで保証される場合)。

ノードは、訪問済み、未訪問、利用可能、利用不可に分けられます。

訪問者について考えることができません。なぜなら、彼が最小値を持っていて、負の値のエッジ (アルゴリズムの仮定を参照) がない場合、より良い方法を見つけることができないからです。

訪問されていないものはすべて別のものであり、実際にそれらすべてに歩くことはできない可能性があります.

利用可能な頂点はすべて未訪問であり、今すぐ訪問できます。（利用できないことは明らかだと思います。）

開始時に使用できるのは最初の頂点のみです。簡単なパターンに従うことができます。

ステップバイステップ:

- (実際に) 利用可能なすべての頂点から最も安価な頂点を取得します。これは、プライオリティ キューで行う必要があります。最も簡単な解決策はバイナリ ヒープ ( O(|E| log |V|) ) ですが、パフォーマンスを考える場合は、フィボナッチ ヒープ ( O(|E|+|V|log|V|) )を使用できます。配列 ( O(|V|^2+E) )を使用することは可能ですが、推奨されません。これがルートになるはずです。

-現在のノードの場合、すべての未訪問の近隣ノード (未訪問、利用不可 (理由は上記を参照)) のトリップ コスト if( (現在のノードのコスト + それらを隣接ノードで接続するエッジの重み) < (の実際のコスト開始ノードから隣接ノードに到達) )。使用不可から使用可能に変更する場合、変更された要素を優先キューに追加する必要があります。ノードのコストを更新するときは、ヒープをアップグレードする必要があります。忘れないでください。

-実際にノードを訪問済みとしてマークします。優先キューから彼を削除します (永続的にアクセスされます)。最小ヒープでは、delete_root 操作です。

-キューが空でなくなるまで繰り返します。

あなたの例では、次のようになります。

数値 - 実際には、ノード間のパスの最小合計重み (最初と最後)。

スター - ノードが訪問され、このコストは決して変わりません。

ダッシュ - ノードは現在利用できません。

| a | b | c | d |
-----------------
| 0 | - | - | - | <-- Available is only a.
-----------------
|*0*| 1 | 2 | - | <-- You can go to b and c.
-----------------
|*0*|*1*| 2 | 16| <-- b was cheaper, you updated costs from this vertex.
-----------------
|*0*|*1*|*2*| 3 | <-- You didn't stop, and find less costly way!
-----------------
|*0*|*1*|*2*|*3*| <-- Work done, the last vertex visited.
-----------------

より具体的には、最初に利用できるのは最初の要素のみであるため、最初に彼を訪問する必要があります。完了すると、2 つの新しいノードが利用可能になり、最も安価な場所にアクセスする必要があります (利用可能なものから、アクセスされていないものまで)。Bです。b から d への唯一の方法であるため、彼のコストのみをアップグレードします (現在は d が使用可能ですが、実際の方法 (コスト) は最適ではない可能性があります)。再度、利用可能な頂点から最も安い頂点を取得します。a と b が訪問され、2 が 16 より小さいため、これは c です。このノードをチェックすると、d へのより良い方法が見つかります。したがって、d のコストを 16 から 3 に更新する必要があります。最後に訪問したノード (d) は形式的で重要ではありません。動く。すべての頂点を訪れたので、これで作業は完了です。

于 2013-07-30T08:33:39.267 に答える