フリンジサーチ

コンピュータサイエンスにおいて、フリンジサーチは、与えられた初期ノードから 1 つの目標ノードまでの最小コストのパスを見つけるグラフ検索アルゴリズムです。

本質的に、フリンジ探索はA*と反復深化 A*バリアント (IDA*)の中間に位置します。

g ( x ) が最初のノードから現在のノードまでの探索パスのコストであり、h ( x ) が現在のノードからゴールまでのコストのヒューリスティック推定値である場合、 $ƒ (x) = g (x) + h (x)$ となり、h * はゴールまでの実際のパスコストになります。ルートノードから左から右への深さ優先探索を再帰的に実行し、ゴールが見つかるか、ノードが最大値ƒに達すると再帰を停止する IDA* について考えます。最初のしきい値ƒでゴールが見つからない場合は、しきい値を増やしてアルゴリズムが再度検索します。つまり、しきい値で反復します。

IDA* には 3 つの大きな非効率性があります。まず、IDA* は、目標ノードへのパスが複数 (場合によっては最適ではない) ある場合、状態を繰り返します。これは、訪問した状態のキャッシュを保持することで解決されることがよくあります。このように変更された IDA* は、ある程度のストレージを使用するため、メモリ拡張 IDA* (ME-IDA*) と呼ばれます。さらに、IDA* は、新しいしきい値で反復する場合、検索で以前のすべての操作を繰り返します。これは、ストレージなしで操作するために必要です。前の反復のリーフノードを保存し、次の反復の開始位置として使用することで、IDA* の効率が大幅に向上します (そうでない場合、最後の反復でツリー内のすべてのノードを常に訪問する必要があります)。

フリンジ検索は、検索ツリーのフロンティアまたはフリンジを反復処理する2 つのリストからなるデータ構造を利用して、IDA* にこれらの改善を実装します。1 つのリストnow には現在の反復が格納され、もう 1 つのリストlater には次の反復が $格納$ されます。したがって、検索ツリーのルートノードでは、nowがルートになり、laterは空になります。次に、アルゴリズムは次の 2 つのアクションのいずれかを実行します。ƒ $(head)$ が現在のしきい値より大きい場合は、head をnowから削除してlaterの末尾に追加します。つまり、 head を次の反復用に保存します。それ以外の場合、 $ƒ$ $(head) が$ しきい値以下の場合は、headを展開してheadを破棄し、その子を考慮してnowの先頭に追加します。反復の終了時に、しきい値が増加し、laterリストがnowリストになり、later は空になります。

ここでのフリンジと A* の重要な違いは、フリンジのリストの内容は必ずしもソートする必要がないことです。これは、オープンリストの順序の維持にコストがかかることが多い A* に比べて大きな利点です。ただし、A* とは異なり、フリンジは同じノードを繰り返し訪問する必要がありますが、そのような訪問のコストは、A* でリストをソートする最悪の場合の対数時間と比較して一定です。

擬似コード

両方のリストを 1 つの二重リンクリストに実装します。現在のノードより前のノードは後続部分で、それ以外はすべて現在のリストです。グリッド内の各ノードのリストに事前に割り当てられたノードの配列を使用すると、リスト内のノードへのアクセス時間が一定に短縮されます。同様に、マーカー配列を使用すると、リスト内のノードの検索を一定時間で実行できます。gはハッシュテーブルとして保存され、最後のマーカー配列は、ノードが以前にアクセスされたかどうか、およびキャッシュエントリが有効かどうかを一定時間で検索するために保存されます。

init (開始,目標)フリンジF = sキャッシュC [開始] = ( 0 , null ) flimit = h (開始)見つかった= false 
       
        
      
      

    while ( found == false ) AND ( F が空でない) fmin = ∞ノードがF内、左から右へ( g 、parent ) = C [ node ] f = g + h ( node )場合、f > flimit fmin = min ( f 、fmin )ノード== goalの場合、続行found = trueの場合、中断子がchildren ( node )内、右から左へg_child = g + cost ( node 、child )場合、C [ child ] != null ( g_cached 、parent ) = C [ child ]場合、g_child >= g_cachedの場合、続行子がF内、 F から子を削除子をFのノードの後ろに挿入C [ child ] = ( g_child 、node )ノードをFから削除flimit = fmin       
          
               
               
                
               
                   
                
               
                  
                
                   
                     
                   
                       
                       
                        
                   
                       
                     
                   
               
          

    到達目標== trueの場合、reverse_path (目標)

逆疑似コード。

逆パス(ノード) 
( g ,親) = C [ノード]親がnull の場合逆パス(親)ノードを印刷

実験

通過不可能な障害物を含むコンピュータゲームに典型的なグリッドベースの環境でテストしたところ、タイルの使用またはオクタイルの使用に応じて、fringe は A* より 10 ～ 40 パーセントほど優れたパフォーマンスを示しました。さらに改善できる点としては、キャッシュに簡単に適応できるデータ構造の使用が挙げられます。

参考文献

Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Johnathan。フリンジサーチ: ゲームマップのパスファインディングで A* に勝つ。2005 IEEE 計算知能とゲームに関するシンポジウム (CIG05) の議事録。エセックス大学、コルチェスター、エセックス、イギリス、2005 年 4 月 4 ～ 6 日。IEEE 2005。https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf

外部リンク

Jesús Manuel Mager Hois による C でのフリンジ検索の実装 https://github.com/pywirrarika/fringesearch