A* を使用することでメリットが得られるアプリケーションがあります。ただし、従来の理由から、選択する最適なパスが複数ある場合に、以前とまったく同じパスを生成し続ける必要があります。
たとえば、この迷路を考えてみましょう
...バツ FX.S .... S = スタート F = 仕上げ X = 壁 . = 空きスペース
方向優先度アップ。右; 下; 左。幅優先を使用して、パス DLLLU を見つけます。ただし、A* を使用すると、すぐに左に移動し、パス LULLD を見つけることになります。
同点を解消するときは常に正しい方向に展開するようにしました。PreviousNodeより重要な方向から移動するときにポインターを上書きしますが、その例ではどちらも機能しません。これを行う方法はありますか？
元のアルゴリズムが BFS であった場合、「最小」はエッジの全順序によって誘導される辞書式順序に従っている最小の最短パスを探していOrdます (もちろん、「最短」はパスの長さに従っています)。
amit によって提案された重みを微調整するという考えは自然なものですが、情報の破棄を避けるために重みがパスの長さに匹敵するビット数を持つ必要があるため、あまり実用的ではないと思います。アルゴリズムは桁違いに遅くなります。
ありがたいことに、これは A* に 2 つの単純で安価な変更を加えることで実現できます。
startこのセットは、すべての最短パス エッジを考慮すると DAG 構造を持ち、この DAG で からへの辞書編集最小パスを簡単に見つけることができますgoal。これが望ましいソリューションです。概略的には、従来の A* は次のとおりです。
path_length = infinity for every node
path_length[start] = 0
while score(goal) > minimal score of unvisited nodes:
x := any unvisited node with minimal score
mark x as visited
for y in unvisited neighbors of x:
path_length_through_x = path_length[x] + d(x,y)
if path_length[y] > path_length_through_x:
path_length[y] = path_length_through_x
ancestor[y] = x
return [..., ancestor[ancestor[goal]], ancestor[goal], goal]
のscore(x)略ですpath_length[x] + heuristic(x, goal)。
厳密なwhileループ不等式を非厳密なループ不等式に変えて、パス再構築フェーズを追加するだけです。
path_length = infinity for every node
path_length[start] = 0
while score(goal) >= minimal score of unvisited nodes:
x := any unvisited node with minimal score
mark x as visited
for y in unvisited neighbors of x:
path_length_through_x = path_length[x] + d(x,y)
if path_length[y] > path_length_through_x:
path_length[y] = path_length_through_x
optimal_nodes = [goal]
for every x in optimal_nodes: // note: we dynamically add nodes in the loop
for y in neighbors of x not in optimal_nodes:
if path_length[x] == path_length[y] + d(x,y):
add y to optimal_nodes
path = [start]
x = start
while x != goal:
z = undefined
for y in neighbors of x that are in optimal_nodes:
if path_length[y] == path_length[x] + d(x,y):
z = y if (x,y) is smaller than (x,z) according to Ord
x = z
append x to path
return path
警告: クヌースの言葉を引用すると、私はそれが正しいことを証明しただけで、試したわけではありません。
パフォーマンスへの影響に関しては、最小限に抑える必要があります。検索ループは、従来の A* よりも 1 単位高いスコアを持つノードのみを訪問し、再構築フェーズは、最短パスに属するノード数で準線形です。ほとんどの場合、最短経路が 1 つしかない場合、影響は小さくなります。この特殊なケースを最適化することもできます。たとえばancestor、従来のケースのようにノードを記憶することで、複数の先祖がある場合 (つまり、 の場合path_length[y] == path_length_through_x) に特別なエラー値を設定します。検索ループが終了したら、ancestor従来の A* と同様にパスを取得しようとします。パスの構築時にエラー値が発生した場合にのみ、フル パスの再構築を実行する必要があります。
パスの順序の設定をヒューリスティック関数に直接組み込みます
私は最初にパンファーストアルゴリズムを見ていきます
パンファーストアルゴリズムが選択するすべてのパスの関数を定義します。
深さ優先アルゴリズムを実行していると考えてください。これは、n番目の深さで、アルゴリズムによって以前に行われた決定です。x_i \ in {U、R、D、L}割り当てU = 0、R = 1、D = 2、 L = 3
次に、以下を定義します。
g(x_1,..,x_n) = sum_{i=1}^n x_i * (1/4)^i
アルゴリズムがこのステップよりも深いノードにアクセスするとき、すべてのステップでこのステップのg値をg'として修正しましょう。g（）関数は大きくなります。
{1..n} x_iのonが変更されると、将来のすべてのステップで大きくなるため、深さ優先実行中にg関数が常に発生するのは事実です。
注：深さ優先アルゴリズムが成功した場合、最小のg（）値を持つパスが選択されます
注：max（L、R、U、D）= 3であるため、g（）<1
A *のヒューリスティック関数にgを追加しても、最小エッジ長> = 1であるため、最短パス長に干渉しません。
このように変更されたA*が最初に見つける解決策は、深さ優先探索が見つける解決策です。
あなたのために例：
h_bread=g(DLLLU) = (23330)_4 * c
h_astar=g(LULLD) = (30332)_4 * c
（）_4はbase4ですcは定数です（4 ^ {-5}）
あなたの例：h_bread <h_astar
私はこれを行う2つの方法を思いつきました。どちらも、キューの先頭が開始距離 g 値 <= g(終了ノード) である間、アルゴリズムを続行する必要があります。A* で使用されるヒューリスティックは許容可能であるため、これにより、何らかの最適パスに属するすべてのノードが最終的に展開されることが保証されます。
最初の方法は、競合が発生した場合(つまり、両方が最適パスに沿ったノードの親になる可能性がある同じ f 値を持つ 2 つのノードを見つけた場合)、最初のポイントに戻ることで解決します。それらが出会うパスに沿って(これは で簡単に行うことができますO(path-length))。次に、両方のパスの方向優先度を確認し、BFS 検索で優先度が高い方のパスを使用します。
2 番目の方法は、各ノードが水平方向および垂直方向 (および場合によっては斜め方向) に隣接するノード(つまり、4 接続されたグリッド グラフ)に接するグリッドに対してのみ機能します。前と同じことを行いますが、競合を解決するために後戻りする代わりに、最初からパスに沿ったノードを比較し、それらが異なる最初の場所を見つけます。それらが最初に異なる場所は、以前と同じ重要なノードであり、そこから方向の優先度を確認できます。
これは、各ノードのこれまでの最適なパスを保存することによって行います。通常、これは面倒ですが、4 連結グラフがあるため、パスに沿った各方向を格納することで、かなり効率的にこれを行うことができます。これには、ノードあたり 2 ビットしかかかりません。したがって、基本的に整数を使用してパスをエンコードできます。32 ビット レジスタを使用すると、一度に 16 個のノードを比較できます。64 ビット レジスタを備えた 32 ノード。また、128 ビット レジスタ (x86 および x64 プロセッサの SSE レジスタなど) を使用して一度に 64(!) ノードを検索できるため、数百のノードを含むパスの場合でも、この検索は非常に安価になります。
速度をテストするために、@generic human のアルゴリズムと共にこれらの両方を実装しました。50x50 のグリッドに 400 のタワーがあり、
したがって、私のアプリケーションは 4 連結グラフを使用しているため、整数エンコード アルゴリズムが最適なようです。
私が教授に書いた電子メールをここにコピーしました。アルゴリズムのより詳細な説明と、それらが機能することの証明のスケッチが含まれています。
一般に、これを行うための重要な方法はありません。
幅優先探索は、頂点が考慮される順序によって決定される最低次数の最短経路を見つけます。また、同じ長さのパス間の結びつきを断ち切るときは、この順序が他のどの要素よりも優先される必要があります。
例：ノードがA、B、Cの順序で考慮される場合、Node A < Node C。したがって、Aで始まる最短経路とCで始まる最短経路の間に同点がある場合、Aで始まる経路が見つかります。
一方、A *検索では、ノードのヒューリスティック値によって決定される最下位の最短経路が検出されます。したがって、ヒューリスティックは、各ノードへの最低の辞書式パスを考慮に入れる必要があります。そしてそれを見つける唯一の方法はBFSです。