ダイクストラ アルゴリズムと A* スター アルゴリズムについて読んでいました。違いは使用されるヒューリスティックであることを私は知っています。しかし、ヒューリスティックとは何で、これがアルゴリズムにどのように影響するのでしょうか? ヒューリスティックは距離を測定するための単なる方法ですか？しかし、ダイクストラは距離も考慮しますか? 申し訳ありませんが、私の質問はヒューリスティックとそれが何を意味し、なぜそれらを使用するかについてです... (私はそれについて読んでいましたが、理解していません) 他の質問: それぞれいつ使用する必要がありますか?
ありがとうございました
このコンテキストでは、ヒューリスティックとは、アルゴリズムに何らかの形式の特別な評価情報を提供する方法です。これにより、アルゴリズムは、すべての可能なソリューションを徹底的に検索することなく、「十分に良い」ソリューションを見つけることができます。
ダイクストラのアルゴリズムはヒューリスティックを使用しません。開始ノードから外側に展開し、最短パスを見つけるためにグラフ内のすべてのノードを調べます。これは正確ですが、計算コストが高くなる可能性があります。
比較すると、A* アルゴリズムは距離 + コスト ヒューリスティックを使用して、探索する次のノードの選択においてアルゴリズムを導きます。これは、アルゴリズムがグラフ上のすべてのノードを調べることなく、可能な検索ソリューションを見つけることを意味します。したがって、実行するのははるかに安価ですが、完全な精度が失われます。通常、結果は最適解に十分近く、グラフ全体を徹底的に検索するよりも安く済むため、これが機能します。
それぞれをいつ使用する必要があるかについては、実際にはアプリケーションによって異なります。ただし、A* アルゴリズムを使用するには許容可能なヒューリスティックが必要であるため、このような情報がアルゴリズムで利用できない状況では適用できない場合があります。
ヒューリスティックとは、基本的にアイデアや直感を意味します。難しい問題を解決するために使用する戦略はすべてヒューリスティックです! 一部の分野 (組み合わせ問題など) では、 NP 困難問題を多項式時間内で準最適に解くのに役立つ戦略を指します。
Dijkstra は、単一ソース ルーティングの問題を解決します。つまり、空間内の 1 点から他の任意の点に移動するコストを示します。
A* は、単一ソース、単一ターゲットの問題を解決します。特定のポイントから別の特定のポイントまでの最小距離パスを提供します。
A* は通常、許容できるヒューリスティックを与える場合、ダイクストラよりも高速です。ここで与えられた以前の回答とは対照的に、使用されたヒューリスティックが許容できる場合、A* は完全であり、最適な回答が得られます。