A スター アルゴリズムは完全であることが知られています。ただし、Web を検索して見つけたすべての実装は、最初の (最適な) ソリューションのみを返すようです。
たとえば、この実装: スター アルゴリズムの実装
アルゴリズムは常に最小の f 値を持つノードを拡張し、最初のノードが解になると実装が停止するように見えるため、前述のコードをどのように適応させて、重複するアクション (つまり、同じアクションを何度も含むパス) を考慮せずに、目標を設定しますか?
質問する
1795 次
2 に答える
1
すべてのパスで、幅優先探索を使用する方がはるかに理にかなっています。または、上位n個の最短経路を見つけたい場合は、ダイクストラのアルゴリズムを試すことができます。
于 2013-01-30T19:30:51.287 に答える
1
これは完全です。つまり、存在する場合は解決策を見つけますが、アルゴリズムは具体的には 1 つのパスのみを返します。ただし、幅優先検索では、2 つのノード間のすべての非循環パスが検索されます: http://en.wikipedia.org/wiki/Breadth-first_search
更新- これは、n (またはこの場合は k) の最短パスのリストを最短から最長の順に返す k-最短パス アルゴリズムです。http://code.google.com/p/k-shortest-paths/
于 2013-01-30T19:07:13.117 に答える