Spaces:
Sleeping
Sleeping
File size: 564 Bytes
e067c2d 47bba68 e067c2d | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | """Manhattan distance heuristic."""
from typing import Tuple
def manhattan_heuristic(state: Tuple[int, int], goal: Tuple[int, int]) -> float:
"""
Manhattan distance heuristic.
h(n) = |x1 - x2| + |y1 - y2|
Admissible: Assumes minimum cost of 1 per step, which is the minimum possible traffic level.
Args:
state: Current position (x, y)
goal: Goal position (x, y)
Returns:
Estimated cost to reach goal
"""
if goal is None:
return 0.0
return abs(state[0] - goal[0]) + abs(state[1] - goal[1])
|