Consider what happens if the heuristic function is not admissible, but is still non-negative. What guarantees can be made when the path found by A∗ when 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 always no more than 10 units greater than 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 δ.