0

A* アルゴリズムを考えてみましょう。

Google では、適切な疑似コードを見つけることができます。

function A*(start,goal)
     closedset := the empty set                 // The set of nodes already evaluated.     
     openset := set containing the initial node // The set of tentative nodes to be evaluated.
     came_from := the empty map                 // The map of navigated nodes.
     g_score[start] := 0                        // Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x

                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
                 Update(closedset,y)  
                 Update(openset,y)  

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

よくわからないことが 1 つあります。次のような状況を考えてみてください。

ここに画像の説明を入力

A* はどのようにして a->b->c から a->d... に変更できますか? ??? つまり、A* はノードから開始し、ノード間を移動します。ある時点で、ノードには複数の隣接ノードがあり、A* は隣接ノードによって生成されたパスをたどることができますが、ある時点で切り替えることができます...そして、前のステップから始まるそのステップに戻ることができます放棄された道がその道を横切らなかったとしても...

コードでは、この環境を有効にする条件は何ですか?

4

1 に答える 1

1

A* はダイクストラのアルゴリズムの一般化であり、これも幅優先探索 (BFS) の一般化です。検索操作を深さ優先検索 (DFS) に似たものと考えているため、「パスの切り替え」について混乱しているようです。DFS はパスを最後までたどり、少しバックトラックして別のパスを試行し、さらにバックトラックします。これは、実際に探索操作を実行する方法に対応しています (つまり、迷路から抜け出す方法を見つけなければならない場合)。一方、BFS は、訪問する予定のノードのキューを維持します。各反復で、キューの先頭からノードを選択し、その近隣ノードを調べて、未訪問の近隣ノードをキューの末尾に追加します。次に、キューの先頭にある次のノードに進みます。異なるノード間でテレポートする機能が必要になるため、実際にはこれを行うことはできません。:-) Dijkstra と A* は同じ考え方に基づいていますが、代わりにプライオリティ キューを使用し、開始ノードに最も近い「未完成」ノードを常に選択します。これらのアルゴリズムは実際には常にパスを切り替える: 現在最適なパスを提供していると思われるノードを常に調査します。

于 2011-02-23T21:43:14.830 に答える