0

累積距離、パスごとの距離、および頂点の名前 (または位置) を追跡することは理解できますが、目的地にどれだけ効率的に到達したかを追跡したい場合を除き、歩数を追跡する必要はありません。 ?

このステップは、パスを見つけるためにまったく不要であり、とにかく恣意的なようです。たとえば、累積距離が同じで最小数の複数の頂点がある場合、どの頂点から開始するかを気にする理由はありませんが、次のステップでラベル付けされる頂点はどれでもかまいません。

私は多くのコードを目にしますが、それらは通常、ステップを追跡するというこの原則に従っています。特に、それらの多くが移動コストが 1 または無限の 2D マトリックスで経路探索を行っている場合は、非常に奇妙に思えます。その場合、頂点ごとのステップ数が不必要であるだけでなく、気にする必要がある唯一の情報は、距離と頂点のラベルであると私には思えます。距離がある場合は、頂点を訪れたことがわかります。すべての距離が同じであるため、最初に頂点に到達するときは常にその頂点の最短距離になるはずです。低いか高いかを評価する必要はなく、存在することだけが必要です。

とにかく、なぜそんなに単純なものに余分な情報が集められなければならないのか、私はただ興味があります. 私が把握していないだけの理由はありますか？

編集 -

少し明確にするために、コメントで適切にフォーマットされていなかったため、通常、ステップは人々が使用するように指示する表に示されています.

____________________
|name|step|distance|
--------------------
|temporary Labels  |
--------------------

ステップは、位置が原点から次に短いポイントである場合に追加されます。

4

1 に答える 1

2

わかりました、今そのビデオを見ましたが、実際にそのようなテーブルが使用されているのを見たのは初めてです. 私にはあまり意味がありません。「ラベル」と「距離」が完全に混ざり合っています。恒久的なラベルはノードがマークされた順序であり、一時的なラベルは現在の固定されていない距離です。これらはどちらもまったく必要ありません。

代わりに、ノードに対して通常持っているものは次のとおりです。距離（開始ノードから）、親（または前の）ノード、およびノー​​ドを完了または未完了としてマークするマーク（実装では通常、優先キューがあります）代わりに、マークされていないすべてのノードに対して)。

次に、合計距離が最小のマークされていないノードを見続け、それをマークして、マークされていないすべての隣接ノードの距離を更新します。また、距離を短くするたびに、親ノードも更新します。

ただし、ノードを完了としてマークした順序や、以前の未完了の距離をすべて保持する必要はありません。私には、そのビデオでは、生徒の作業を簡単に確認できるようにするための方法のように思えます。同じ距離がなければ、常に頂点を見る順序が 1 つになるからです。

そうは言っても、通常のダイクストラ アルゴリズムにはこのようなものは含まれておらず、必要ありません。実際に保存するものの実装の詳細については、ウィキペディアの疑似コードを参照してください (前述のように、通常、各ノードの距離と親、およびマークされていないノードの優先キューのみがあります)。

特に、それらの多くが移動コストが 1 または無限の 2D マトリックスで経路探索を行っている場合は、非常に奇妙に思えます。

ここで説明しているのは非常に特殊なケースです。ダイクストラ アルゴリズムは実際には、距離が等しくない多くのグラフの問題で使用され、すべての方向に 4 つの単純な隣接点しかないより多くの接続があります。

于 2013-05-08T11:23:03.750 に答える