1

ウィキペディアで提供された a* アルゴリズムの疑似コードを c で実装しようとしていますが、reconstruct_path 関数とは何かを理解するのに本当に行き詰まっています。誰かがこの関数の変数 (p、p + current_node、set)代表する？

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)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         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

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

ありがとうございました

4

2 に答える 2

2

came_fromコメントが言うように、ナビゲートされたノードのマップです。いくつかの方法で実装できますが、この目的には従来のマップで問題ありません (リストでも問題ありません)。

マップに慣れていない場合は、std::mapを確認してください。

の目標はA*、与えられた問題 (グラフとして表される) を解決する動きのリストを見つけることです。ソリューションは、グラフを通るパスです。

提案された疑似コードでは、came_from実際に評価しているソリューションの「履歴」を保存します (つまり、グラフを通過する可能性のあるパス)。

ノードを探索する場合 (新しいノード、または既にアクセスしたリストでコストが低いノード):

if neighbor not in openset or tentative_g_score < g_score[neighbor] 
    came_from[neighbor] := current

came_fromあなたが来たノードをマップに保存しています。(ソリューション ノードに到達するまでの移動の順序付きリストとして考える方が簡単です。パフォーマンスの問題のために、リストの代わりにマップが使用されます)。

上記の行は基本的に次のことを意味します。

「今、隣のノードに行きます。現在のノードから来る隣のノードに到達したことを思い出してください」.

goalノードに到達すると、ノードから へA*の移動のリストを返す必要があります。ノードへの参照があるので、移動のリストをマップに格納したため、移動の list( ) を再構築して、ノードから到達することができます。startgoalgoalreconstruct_pathstartcame_from

于 2013-03-02T18:06:28.943 に答える
0

ノードのセットがあり、パス内の各ノードはその前のノード (このノードに移動した元のノード) を「指す」ことができます - これは came_from マップが格納しているものです。

a* 関数がパス内のノードのリスト* を返すようにします。

さて、話を戻しますreturn (p + current_node)- このコードは基本的に p のすべての要素を含むリストを最後に current_node で返すことを意味します。そのpため、 の末尾に 1 つの要素が追加されていpます。

この関数は再帰的であるため、最初に単一の要素が含まれていることがわかります。パスの最初に、これが開始点になります。次に新しい要素を追加goalし、最後に要素を追加します。

これを次のように見ることもできます: アルゴリズムにより、 からgoalへのパスを見つけることができましたstart(ノードの をたどるだけcame_fromで済みます)。この関数を使用すると、再帰startにgoal感謝するまでパスをたどることができるため、正しい順序でパスを含む何らかのリストが得られるはずです。

* リストとは、セットではなく一連の要素を表す構造を意味します。

于 2013-03-02T18:04:13.907 に答える