For a given network of cities, find an optimal path to reach from a given source city to any other destination city using an admissible heuristic.
Objective: For a given network of cities, find an optimal path to reach from a given source city to any other destination city using an admissible heuristic. Theory: Heuristics: The heuristic function h(n) tells A* an estimate of the minimum cost from any vertex n to the goal. It’s important to choose a good heuristic function. The heuristic can be used to control A*’s behavior. At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra’s Algorithm, which is guaranteed to find a shortest path. If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower. If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can’t make this happen in all cases, you can make it exact in some special cases. It’s nice to know that given...