贪心最佳优先搜索（GBFS）算法是一种在路径搜索中非常实用的算法，它通过选择当前看起来最接近目标的路径来引导搜索方向。本文将详细解释GBFS算法的工作原理、如何在Python中实现该算法，以及它在网格路径搜索中的应用。
GBFS算法的工作原理可以概括为以下几个步骤：从初始位置或节点开始，评估所有可能的下一步选项，选择看起来最接近目标的选项，然后重复这个过程直到达到目标。这种方法听起来很简单，但需要注意的是，GBFS算法并不总是能找到最短路径，因为它只考虑当前的最佳选择，而不是整个旅程。
在Python中实现GBFS算法，首先定义一个节点类，用于表示网格中的一个点，并存储到达该节点的成本。然后，使用欧几里得距离作为启发式函数，计算到达目标的直线距离。接着，使用Python的heapq库来管理优先队列，确保总是选择成本最小的下一个节点。还使用一个集合来跟踪已经检查过的节点，以避免重复处理。
import heapq
import math
class Node:
def __init__(self, x, y, cost):
self.x = x
self.y = y
self.cost = cost
def __lt__(self, other):
return self.cost < other.cost
def euclidean_distance(x1, y1, x2, y2):
return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
def greedy_best_first_search(grid, start, goal):
rows = len(grid)
cols = len(grid[0])
pq = []
heapq.heappush(pq, Node(start[0], start[1], 0))
visited = set()
visited.add((start[0], start[1]))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while pq:
current = heapq.heappop(pq)
if (current.x, current.y) == goal:
print(f"Goal reached at ({current.x}, {current.y})")
return
for d in directions:
new_x, new_y = current.x + d[0], current.y + d[1]
if 0 <= new_x < rows and 0 <= new_y < cols and grid[new_x][new_y] == 0 and (new_x, new_y) not in visited:
cost = euclidean_distance(new_x, new_y, goal[0], goal[1])
heapq.heappush(pq, Node(new_x, new_y, cost))
visited.add((new_x, new_y))
print("Goal not reachable")