道を探すアルゴリズムについてのいくつかの思考(4):Aアルゴリズムの変体
4557 ワード
本文は伯楽オンライン-楽徒翻訳、黄利民学の原稿です.許可なしに転載禁止!英語の出所:theory.stanford.edu.翻訳グループにようこそ.
本シリーズ:道を探すアルゴリズムについてのいくつかの思考(1):Aアルゴリズム紹介 道を探すアルゴリズムについてのいくつかの考え(2):Heuristics関数 道を探すアルゴリズムについてのいくつかの思考(3):Aアルゴリズムの実現 道を探すアルゴリズムについてのいくつかの思考(4):Aアルゴリズムの変形 道路探索アルゴリズムに関するいくつかの思考(5):移動中の障害物を処理する 道探しアルゴリズムに関するいくつかの思考(6):あらかじめ計算された経路のための空間 道を探すアルゴリズムについてのいくつかの思考(7):地図表示 道を探すアルゴリズムについてのいくつかの思考(8):長期と短期目標 道を探すアルゴリズムについてのいくつかの思考(9):道を探す人の移動コスト 道探しアルゴリズムに関するいくつかの思考(10):最短パスのユーザ体験 道を探すアルゴリズムについてのいくつかの思考(11):道を探すアルゴリズムの他のアプリケーション 道を探すアルゴリズムについてのいくつかの思考(12):AI技術 指向検索
Aアルゴリズムのサイクルでは、OPENのセットは、経路を探すために使用されるすべての被検索ノードを保存するために使用される.指向性探索はAアルゴリズムに基づいてOPENのセットサイズに制約条件を設定することによって得られた変形アルゴリズムである.セットが大きすぎると、最も最適なパス上に表示されないノードが削除されます.このようにすると、フィルタを維持しなければならないので、選択可能なデータ構造の種類が制限されます.
反復深化(Iterative deepening)
反復深化は多くのAIアルゴリズムによって採用された方法であり、開始時には推定値を与え、反復によってより正確にする.この名前は、ゲームツリーの検索に何回か連結された前倒しの判定(例えば、将棋ゲーム)に由来します.前の方でもっと多くの操作をしてゲームツリーを深めることができます.結果が変化しない時や多くの向上があると、非常に良い結果を得たと考えられます.たとえそれをより正確にしても、結果は改善しません.反復深化A(IDA)アルゴリズムでは、「深さ」はf値の現在のカットオフ値である.f値が大きいとノードは考慮されない(つまりOPEN集中には加入されない).第1サイクルの場合は、非常に少ないノードだけを処理する必要があります.その後のループ毎に、アクセスノード数が増加する.パスが最適化されていることが分かったら、現在のカットオフ値を増加し続けます.そうでなければ終了します.詳細は、リンクを参照してください.
個人的にはIDA*アルゴリズムがゲーム地図で道を探す時の応用をよく見ていません.反復深化アルゴリズムはしばしば計算時間を増加させ,同時にメモリ需要を低減させる.しかし、地図で道を探すシーンでは、ノードは座標情報だけを含み、必要なメモリは非常に小さい.だからこの部分のメモリの支出を減らします.メリットはあまりありません.
ダイナミック重み
動的重み付けアルゴリズムでは、検索開始時に1つの位置に素早く到達することがより重要であると仮定し、検索終了時に目標位置に到達することがより重要である.
帯域幅検索
帯域幅探索には非常に有用と考えられる二つの特性がある.このアルゴリズム変数はhが過大な推定値であると仮定するが、その推定誤差はeを超えない.このような条件では、検索された経路の価格と最適な経路の価格との誤差はeを超えない.ここでもう一度強調する必要があります.啓発値の設定がよければ、結果もよくなります.
もう一つの特性はOPENのセットの一部のノードを削除することができるかどうかを判断するためです.h＋dが経路の真の代償より大きい限り(いくつかのdについて)、そのf値がOPENのセットの中の最適ノードf値よりも少なくとも大きいe＋dを満たすノードを捨てることができる.これは非常に特異な特性である.f値を得た帯域幅に相当します.この帯域幅におけるすべての予期しないノードは、最適なパスに絶対に現れないと保証されているので、破棄されてもよい.
興味深いことに、この2つの特性に対してそれぞれ異なる啓発値を使用しても、結果が計算されます.ヒントを使って、経路の価格があまり大きくないことを保証します.もう一つのヒントを与えて、OPENの集中しているノードを捨てることを決めます.
双方向検索
最初から最後までの検索とは違って、二つの検索を並行して行うこともできます.一つは始まりから終わりまで、一つは終わりから始まります.それらが出会うと、あなたは一番いいパスを得ることができます.
この考えはいくつかの場合において非常に有用である.双方向検索の主な考えは、検索結果が地図上で扇形に展開されるツリーになります.大きい木は二つの小さい木より遠いので、二つの小さい検索木を使ったほうがいいです.
対面の変形体は二つの検索結果を結びつける.このアルゴリズムは、ベストg(start,x)＋h(x,y)＋g(y,goal)を満たす一対のノードを選択し、ベスト順方向の検索ノードg(start,x)＋h(x,goal)または最適後の検索ノードg(y,goal)＋h(start,y)を選択するものではない.
リダイレクトアルゴリズムは、前方と後方の両方の検索方法を放棄する.アルゴリズムは最初に短い順方向検索を行い、最良の順方向候補ノードを選択する.続いて検索します.このとき、後方サーチは開始ノードに向けられず、得られたばかりの順方向の候補ノードに向けられている.検索後も最適な検索ノードを選択します.次に、順方向検索が実行され、現在の順方向から候補ノードへと続く.このプロセスは、後のノードが重なるまで繰り返します.
ダイナミックAと終身計画A
いくつかのAの変形アルゴリズムは、初期経路計算後の地図変更を可能にする.ダイナミックAは地図情報を全部知らない場合に道を探すために使用できます.すべての情報がないなら、Aアルゴリズムの計算は間違いがあるかもしれません.動的Aの利点は、多くの時間がかかりません.生涯計画Aアルゴリズムは、価格の変化が発生した場合に用いることができる.地図が変更された場合、A計算でパスが無効になる可能性があります.生涯計画Aは以前のA計算を繰り返し利用して新しい道を作ることができる.
しかし、動的Aと終身計画Aは、大量の空間を要求しています.Aアルゴリズムを実行するには、内部情報(OPEN／CLOED集合、パスツリー、g値)を維持する必要があります.経路が変わった時、動的Aまたは生涯計画A＊アルゴリズムは地図の変化によって経路を調整する必要があるかどうかを教えます.
大量の運動ユニットがあるゲームについては、通常はすべての情報を保存したくないので、ダイナミックDとライフプランAは適用されないかもしれません.この二つのアルゴリズムは主にロボットのために設計されている.ロボットが一つしかない場合、メモリを他のロボットの経路のために繰り返し使う必要はありません.もしあなたのゲームが一つまたは少ないユニットであれば、ダイナミックAまたは生涯Aアルゴリズムを研究したいです. D*アルゴリズム概要 D*文章1 D*文章2 生涯計画アルゴリズムの概要 生涯計画アルゴリズム論文(PDF) 生涯計画A*アルゴリズムapple ジャンプポイント検索
Aアルゴリズムの計算速度を高めるほとんどの技術はノード数を減らす戦略をとることである.統一価格の格子ネットワークでは、個々の格子空間を検索するたびに、非常に浪費される.一つの解決方法は、肝心なノード(例えば、角)に道を探すための図を作ることである.しかし、標識図をあらかじめ計算しておきたいという人はいません.じゃ、グリッド上で前にジャンプできるA変体アルゴリズムを見てみます.ジャンプポイントは検索します.現在のノードの子供ノードがOPENのセットに現れる可能性があることを考慮して、ジャンプポイントは現在の点から見られ得る遠いノードに直接ジャンプします.OPEN集合におけるノードの減少に伴い、一歩ごとの価格が高くなりますが、ステップ数も少なくなります.関連の詳細は、リンクを参照することができます.このブログにはよく見える説明があります.また、redditでの長所と短所についての議論はこのリンクをクリックしてもいいです.
また、矩形対称クリッピングには、地図を解析したり、図にジャンプを埋め込んだりしています.これらの2つの技術はいずれも方眼ネットワーク図に適用される.
Thta*
時にはグリッドが道を探すのに使われます.地図はグリッドで生成されます.本当にグリッド上を移動するからではありません.キーポイントの図(例えば、角)がグリッドではなく与えられた場合、Aアルゴリズムはより速く実行され、より優れたパスを得ることができる.しかし、それらのグラフの角を計算しておきたくないなら、Aアルゴリズムの変体Thtaを通じて、方眼ネットワーク上で道を探すことができます.厳密にそれらのチェックに従う必要はありません.父のポインタを構築するときに、先祖とノードの間にエッジが存在すると、テータアルゴリズムは、その祖先に直接にポインタを向けて、すべての中間ノードを無視する.パスが滑らかではないようにAで見つかった経路を直線に変えて、Thtaはそれらの経路の分析をA＊アルゴリズムプロセスの一部とすることができる.このような方法は、後処理格子経路よりも任意の傾斜角の経路にする方法で、より短い経路を得ることができる.この文章はアルゴリズムの合理的な紹介であり、また怠惰なThta*を参考にすることができる.
Thta*の考え方はナビゲーショングリッドにも適用されるかもしれません.
本シリーズ:
Aアルゴリズムのサイクルでは、OPENのセットは、経路を探すために使用されるすべての被検索ノードを保存するために使用される.指向性探索はAアルゴリズムに基づいてOPENのセットサイズに制約条件を設定することによって得られた変形アルゴリズムである.セットが大きすぎると、最も最適なパス上に表示されないノードが削除されます.このようにすると、フィルタを維持しなければならないので、選択可能なデータ構造の種類が制限されます.
反復深化(Iterative deepening)
反復深化は多くのAIアルゴリズムによって採用された方法であり、開始時には推定値を与え、反復によってより正確にする.この名前は、ゲームツリーの検索に何回か連結された前倒しの判定(例えば、将棋ゲーム)に由来します.前の方でもっと多くの操作をしてゲームツリーを深めることができます.結果が変化しない時や多くの向上があると、非常に良い結果を得たと考えられます.たとえそれをより正確にしても、結果は改善しません.反復深化A(IDA)アルゴリズムでは、「深さ」はf値の現在のカットオフ値である.f値が大きいとノードは考慮されない(つまりOPEN集中には加入されない).第1サイクルの場合は、非常に少ないノードだけを処理する必要があります.その後のループ毎に、アクセスノード数が増加する.パスが最適化されていることが分かったら、現在のカットオフ値を増加し続けます.そうでなければ終了します.詳細は、リンクを参照してください.
個人的にはIDA*アルゴリズムがゲーム地図で道を探す時の応用をよく見ていません.反復深化アルゴリズムはしばしば計算時間を増加させ,同時にメモリ需要を低減させる.しかし、地図で道を探すシーンでは、ノードは座標情報だけを含み、必要なメモリは非常に小さい.だからこの部分のメモリの支出を減らします.メリットはあまりありません.
ダイナミック重み
動的重み付けアルゴリズムでは、検索開始時に1つの位置に素早く到達することがより重要であると仮定し、検索終了時に目標位置に到達することがより重要である.
f(p) = g(p) + w(p) * h(p)
帯域幅検索
帯域幅探索には非常に有用と考えられる二つの特性がある.このアルゴリズム変数はhが過大な推定値であると仮定するが、その推定誤差はeを超えない.このような条件では、検索された経路の価格と最適な経路の価格との誤差はeを超えない.ここでもう一度強調する必要があります.啓発値の設定がよければ、結果もよくなります.
もう一つの特性はOPENのセットの一部のノードを削除することができるかどうかを判断するためです.h＋dが経路の真の代償より大きい限り(いくつかのdについて)、そのf値がOPENのセットの中の最適ノードf値よりも少なくとも大きいe＋dを満たすノードを捨てることができる.これは非常に特異な特性である.f値を得た帯域幅に相当します.この帯域幅におけるすべての予期しないノードは、最適なパスに絶対に現れないと保証されているので、破棄されてもよい.
興味深いことに、この2つの特性に対してそれぞれ異なる啓発値を使用しても、結果が計算されます.ヒントを使って、経路の価格があまり大きくないことを保証します.もう一つのヒントを与えて、OPENの集中しているノードを捨てることを決めます.
双方向検索
最初から最後までの検索とは違って、二つの検索を並行して行うこともできます.一つは始まりから終わりまで、一つは終わりから始まります.それらが出会うと、あなたは一番いいパスを得ることができます.
この考えはいくつかの場合において非常に有用である.双方向検索の主な考えは、検索結果が地図上で扇形に展開されるツリーになります.大きい木は二つの小さい木より遠いので、二つの小さい検索木を使ったほうがいいです.
対面の変形体は二つの検索結果を結びつける.このアルゴリズムは、ベストg(start,x)＋h(x,y)＋g(y,goal)を満たす一対のノードを選択し、ベスト順方向の検索ノードg(start,x)＋h(x,goal)または最適後の検索ノードg(y,goal)＋h(start,y)を選択するものではない.
リダイレクトアルゴリズムは、前方と後方の両方の検索方法を放棄する.アルゴリズムは最初に短い順方向検索を行い、最良の順方向候補ノードを選択する.続いて検索します.このとき、後方サーチは開始ノードに向けられず、得られたばかりの順方向の候補ノードに向けられている.検索後も最適な検索ノードを選択します.次に、順方向検索が実行され、現在の順方向から候補ノードへと続く.このプロセスは、後のノードが重なるまで繰り返します.
ダイナミックAと終身計画A
いくつかのAの変形アルゴリズムは、初期経路計算後の地図変更を可能にする.ダイナミックAは地図情報を全部知らない場合に道を探すために使用できます.すべての情報がないなら、Aアルゴリズムの計算は間違いがあるかもしれません.動的Aの利点は、多くの時間がかかりません.生涯計画Aアルゴリズムは、価格の変化が発生した場合に用いることができる.地図が変更された場合、A計算でパスが無効になる可能性があります.生涯計画Aは以前のA計算を繰り返し利用して新しい道を作ることができる.
しかし、動的Aと終身計画Aは、大量の空間を要求しています.Aアルゴリズムを実行するには、内部情報(OPEN／CLOED集合、パスツリー、g値)を維持する必要があります.経路が変わった時、動的Aまたは生涯計画A＊アルゴリズムは地図の変化によって経路を調整する必要があるかどうかを教えます.
大量の運動ユニットがあるゲームについては、通常はすべての情報を保存したくないので、ダイナミックDとライフプランAは適用されないかもしれません.この二つのアルゴリズムは主にロボットのために設計されている.ロボットが一つしかない場合、メモリを他のロボットの経路のために繰り返し使う必要はありません.もしあなたのゲームが一つまたは少ないユニットであれば、ダイナミックAまたは生涯Aアルゴリズムを研究したいです.
Aアルゴリズムの計算速度を高めるほとんどの技術はノード数を減らす戦略をとることである.統一価格の格子ネットワークでは、個々の格子空間を検索するたびに、非常に浪費される.一つの解決方法は、肝心なノード(例えば、角)に道を探すための図を作ることである.しかし、標識図をあらかじめ計算しておきたいという人はいません.じゃ、グリッド上で前にジャンプできるA変体アルゴリズムを見てみます.ジャンプポイントは検索します.現在のノードの子供ノードがOPENのセットに現れる可能性があることを考慮して、ジャンプポイントは現在の点から見られ得る遠いノードに直接ジャンプします.OPEN集合におけるノードの減少に伴い、一歩ごとの価格が高くなりますが、ステップ数も少なくなります.関連の詳細は、リンクを参照することができます.このブログにはよく見える説明があります.また、redditでの長所と短所についての議論はこのリンクをクリックしてもいいです.
また、矩形対称クリッピングには、地図を解析したり、図にジャンプを埋め込んだりしています.これらの2つの技術はいずれも方眼ネットワーク図に適用される.
Thta*
時にはグリッドが道を探すのに使われます.地図はグリッドで生成されます.本当にグリッド上を移動するからではありません.キーポイントの図(例えば、角)がグリッドではなく与えられた場合、Aアルゴリズムはより速く実行され、より優れたパスを得ることができる.しかし、それらのグラフの角を計算しておきたくないなら、Aアルゴリズムの変体Thtaを通じて、方眼ネットワーク上で道を探すことができます.厳密にそれらのチェックに従う必要はありません.父のポインタを構築するときに、先祖とノードの間にエッジが存在すると、テータアルゴリズムは、その祖先に直接にポインタを向けて、すべての中間ノードを無視する.パスが滑らかではないようにAで見つかった経路を直線に変えて、Thtaはそれらの経路の分析をA＊アルゴリズムプロセスの一部とすることができる.このような方法は、後処理格子経路よりも任意の傾斜角の経路にする方法で、より短い経路を得ることができる.この文章はアルゴリズムの合理的な紹介であり、また怠惰なThta*を参考にすることができる.
Thta*の考え方はナビゲーショングリッドにも適用されるかもしれません.