启发式算法python实现的完整可运行代码

以下是使用Python实现的一个简单的A*算法示例，用于在一个二维网格环境中寻找两点之间的最短路径。这个例子并没有包括所有细节，比如错误处理和更复杂的搜索邻接方法，但它提供了一个基本框架：

import heapq

# 假设grid是一个二维列表，True表示障碍物，False表示可以通过
def a_star_search(grid, start, end):
    def is_valid(position):
        x, y = position
        return 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] != True

    def neighbors(position):
        x, y = position
        return [(x+dx, y+dy) for dx, dy in ((0, 1), (1, 0), (-1, 0), (0, -1)) if is_valid((x+dx, y+dy))]

    def heuristic(position):
        x1, y1 = start
        x2, y2 = end
        return abs(x1 - x2) + abs(y1 - y2)

    class Node:
        def __init__(self, position, g, h, f):
            self.position = position
            self.g = g
            self.h = h
            self.f = g + h

        def __lt__(self, other):
            return self.f < other.f

    def search():
        open_list = []
        heapq.heappush(open_list, Node(start, 0, heuristic(start), heuristic(start)))
        closed_list = set()

        while open_list:
            current = heapq.heappop(open_list)

            if current.position == end:
                return current.get_path()

            closed_list.add(current.position)
            for neighbor in neighbors(current.position):
                if neighbor in closed_list:
                    continue

                tentative_g = current.g + 1
                if neighbor not in open_list or tentative_g < neighbor.g:
                    neighbor.g = tentative_g
                    neighbor.h = heuristic(neighbor)
                    neighbor.f = tentative_g + neighbor.h
                    heapq.heappush(open_list, neighbor)

    return search()

# 使用示例
grid = [[False, False, True], [False, True, False], [True, True, True]]
start = (0, 0)
end = (2, 2)
path = a_star_search(grid, start, end)
print("Path:", path)