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)

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)

## No comments:

Post a Comment