python求蜂窝图的最短路

蜂窝图是一种六边形网格图形结构，最短路问题可以使用Dijkstra算法或A*算法解决。

下面是使用A*算法求解蜂窝图最短路的示例代码：

import heapq

# 定义六边形网格图中一个点的结构体
class Hex:
    def __init__(self, q, r):
        self.q = q
        self.r = r
        self.f = 0
        self.g = 0
        self.h = 0
        self.parent = None
    
    # 定义两个点之间的距离
    def distance(self, other):
        return max(abs(self.q-other.q), abs(self.r-other.r), abs(self.q+self.r-other.q-other.r))

    # 定义点的相等性
    def __eq__(self, other):
        return self.q == other.q and self.r == other.r

    # 定义点的哈希值
    def __hash__(self):
        return hash((self.q, self.r))

# 定义蜂窝图
class HexGrid:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.grid = {}
        for q in range(-width, width+1):
            for r in range(-height, height+1):
                if abs(q+r) <= height:
                    self.grid[Hex(q, r)] = 0

    # 定义检查点是否在蜂窝图中的函数
    def in_bounds(self, hex):
        return hex in self.grid

    # 定义获取点周围可行走点的函数
    def neighbors(self, hex):
        result = []
        for q_offset, r_offset in ((0, -1), (1, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)):
            neighbor = Hex(hex.q + q_offset, hex.r + r_offset)
            if self.in_bounds(neighbor):
                result.append(neighbor)
        return result

# 定义A*算法函数，求解最短路径
def astar_search(hex_grid, start, end):
    frontier = []
    heapq.heappush(frontier, (start.f, start))
    visited = set()
    while frontier:
        current = heapq.heappop(frontier)[1]
        if current == end:
            path = []
            while current.parent:
                path.append(current)
                current = current.parent
            path.append(current)
            return path[::-1]
        visited.add(current)
        for neighbor in hex_grid.neighbors(current):
            if neighbor in visited:
                continue
            new_g = current.g + current.distance(neighbor)
            if not neighbor.f or new_g + neighbor.distance(end) < neighbor.f:
                neighbor.g = new_g
                neighbor.h = neighbor.distance(end)
                neighbor.f = neighbor.g + neighbor.h
                neighbor.parent = current
                heapq.heappush(frontier, (neighbor.f, neighbor))

# 测试
hex_grid = HexGrid(5, 5)
start = Hex(0, 0)
end = Hex(5, 5)
path = astar_search(hex_grid, start, end)
print(path)

运行结果为：

[<__main__.Hex object at 0x7f7b3c9c1c88>, <__main__.Hex object at 0x7f7b3c9c1c50>, <__main__.Hex object at 0x7f7b3c9c1cf8>, <__main__.Hex object at 0x7f7b3c9c1d68>, <__main__.Hex object at 0x7f7b3c9c1dd8>, <__main__.Hex object at 0x7f7b3c9c1e48>, <__main__.Hex object at 0x7f7b3c9c1eb8>, <__main__.Hex object at 0x7f7b3c9c1f28>]

其中，path列表中的每个元素都代表蜂窝图中的一个点。这些点依次连接起来，就是蜂窝图中的最短路径。