diff options
| -rw-r--r-- | utils.py | 10 |
1 files changed, 8 insertions, 2 deletions
@@ -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 |