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
- If there is a path existing between S to G, it can always find one
- It will always find the one that is optimal (least cost)
- 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
- 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.
- Repeat the following ...
- Pick the lowest cost path ... based on f(X) from the priority queue to explore
- Set current_node to be the last node of the lowest cost path
- If current_node is explored already, skip this node and go back to step 3
- If current_node is the goal, then done. This is the optimal path
- 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)
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
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
return nil # No solution
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)