From ae614f5480c8dc403ec5b713bd745e93e0aa405f Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Mon, 18 Dec 2023 01:43:39 +0000 Subject: clean up a* --- utils.py | 25 +++++++------------------ 1 file changed, 7 insertions(+), 18 deletions(-) diff --git a/utils.py b/utils.py index afdd191..7aaaa61 100644 --- a/utils.py +++ b/utils.py @@ -37,31 +37,20 @@ def a_star( i += 1 return ret - open_set: set[T] = {start} - open_heapq: list[tuple[float, int]] = [(0, intern(start))] - came_from: dict[T, T] = dict() - g_score: defaultdict[T, float] = defaultdict(lambda: float("inf")) - g_score[start] = 0 - f_score: dict[T, float] = dict() - f_score[start] = h(start) - while open_set: - while True: - f, current = heappop(open_heapq) - current = itov[current] - if current in open_set: - break + open_heapq: list[tuple[float, int]] = [(h(start), intern(start))] + g_score: defaultdict[T, float] = defaultdict(lambda: float("inf"), [(start, 0)]) + while open_heapq: + f, current = heappop(open_heapq) + current = itov[current] if callable(goal): if goal(current): return f elif current == goal: return f - open_set.remove(current) for neighbour in neighbours(current): tentative_g = g_score[current] + d(current, neighbour) if tentative_g < g_score[neighbour]: - came_from[neighbour] = current g_score[neighbour] = tentative_g - f_score[neighbour] = tentative_g + h(neighbour) - open_set.add(neighbour) - heappush(open_heapq, (f_score[neighbour], intern(neighbour))) + f_score = tentative_g + h(neighbour) + heappush(open_heapq, (f_score, intern(neighbour))) return None -- cgit v1.2.3-54-g00ecf