Question

In this question you will work with A*. Let’s suppose that you are given an upper bound Z to the cost of the optimal solution of a search problem. We decide to modify A* in the following manner: every time that a node i with f(i) > Z is generated, the node is immediately discarded. • Is this new algorithm guaranteed to find the optimal solution? Explain your answer and state your assumptions. • What will happen if you use a non-admissible heuristic?

Answer 1

A* algorithm uses an evaluation function f(node) to search. For node i, f(i) = g(i) + h(i) where g(i) is the total cost of the path from source node to node i and h(i) is the estimated cost from node i to the goal node.

Let C* be the optimal cost from the source node to the goal node. Followings are some properties of the A* algorithm:

i) A* expands to every node with f(i) < C*

ii) A* will never expand to any node with f(i) > C*

iii) A* expands to some nodes with f(i) = C*

iv) If h is an admissible heuristic function, then A∗ search with h is optimal.

If the A* algorithm is modified such that every time a node with f(i) >Z is generated, the node is immediately discarded, then the optimality depends on the value of Z and nature of heuristic. If the heuristic is admissible, two cases arise based on the value of Z.

Case 1: Z < C*

In this case, the search may be incomplete because A* can't expand to all nodes with f(i) < C*. Hence, doesn't guarantee an optimal solution.

Case 2: Z >=C*

In this case, A* will still expand to every node with f(i) < C*. And since the heuristic function is admissible, it will result in an optimal solution.

If the heuristic is non-admissible, it may overestimate the cost of reaching the goal. Hence, it may or may not result in an optimal solution.