Mô phỏng thuật toán Tìm đường A*

A* Search · Nhóm: Đồ thị

Tìm đường A* (A* Search), nhóm Đồ thị.

Mã Python

def a_star(grid, start, goal):
    open_set = {start}
    g = {start: 0}
    f = {start: h(start, goal)}
    while open_set:
        cur = min(open_set, key=lambda n: f[n])
        if cur == goal:
            return reconstruct(cur)
        open_set.remove(cur); closed.add(cur)
        for nb in neighbors(cur, grid):
            ng = g[cur] + 1
            if ng < g.get(nb, INF):
                parent[nb] = cur
                g[nb] = ng; f[nb] = ng + h(nb, goal)
                open_set.add(nb)
    return None

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.