5

ダイクストラのアゴリズム、フロイド-ワーシャル アルゴリズム、およびグラフの 2 つの頂点間の最も安いパスを見つけるためのベルマン-フォード アルゴリズムについて知っています。

しかし、すべてのエッジのコストが同じ場合、最も安価なパスはエッジの数が最小のパスでしょうか? 私は正しいですか？Dijkstra または Floyd-Warshall を実装する理由はありません。最適なアルゴリズムは、ターゲットに到達するまで、ソースからの幅優先検索ですか? 最悪の場合、すべての頂点をトラバースする必要があるため、複雑さは O(V)? より良い解決策はありませんか？私は正しいですか？

しかし、インターネット上には、障害のあるグリッド内の最短経路について話し、Dijkstra または A* に言及している記事がたくさんあります。StackOverfow でも -最短経路を見つけるためのアルゴリズム、障害物 またはここhttp://qiao.github.io/PathFinding.js/visual/

それで、それらの人々はすべて愚かですか？それとも私は愚かですか？ダイクストラのような複雑なものを、敵を通常のグリッドで主人公に移動させたいだけの初心者に勧めるのはなぜですか? これは、誰かがリスト内の最小数を見つける方法を尋ねたときに、ヒープ ソートを実装し、ソートされた配列から最初の要素を取得するように勧めた場合のようなものです。

4

3 に答える 3

5

BFS (幅優先探索) は、グラフを移動する方法にすぎません。目標は、すべての頂点を訪問することです。それで全部です。グラフを移動する別の方法は、たとえば DFS です。

ダイクストラは、特定の頂点 v から他のすべての頂点への最短経路を見つけることを目標とするアルゴリズムです。

Dijkstra は、初心者でもそれほど複雑ではありません。BFS を使用してグラフを移動し、さらに何かを実行します。これはさらに、現在訪れている頂点への最短経路に関する情報を保存および更新することです。

2 つの頂点 v と q の間の最短経路を見つけたい場合は、Dijkstra を少し変更するだけで実行できます。頂点qに到達したら停止します。

最後のアルゴリズム - A* はいくぶん最も賢い (そしておそらく最も難しい) アルゴリズムです。魔法の妖精であるヒューリスティックを使用して、どこに行くべきかをアドバイスします。優れたヒューリスティック関数がある場合、このアルゴリズムは BFS やダイクストラよりも優れています。A* は Dijktra のアルゴリズムの拡張と見なすことができます (ヒューリスティック関数は拡張です)。

しかし、すべてのエッジのコストが同じ場合、最も安価なパスはエッジの数が最小のパスでしょうか? 私は正しいですか？

右。

Dijkstra または Floyd-Warshall を実装する理由はありません。最適なアルゴリズムは幅優先探索ですか? 私は正しいですか？

すべてのエッジの重みが同じであるような単純なケースになると、好きな方法を使用でき、すべてが機能します。ただし、優れたヒューリスティックを備えた A* は、BFS や Dijkstra よりも高速である必要があります。あなたが言及したシミュレーションでは、それを観察できます。

それで、それらの人々はすべて愚かですか？それとも私は愚かですか？ダイクストラのような複雑なものを、敵を通常のグリッドで主人公に移動させたいだけの初心者に勧めるのはなぜですか?

彼らは別の問題を抱えており、それによって解決策が変わります。問題の説明を注意深く読んでください。

(...) キャッチは任意のポイント (A と B を除く) であり、パスを妨げる障害物がある可能性があるため、迂回する必要があります。

敵は主人公に向かう途中に障害物を持っている可能性があります。したがって、たとえば A* はそのような場合に適しています。

于 2013-04-27T07:36:58.537 に答える
2

BFS は、重み付けされていないグラフで最短経路を見つけるための「力ずく」のようなものです。Dijkstra は、加重グラフの「力ずく」のようなものです。重み付けされていないグラフでダイクストラを使用すると、BFS とまったく同じになります。

したがって、ダイクストラは BFS の拡張と見なすことができます。これは実際には「複雑な」アルゴリズムではありません。BFS よりも少しだけ複雑です。

A* は、ヒューリスティックを使用してパスファインディングを高速化する Dijkstra の拡張機能です。

于 2013-04-29T15:43:29.067 に答える
0

しかし、すべてのエッジのコストが同じ場合、最も安価なパスはエッジの数が最小のパスでしょうか? . はい

リンクした投稿を本当に理解していれば、彼らが解決したい問題があなたのものとは異なることに気付いたでしょう。

于 2013-04-27T07:37:54.400 に答える