7. What happens if the heuristic function is not admissible, but is still nonnegative? What can we say about the path found by A * if the heuristic function

(a) is less than 1 + ϵ times the least-cost path (e.g., is less than 10% greater than the cost of the least-cost path)

(b) is less than δ more than the least-cost path (e.g., is less than 10 units plus the cost of the optimal path)?

Develop a hypothesis about what would happen and show it empirically or prove your hypothesis. Does it change if multiple-path pruning is in effect or not?

Does loosening the heuristic in either of these ways improve efficiency? Try A * search where the heuristic is multiplied by a factor 1 + ϵ, or where a cost δ is added to the heuristic, for a number of graphs. Compare these on the time taken (or the number of nodes expanded)

and the cost of the solution found for a number of values of ϵ or δ.