0
$\begingroup$

What is the difference between this two pseudocode and which one should i implement?

 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.
 g_score[start] := 0                        % Distance from start along optimal path.
 came_from := the empty map                 % The map of navigated nodes.
 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,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]
 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 the empty path

And the second one is

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
openSet := {start}

// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
// to n currently known.
cameFrom := an empty map

// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
gScore := map with default value of Infinity
gScore[start] := 0

// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
// how cheap a path could be from start to finish if it goes through n.
fScore := map with default value of Infinity
fScore[start] := h(start)

while openSet is not empty
    // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
    current := the node in openSet having the lowest fScore[] value
    if current = goal
        return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    for each neighbor of current
        // d(current,neighbor) is the weight of the edge from current to neighbor
        // tentative_gScore is the distance from start to the neighbor through current
        tentative_gScore := gScore[current] + d(current, neighbor)
        if tentative_gScore < gScore[neighbor]
            // This path to neighbor is better than any previous one. Record it!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := tentative_gScore + h(neighbor)
            if neighbor not in openSet
                openSet.add(neighbor)

// Open set is empty but goal was never reached
return failure

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

Both seem to do the same thing but the second is simpler and I don't know which one to use.

$\endgroup$

1 Answer 1

0
$\begingroup$

There is only 1 real difference between them, the first explicitly excludes nodes from the neighbors that have been explored already, but that is easy enough to add in the second implementation however you can guarantee that tentative_gScore < gScore[neighbor] will be false if neighbor has already been explored. Flip a coin and pick one. If you really care you can implement both and evaluate what the exact differences are between them with benchmarks and profiling.

This tends to happen quite often, there are usually more than one equivalent way to implement things like this. However the first option you pick for implementing something is often good enough.

$\endgroup$
3
  • $\begingroup$ If the heuristic function is admissible(never overestimates the actual cost to get to the goal ) and consistent (h(x) ≤ d(x, y) + h(y)) are the two pseudocode equivalent? In that case is the second pseudocode better that the first one? $\endgroup$
    – matthews24
    Jul 26 at 10:41
  • $\begingroup$ @matthews24 my point is that there is no "better" implementation, both are equivalent. Which one is preferable depends on other details like the cpu it's running on, how you find the node in openset having the lowest f_score[] value (this can require special handling when a node in the open set gets a new lower score), etc. $\endgroup$ Jul 27 at 11:58
  • $\begingroup$ But is the second pseudocode taking for granted that the two condition (admissible and consistency) are true? $\endgroup$
    – matthews24
    Jul 27 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.