A* search: Minimizing the total estimated solution cost
• A* Search is an informed search algorithm that combines the advantages of both
Uniform Cost Search and Greedy Best-First Search. It evaluates a node based on
a combination of the cost of the path from the start node to that node and an
estimated heuristic function that estimates the cost to reach the goal form the
current node.
• A∗ search evaluates nodes by combining g(n), the cost to reach the node, and
h(n), the estimated cost to get from the node to the goal: f(n) = g(n) + h(n)
[Link]
[Link]
Algorithm:
1. Start with the initial state as the root node.
2. Create an evaluation function that combines the cost of the path and a heuristic estimate.
3. Initialize an empty priority queue or priority-based data structure.
4. Enqueue the initial state into the priority queue based on the evaluation function.
5. While the priority queue is not empty, do the following:
1. Dequeue the node with the highest priority from the priority queue.
2. If the dequeued node is the goal state, terminate the search and return the solution.
3. Otherwise, expand the node and enqueue its unvisited neighboring nodes into the
priority queue based on the evaluation function.
6. Repeat steps 5 until a solution is found or the priority queue is empty.
[Link]
Completeness:
• A* Search is complete if the search space is finite and the heuristic function is admissible
(never overestimates the actual cost).
Optimality:
• A* Search is optimal if the heuristic function is admissible and consistent (also known as
monotonic).
Time Complexity:
• The time complexity of A* Search depends on the heuristic function, the branching factor, and
the structure of the search space. In the worst case, it can be exponential.
Space Complexity:
• The space complexity of A* Search depends on the size of the priority queue and the number
of nodes stored in memory. In the worst case, it can be exponential.
[Link]
Conditions for optimality: Admissibility and consistency
• The first condition we require for optimality is that h(n) be an admissible
heuristic.
• An admissible heuristic is one that never overestimates the cost to reach the
goal. Admissible heuristics are by nature optimistic because they think the cost
of solving the problem is less than it actually is.
• For example, Straight-line distance is admissible because the shortest path
between any two points is a straight line, so the straight line cannot be an
overestimate.
[Link]
• A second, slightly stronger condition called consistency (or monotonicity) is
required only for applications of A∗ to graph search.
• A heuristic h(n) is consistent if, for every node n and every successor n’ of n
generated by any action a, the estimated cost of reaching the goal from n is no
greater than the step cost of getting to n’ plus the estimated cost of reaching the
goal from n’:
h(n) ≤ c(n, a, n’) + h(n’)
[Link]
Problem with A* Algorithm
• So far we have considered search strategies for OR graphs through which we want to find a
single path to a goal.
• The AND-OR GRAPH (or tree) is useful for representing the solution of problems that can
solved by decomposing them into a set of smaller problems, all of which must then be solved.
This decomposition, or reduction, generates arcs that we call AND arcs. One AND arc may
point to any number of successor nodes, all of which must be solved in order for the arc to
point to a solution.
[Link]
AO Search Algorithm*
[Link]
[Link]
The pseudocode of AO* is as follows:
1. Initialize the graph with a single node (the start node).
2. While the solution graph contains non-terminal nodes (nodes that have
successors not in the graph):
1. Choose a non-terminal node for expansion based on a given strategy.
2. Expand the node (add successors to the graph and update the costs of
nodes).
3. The process continues until the start node is labeled as a terminal node.
[Link]
Advantages of AO Algorithm*
• It can efficiently solve problems with multiple paths due to its use of heuristics.
• It is optimal when the heuristic function is admissible (never overestimates the
true cost).
Disadvantages of AO Algorithm*
• It can consume a large amount of memory, similar to the A* algorithm.
• The performance of AO* is heavily dependent on the accuracy of the heuristic
function. If the heuristic function is not well-chosen, AO* could perform poorly.
[Link]
• Completeness and Optimality
• AO* is complete, meaning it is guaranteed to find a solution if one exists. It is also
optimal, meaning it will find the best solution, provided that the heuristic function
is admissible (never overestimates the true cost) and consistent (satisfies the
triangle inequality).
• Time and Space Complexity
• The time and space complexity of the AO* algorithm is highly dependent on the
problem at hand, particularly the size of the state space, the number of goals, and
the quality of the heuristic function. In the worst case, the algorithm will need to
visit all nodes, and since each node is stored, the space complexity is also
proportional to the number of nodes.
[Link]