CODEWITHSUNDEEP
calgorithmgraph-algorithma-star
user2102173
user2102173

Reputation: 13

a* algorithm pseudocode

I am trying to implement in c the pseudocode of a* algorithm given by wikipedia but I am really stuck in understanding what is the reconstruct_path function, can someone explain to me what do the variables in this function (p, p+current_node, set) represent?

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

Thank you

Upvotes: 1

Views: 7299

Answers (2)

Heisenbug
Heisenbug

Reputation: 39164

came_from is a map of navigated nodes, like the comment says. It can be implemented in several ways, but a classic map should be fine for this purpose(even a list is fine).

If you are not familiar with maps, checkout std::map.

The goal of A* is to find a list of moves, that will solve the given problem (represented as a graph). A solution is a path through the graph.

In the pseudocode proposed, came_from store the "history" of the solution you are actually evaluating (so a possible path through the graph).

When you explore a node (a new node or one with less cost in the already visited list):

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

you are saving in the came_from map the node where you come from. (It's simpler to think at it as the ordered list of moves till the solution node is reached. A map is used instead of a list for performance issues).

The line above basically means:

"Now I'll visit neighbor node. Remember that I reached neighbor node coming from current node".

When goal node is reached, A* needs to return the list of moves from start node to goal. You have the reference to the goal node, so you can now recontruct the list(reconstruct_path) of moves to reach it coming from start node, because you stored the list of moves in came_from map.

Upvotes: 2

Marcin Deptuła
Marcin Deptuła

Reputation: 11957

You have a set of nodes and each node in your path can "point" to its predecessor (the node from which you came from to this node) - this is what came_from map is storing .

You want your a* function to return a list* of nodes in the path.

Now, back to return (p + current_node) - this code basically means return a list which contains all elements from p with current_node at the end. So it's p with 1 element added to the end of p.

You can see, that because this function is recursive, at the beginning it will contain a single element - first in your path, which will be a start. You will then add new elements to it, ending with goal element at the end.

You could also look at this this way: your algorithm allowed you to find a path from goal to start (you just need to follow the came_from of your nodes). This function allows you to traverse your path from start to goal thank you recursion, so you should end up with a list of some sort, containing your path in correct order.

* by list I mean some structure that represent a sequence of elements, not a set.

Upvotes: 0

Related Questions