パスファインディングでは、DFSとダイクストラの違いは何ですか？

Question

私はDFSとダイクストラについて学んでいます。 私の単純なテストケースでは、DFSがより高速であることがわかります。 テストケースでは、すべてのノードに同じコストがかかります。 しかし、ほとんどの人は、Dijkstraが非常に正確であるため、Path FindingでDjにDjkstraを好む。

DFSとダイクストラの違いは何ですか？ また、各アルゴリズムの長所と短所は何ですか？

Answer 1

パスが見つかるまで、DFSはノードにジャンプし続けますが、ダイクストラはBFSに似ていますが、ウェイトのトラッキングはすべてのパスで同じコストではありません。ターゲットに到達します。一般DFSに

は（通常は）パスを見つけるための最速の方法であると再帰で非常に簡単に実装することができますが、ダイクストラ法は 可能な最短パスを見つけるための最速 一般方法です。

あまり一般的でないケースでは、Dijkstraのアルゴリズムで、最初にチェックする方が良いパスを推測するためにいくつかの余分なヒューリスティックスがあります。これは可能な限り最短のパスも見つけますが、ヒューリスティックが良い場合は速く実行できます。

EDIT：

私はあなたのグラフがあまりにも持っていない場合、ヒューリスティックとDFSは、多くの場合、良い選択であることを、あなたは急いやヒューリスティックに「かなり良い」パスをしたい場合は利用可能であることを、追加する必要があります多くの死んだ終わり。これは、Greedy Best First Searchと呼ばれ、十分に活用されていない経路探索アルゴリズムであり、例えば、デッドエンドの少ないマップやA *が非常に高価なロードマップを設計することができます。