AI: Greedy search against A*

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) and A*: ROUTE (cost N), with routes written A -> B -> C; print greedy: no path and A*: no path if 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

Example 1 · 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
Expected output
greedy: S -> A -> G (cost 11)
A*: S -> B -> C -> G (cost 7)
Example 2 · Input
3
S A 1
A G 1
S G 5
3
S 2
A 1
G 0
S G
Expected output
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))

Lesson: Heuristics and A* search →