### Python 实现节点定位算法 #### 广度优先搜索 (BFS) 广度优先搜索可以作为一种简单的节点定位方法，在无权图中寻找从起始节点到目标节点的路径。下面是一个基于队列实现的 BFS 算法，该算法能够标记访问过的节点并记录到达各节点的距离。 ```python from collections import deque, defaultdict def bfs(graph, start_node): visited = set() # 记录已访问的节点集合 queue = deque([start_node]) # 初始化队列并将起点加入其中 distances = {start_node: 0} # 存储每个节点距离起点的距离 while queue: node = queue.popleft() if node not in visited: visited.add(node) for neighbor in graph[node]: if neighbor not in visited and neighbor not in queue: queue.append(neighbor) distances[neighbor] = distances[node] + 1 return distances ``` 此代码实现了基本的广度优先遍历功能，并计算了各个节点离给定起点之间的最短步数[^1]。 #### 基于A* 的节点定位优化 对于加权图中的节点定位问题，则更适合采用 A* 搜索算法。这种算法不仅考虑了当前路径的成本，还加入了对未来可能成本的一个预估值 h(n)，从而提高了效率。这里给出一个简化版的 A* 节点定位实现： ```python import heapq def a_star_search(graph, start, goal, heuristic_func): open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} g_score = defaultdict(lambda: float('inf')) g_score[start] = 0 f_score = defaultdict(lambda: float('inf')) f_score[start] = heuristic_func(start, goal) while open_set: _, current = heapq.heappop(open_set) if current == goal: break for neighbor, cost in graph[current].items(): tentative_gscore = g_score[current] + cost if tentative_gscore < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_gscore f_score[neighbor] = tentative_gscore + heuristic_func(neighbor, goal) if neighbor not in [item[1] for item in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) path = reconstruct_path(came_from, start=start, goal=goal) return path def manhattan_distance(point_a, point_b): """曼哈顿距离作为启发式函数""" xa, ya = point_a xb, yb = point_b return abs(xa-xb)+abs(ya-yb) def euclidean_distance(point_a, point_b): """欧几里得距离作为另一种启发式选项""" from math import sqrt xa, ya = point_a xb, yb = point_b return sqrt((xa-xb)**2+(ya-yb)**2) def reconstruct_path(came_from, start, goal): reverse_path = [goal] at = goal while at != start: at = came_from[at] reverse_path.append(at) return list(reversed(reverse_path))[:-1] graph_example = { 'A': {'B': 1}, 'B': {'C': 3,'D':7 }, 'C': {}, 'D': {'E': 8}, 'E': {} } print(a_star_search(graph_example, "A", "E", lambda p,q : 0)[^2]) ``` 上述例子展示了如何利用不同的启发式函数来进行更有效的节点定位操作。注意这里的 `heuristic_func` 参数允许传入任意形式的启发式评估逻辑，可以根据实际情况调整以适应不同场景下的需求.