アルゴリズムa*
の上
？可能性が有望であるかどうかを知る方法は？
- 関数f（x）= g（x） + h（x）
- これはヒューリスティック機能です
- g（x）は、原点からxノードに到達するコストです
- H（x）は、次のノードのコストを推定するためのヒューリスティックな機能です
- 私たちは常にツリーを拡大する可能性を見て、f（x）の値を計算します
- 見つけたものの中に最小のf（x）を持つノードを追加します
- OA*は、グラフで最小限の方法で最も効率的なアルゴリズムです
- ただし、深刻な制限です
- 許容可能なh（x）を定義する必要があります：xからyまでの実際の距離よりも大きい値を返すことはありません
- H（x）が許容されるが、実際の距離が過小評価されている場合、アルゴリズムは非常に非効率的です。 H（x）が許容できない場合、アルゴリズムは最小限の方法を見つけられない場合があります
？複雑
- 複雑さは、使用される関数H（x）に直接依存します。
- 最悪の場合、探索されるノードの量は最小のパスのサイズが指数関数的ですが、H ∗（x）-H（x）≤o（logh ∗（x））の場合、多項式の複雑さがあります。
？いつ使用するのは良いですか？
- マップのように、2つの頂点間の距離を過小評価できるグラフ
- 2つのポイント間の最短距離は線ですが、おそらく実際の距離はそれよりも大きくなります
？この場合の最小限は何ですか？
プロジェクトを実行します
結果
著者
ライセンス
このプロジェクトはMITの下にあります。詳細については、こちらをご覧ください。
