A simple description taken from Wikipedia
The A* search algorithm (pronounced "Ay-star") is a tree search algorithm that finds a path from a given initial node to a given goal node. It employs a "heuristic estimate" which ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.
Description
A* begins at a selected node. Applied to this node are the "cost" of entering this node (usually zero for the initial node). A* then estimates the distance to the goal node from the current node. This estimate and the cost added together are the heuristic which is assigned to the path leading to this node. The node is then added to a priority queue called "Open".
The algorithm then removes the next node from the priority queue (because of the way a priority queue works, the node removed will have the lowest heuristic). If the queue is empty, there is no path from the initial node to the goal node and the algorithm stops. If the node is the goal node, A* constructs and outputs the successful path and stops.
If the node is not the goal node it creates new nodes for admissible adjoining nodes; the exact way of doing this depends on the problem at hand. For each successive node, A* calculates the "cost" of entering the node (the cost is the cumulative sum of all its ancestors plus its own cost) and saves it with the node.
The algorithm then searches a closed node list (nodes whose adjoining nodes have been checked) for the same node. If the node is found in the closed list with a lower or equal cost, no further processing is done on that node with the path associated with it.
If the same node is in the closed but has a higher cost or is not in the list, A* estimates the node's distance to the goal. It then adds the cost and distance estimate together and saves them as the heuristic.
A* then checks to see if this node (i.e. identical nodes that had higher costs) is in the closed list and removes it if it is. It then checks to see if the node is in "Open" priority queue and adds it if it is not. A* then places the original node which it had removed from the "Open" and places it in the closed node list. Then A* pops the next node off of "Open" and starts all over again.
with this background let us try to address your problems
>1. if A* is optimal , why we sitll used closed list in A* ?
We need to remember the nodes that we have expanded already, so that we don't expand the same state repeatedly. Otherwise, we may end up with an implementation which may not terminate at all or which may be very expensive... both scenarios are sub-optimal ....
>because in my understanding , if A* is optimal there is only one best step to the solution?
Allright but you need to be sure that you have not taken this step before... if you have taken this step before and ended up back here, you are going round in circles ( More often, search space is a graph and not a tree)
>2..., in this case, there are 2 posibble solution ?
Yes there can be more than one (optimal)solutions to a problem... given a start state, it may be possible to reach the goal in (minimum possible) N steps in more than one ways (paths)
>but if A* is optimal , is it should there is only 1 best path to reach the solution?
No, as I said above, there can be more than one solutions... however A* will give you one of those best paths (solutions)... it may not enumerate all the best paths but it will give you _an_ optimal solution (not _the_ optimal solution)
You need to differentiate between the algorithm and the problem... existence of more than optiaml solutions or just one optimal solution or no optimal solution is dependent on the problem ... If there is no optimal solution, then A* cannot find you one... however, if there is one or more than one optimal solution, A* will find one for you... A* is just an algorithm which we use to try to find a solution... It has no bearing on the very existence of a solution (or more than one solution)
I am sure you will find this link very useful, take time to read it
http://www.geocities.com/j
good luck for your exam
Main Topics
Browse All Topics
by: SethHoytPosted on 2003-09-29 at 14:38:37ID: 9454982
A* is guaranteed to find *an* optimal solution, not all optimal solutions. It will not return a sub-optimal solution, but there can be other solutions with minimal cost that it does not find.
Basically, we don't care if there are other optimal solutions, since they are all just as good. We would only care if there were a more optimal solution that we didn't find.
-Seth