A* Search

Given a start state S and a Goal state G, find an optimal path S -> A -> B -> ... -> G

We can assign a cost to each arc so the optimal path is represented with the lowest sum of cost. This problem can be modeled as a weighted Graph where nodes represent a state and cost associated arcs represent the transition from one state to another.

A* search is one of the most popular search algorithm and it has the following characteristics

1. If there is a path existing between S to G, it can always find one
2. It will always find the one that is optimal (least cost)
   

Here is the description of the algorithm

• Define a function: f(X) = g(X) + h(X) where ...
• g(X) = minimal cost path from A to X
• h(X) = a heuristic estimation cost from X to S. It is important that the estimated cost h(X) is less than the actual cost
  

1. The algorithm keep track of a list of partially explored path, with an associated f(X) within a priority queue as well as a list of explored nodes. Initially the priority queue contain just one path [S] with cost C and the visited node list contains just S.
2. Repeat the following ...
3. Pick the lowest cost path ... based on f(X) from the priority queue to explore
4. Set current_node to be the last node of the lowest cost path
5. If current_node is explored already, skip this node and go back to step 3
   
6. If current_node is the goal, then done. This is the optimal path
7. Otherwise, find out all the neighbours of the current_node. For each of them, insert a path that leads to them into the priority queue.
   

def A_Search(S, G)
 visited_nodes = [S]
 priorityQ.add([] << S)
 while priorityQ.non_empty
   lowest_cost_path = priorityQ.first  # according to f(X)
   node_to_explore = lowest_cost_path.last_node
   continue if visited_nodes contains node_to_explore
   if node_to_explore == G
     return lowest_cost_path
   else
     add node_to_explore to visited_nodes
     for each v in node_to_explore.neighbors
       new_path = lowest_cost_path << v
       insert new_path to priorityQ
     end
   end
 end
 return nil # No solution
end

Proof: A* Search can always find a path if it exist

This should be obvious because the while loop will only terminate if the Goal is reached or all connected node has been explored

Proof: A* Search will find the path with least cost

Lets say the algorithm find a path S -> A -> K -> ... -> G which is not the optimal path
S -> A -> B -> ... -> G

That means, in the last extraction from the priorityQ, f(G) is smaller than f(B)

This is not possible because ...
f(G) == cost(S->A->K...G) > cost (S->A->B...G) > g(B) + h(B) == f(B)