2

ウィキペディアの擬似コードに基づいた単純なA*検索プログラムを実装しようとしていました。ただし、開集合の説明は私にはやや不明確です。開始ノードが最初にopensetに追加されることを理解しています。ただし、コードの実行では、でエラーがスローされます。これは、最初の反復中にオープンセットに追加されなかったため、理にかなっていますremove current from openset。current開集合は、ループする前に開始ノードの8つのネイバーも追加する必要があるようです。誰かが私を正しい方向に向けてくれませんか？

ありがとう、

 function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         if neighbor in closedset
             continue
         tentative_g_score := g_score[current] + dist_between(current,neighbor)

         if neighbor not in openset or tentative_g_score <= g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure
4

1 に答える 1

3

「オープンセット」は、選択currentしたノードのセットです。つまり、次に検討する可能性のあるすべてのノードが含まれています。「閉集合」は、すでに検討したノードのセットです。多くの場合、実際の閉集合ではなくNode、名前付きHasBeenVisitedまたは類似のものごとにフラグを設定します。

最初、Openセットにはstart、のみが含まれているため、最初の反復では、を削除startし、そのネイバーをOpenセットに追加startして、Closedセットに追加します。次に、オープンセットの次のノードを取得し、そのネイバーを追加します。

ヒューリスティックが一貫openしていると仮定すると、一度削除されると、それらはセットに再追加されません。

于 2012-11-27T16:50:15.417 に答える