From b092a120b8c940f1eed2539f9b6d937d347541f9 Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Mon, 18 Dec 2023 02:14:20 +0000 Subject: undo some of the excessive "cleaning" --- utils.py | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/utils.py b/utils.py index 7aaaa61..2328cc2 100644 --- a/utils.py +++ b/utils.py @@ -38,9 +38,14 @@ def a_star( return ret open_heapq: list[tuple[float, int]] = [(h(start), intern(start))] + open_set: set[int] = {intern(start)} g_score: defaultdict[T, float] = defaultdict(lambda: float("inf"), [(start, 0)]) - while open_heapq: - f, current = heappop(open_heapq) + while open_set: + while True: + f, current = heappop(open_heapq) + if current in open_set: + break + open_set.remove(current) current = itov[current] if callable(goal): if goal(current): @@ -53,4 +58,5 @@ def a_star( g_score[neighbour] = tentative_g f_score = tentative_g + h(neighbour) heappush(open_heapq, (f_score, intern(neighbour))) + open_set.add(intern(neighbour)) return None -- cgit v1.2.3-54-g00ecf