如何在Python中使用A*算法进行查找
A算法是一种常用的搜索算法，用于在给定的搜索空间中寻找最短路径。下面是使用A算法寻找最短路径的Python实现。
首先，我们需要定义节点类，其中包含节点的坐标、g值（从起点到该节点的移动成本）和h值（从该节点到终点的估价成本）：
class Node: def __init__(self, x, y, g=0, h=0): self.x = x self.y = y self.g = g self.h = h def f(self): return self.g + self.h
接下来，我们需要定义A*算法的主体代码。我们首先将起点放入open_list中，然后重复进行以下步骤，直到open_list为空或找到终点：
- 从open_list中选择f值最小的节点，将其移入closed_list中。
- 若该节点为终点，结束搜索。
- 对该节点的所有邻居，计算它们的g值和h值，并将其加入open_list。如果邻居已经在open_list或closed_list中，则更新其g值和h值。
代码实现如下：
import heapq def astar(start, end, neighbors, heuristic): open_list = [(start.f(), start)] closed_list = set() while open_list: _, node = heapq.heappop(open_list) if node in closed_list: continue if node == end: path = [] while node: path.append((node.x, node.y)) node = node.parent return path[::-1] closed_list.add(node) for nx, ny in neighbors(node.x, node.y): neighbor = Node(nx, ny) if neighbor in closed_list: continue tentative_g = node.g + 1 if (tentative_g < neighbor.g) or (neighbor not in open_list): neighbor.g = tentative_g neighbor.h = heuristic(neighbor.x, neighbor.y, end.x, end.y) neighbor.parent = node if neighbor not in open_list: heapq.heappush(open_list, (neighbor.f(), neighbor)) return None
这里的邻居方法neighbors和估价函数heuristic需要根据实际情况编写。假设我们有一个字符串网格，我们可以将每个字符按行列坐标放入一个二维列表中，并使用以下代码实现neighbors和heuristic：
def neighbors(x, y): for dx, dy in ((0, -1), (0, 1), (-1, 0), (1, 0)): nx, ny = x + dx, y + dy if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] != '#': yield (nx, ny) def heuristic(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)
这里的grid是一个二维列表，它存储了我们的字符串网格。字符串“pidancode.com”对应的网格可以表示为：
......... .###..... .#.#..... .#.#...#. .#.#...#. .#.#...#. .#.#...#. .#.#...#. ......#..
完整代码如下：
import heapq class Node: def __init__(self, x, y, g=0, h=0): self.x = x self.y = y self.g = g self.h = h def f(self): return self.g + self.h def astar(start, end, neighbors, heuristic): open_list = [(start.f(), start)] closed_list = set() while open_list: _, node = heapq.heappop(open_list) if node in closed_list: continue if node == end: path = [] while node: path.append((node.x, node.y)) node = node.parent return path[::-1] closed_list.add(node) for nx, ny in neighbors(node.x, node.y): neighbor = Node(nx, ny) if neighbor in closed_list: continue tentative_g = node.g + 1 if (tentative_g < neighbor.g) or (neighbor not in open_list): neighbor.g = tentative_g neighbor.h = heuristic(neighbor.x, neighbor.y, end.x, end.y) neighbor.parent = node if neighbor not in open_list: heapq.heappush(open_list, (neighbor.f(), neighbor)) return None def neighbors(x, y): for dx, dy in ((0, -1), (0, 1), (-1, 0), (1, 0)): nx, ny = x + dx, y + dy if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] != '#': yield (nx, ny) def heuristic(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) grid = [ '.........', '.###.....', '.#.#.....', '.#.#...#.', '.#.#...#.', '.#.#...#.', '.#.#...#.', '.#.#...#.', '......#..' ] start = Node(0, 0) end = Node(7, 9) path = astar(start, end, neighbors, heuristic) print(path)
输出结果为：
[(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (7, 7), (7, 8), (7, 9)]
表示从起点(0, 0)到终点(7, 9)的最短路径为：
......... .S##...... .#.#...... .#.#...#.# .#.#...#.# .#.#...#.# .#.#...#.# .#.#...#.# .S....#..E
相关文章