A* search with an admissible heuristic
Uninformed search explores in every direction. Informed search uses a heuristic function h(n), an estimate of the remaining cost from a state n to the goal. A* orders its frontier by f(n) = g(n) + h(n), where g(n) is the cost of the best path found so far. It always expands the state with the lowest estimated total cost.
Python
import heapq
GRID = [
"S.......",
"........",
"..####..",
"........",
"........",
".......G",
]
def find(symbol):
for r, row in enumerate(GRID):
if symbol in row:
return (r, row.index(symbol))
START, GOAL = find("S"), find("G")
def manhattan(cell):
return abs(cell[0] - GOAL[0]) + abs(cell[1] - GOAL[1])
def search(heuristic):
frontier = [(heuristic(START), heuristic(START), 0, START)]
best = {START: 0}
expanded = 0
while frontier:
_, _, cost, cell = heapq.heappop(frontier)
if cost > best[cell]:
continue
expanded += 1
if cell == GOAL:
return cost, expanded
r, c = cell
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < len(GRID) and 0 <= nc < len(GRID[0]) and GRID[nr][nc] != "#":
new_cost = cost + 1
if new_cost < best.get((nr, nc), 10**9):
best[(nr, nc)] = new_cost
h = heuristic((nr, nc))
heapq.heappush(frontier, (new_cost + h, h, new_cost, (nr, nc)))
return None
print(search(manhattan))
print(search(lambda cell: 0))