3

私はA*アルゴリズムが最短経路を見つけることができることを知っています。しかし、私の仕事の問題は、すべての最短経路を見つける必要があるということです。より正確には、いくつかの最短経路が存在する可能性がありますが、時計回りの優先順位で1つの最短経路を選択する必要があります。

最短経路をすべて取得できれば、必要な経路（時計回りの優先順位）を取得できます。

4

3 に答える 3

8

A*アルゴリズムの特徴は、完全で最適であることです。つまり、パスが存在する場合はソリューションへのパスを見つけるだけでなく、最短パスを最初に見つけることが保証されます。

これは、A* が使用するヒューリスティック関数が許容可能なヒューリスティックでなければならないためです。つまり、目標までの距離を過大評価してはなりません。

これにより、ソリューションへのパスを見つけるとすぐに、検索空間の残りの部分にそのパスよりも短いパスがないことがわかります。

最初の解までの距離がd(problem)だったとしましょう。さて、私の最後のステートメントは、実際には、最初の解d(problem)を見つけた後も続けて、別の解d2(problem)を見つけた場合、 2 つの可能性があることを意味します。

  • d2(problem) = d(problem) :すべての最適なパスが必要なため、それを保持します。また、すべての新しいパスはd2 = d以上にすることができます
  • d2(problem) > d(problem) : 今、上で書いたのと同じことが有効です: d2より短いパスはもうありません。そして、d2は、探しているソリューションよりも既に長くなっています。したがって、 d2を破棄して検索を終了できます。
  • 3 番目のオプションがないことに注意してください。d2(問題)は、アルゴリズムの基本的なプロパティの 1 つであるため、既に見つけた最適なd(問題)よりも短くなることはありません。

つまり、要約すると、最初の最適な解を見つけた後も続行し、同じ距離にあるすべての解を受け入れます。距離が悪い（長い）最初のパスは、破棄して検索を停止します。

質問の「時計回り」の部分を見ただけです。ヒューリスティック関数またはコスト関数に時計回り性を挿入することで、すべての最適解の検索を回避できる可能性があります。たとえば、私が時々使用しているトリックは次のとおりです。コストは 0 からinfまでの整数です。次に、間隔[0, 1)からの実数値を持つことができる時計回りコンポーネントを追加します。このように、以前は true であった場合はそのままになりますが、時計回りのコンポーネントが異なる場合、関係が変更される可能性があります。a > ba == b

明示的に数値を処理したくない場合、比較できる別の方法は、コストを値のペアにすることです。ペアの最初のコンポーネントが 2 つのパス コストで異なる場合は、それらを比較するだけです。最初のコンポーネントが同じ場合にのみ、ペアの 2 番目の値を比較します。

そうは言っても、私の頭の中で、コストまたはヒューリスティック関数 (またはその両方) を変更するようアドバイスするかどうかはわかりません。また、この正確なトリックがあなたの問題で機能するかどうかはわかりませんが、少しプレイするだけで、これらの関数の1つを変更するだけで、アルゴリズムを最も時計回りのソリューションに向けてかき混ぜることができるはずです.

于 2012-05-24T14:05:34.490 に答える
-6

ダイクストラのアルゴリズムは、すべての最短経路を提供します。A* は、改良された Dijkstra として作成され、制約が追加されました。改善点は、すべてのノードにアクセスする必要がなくなったことです。すべてのノードを探索したい場合 (すべての最短パスを確認するために必須です)、A* を使用する意味はありません。汎用の先祖に固執するだけです。

于 2012-05-24T13:38:54.770 に答える