See for yourself why A* needs the cost so far.
What to build
A program that runs greedy best-first search and A* on the same map and prints both routes.
Requirements
- Roads go both ways. Greedy expands the town with the smallest h (ties: name); it records a town's parent when it first finds the town. A* expands the smallest g + h (ties: smaller h, then name) and updates a town's parent when it finds a cheaper path. Both stop when the goal is taken out of the frontier and never expand a town twice.
- Print
greedy: ROUTE (cost N)andA*: ROUTE (cost N), with routes writtenA -> B -> C; printgreedy: no pathandA*: no pathif the goal cannot be reached.
Input
Line 1: r. Then r lines TOWN TOWN COST. Then a line with n and n lines TOWN H. Last line: start and goal.
Output
Two lines.
Constraints
r ≤ 100; every town has an h value; the heuristic is consistent.
Example
Input:
5
S A 5
A G 6
S B 2
B C 2
C G 3
5
S 6
A 2
B 4
C 3
G 0
S G
Output:
greedy: S -> A -> G (cost 11)
A*: S -> B -> C -> G (cost 7)
Why it works
Greedy follows the estimate alone and can commit to an expensive route; A* adds the cost so far, so with an admissible heuristic the goal comes out of the frontier along a cheapest route.
Examples
5 S A 5 A G 6 S B 2 B C 2 C G 3 5 S 6 A 2 B 4 C 3 G 0 S G
greedy: S -> A -> G (cost 11) A*: S -> B -> C -> G (cost 7)
3 S A 1 A G 1 S G 5 3 S 2 A 1 G 0 S G
greedy: S -> G (cost 5) A*: S -> A -> G (cost 2)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Write one search loop and pass it the priority: (h, name) for greedy, (g + h, h, name) for A*.
Hint 2
For greedy, keep the first parent found for each town; for A*, update the parent whenever a cheaper path is found.
Solution
Show one correct solution (try it yourself first)
import heapq
roads = {}
for _ in range(int(input())):
a, b, cost = input().split()
roads.setdefault(a, {})[b] = int(cost)
roads.setdefault(b, {})[a] = int(cost)
h = {}
for _ in range(int(input())):
town, value = input().split()
h[town] = int(value)
start, goal = input().split()
def search(astar):
def key(g, town):
return (g + h[town], h[town], town) if astar else (h[town], town)
frontier = [(key(0, start), start)]
best, parent, done = {start: 0}, {start: None}, set()
while frontier:
_, town = heapq.heappop(frontier)
if town in done:
continue
done.add(town)
if town == goal:
path = [goal]
while parent[path[-1]]:
path.append(parent[path[-1]])
return " -> ".join(reversed(path)) + f" (cost {best[goal]})"
for nxt, step in roads.get(town, {}).items():
cost = best[town] + step
if nxt not in best or (astar and cost < best[nxt] and nxt not in done):
best[nxt], parent[nxt] = cost, town
heapq.heappush(frontier, (key(cost, nxt), nxt))
return "no path"
print("greedy:", search(False))
print("A*:", search(True))