TIP该文章的性质更多的是个人的知识复盘,更好的方便回顾，可能细节与文章连贯性不会很完善
来源是
Shakey the robot,全球首款可以自动拆解任务并执行的Robot,内核是SRI 开发的 STRIPS 规划器（Stanford Research Institute Problem Solver），其中，STRIPS规划器所使用的核心的算法便是A*算法
A*搜索算法
概念
A*搜索算法，又称启发式搜索,是图遍历以及路径规划的基础方法中较为核心的一种
该算法的核心是通过代价函数 f(n)=g(n)+h(n) 综合考虑“已经走过的代价”和“预计到目标的代价”，优先扩展最有希望的节点，从而高效找到最短路径。
-
g(n)为实际代价:从起点到当前节点已经消耗的路径成本,比如时间，步数，距离等等
-
h(n)为启发函数:从当前节点到目标节点，预计消耗的成本 , 在网格地图中，常常使用曼哈顿距离 , 而在允许斜走的时候，便常用欧氏距离
-
在每一步，程序会计算所有候选节点的f(n),选择最小f(n)对应的节点进行行动，相较于广度优先算法，该算法不再盲目地按照距离层次进行搜索，而是利用启发函数 h(n) 引导搜索方向，使搜索过程更加趋向目标节点，因此能够在保证最优路径的前提下，大幅减少无效节点的扩展，提高搜索效率。
算法代码实现
from queue import PriorityQueue
def heuristic(a, b): """ 曼哈顿距离 heuristic 适用于四方向网格 """ (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2)
def a_star_search(graph, start, goal): """ A* 搜索
graph: 需要提供: - neighbors(node) - cost(from_node, to_node)
start: 起点
goal: 终点 """
frontier = PriorityQueue() frontier.put(start, 0)
came_from = {} cost_so_far = {}
came_from[start] = None cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal: break
for next_node in graph.neighbors(current):
new_cost = ( cost_so_far[current] + graph.cost(current, next_node) )
if ( next_node not in cost_so_far or new_cost < cost_so_far[next_node] ): cost_so_far[next_node] = new_cost
priority = ( new_cost + heuristic(next_node, goal) )
frontier.put(next_node, priority)
came_from[next_node] = current
return came_from, cost_so_farbilibili教程
Q&A
预估函数，我们该如何选择
随着每一步的行动，我们上述的代价函数中 g(n)，也就是实际代价会均匀的增加 而h(n),也就是预计到目标的代价，在理想的预估函数估计下，应该是逐渐减少(最佳是增长量与减少量抵消，代价维持不变，也就是传统二维平面三点共线的情况)，减小量<=增加量，偶尔在遇到障碍物的情况下h(x)也可能增加.用公式表达，就是h(x) ≤ d(x, y) + h(y) ，即h(x)-h(y)代表的预估值的减少量，可以为负，要小于实际代价的增加量d(x,y),这样就能保证f(x)始终是保持一个单调增长的态势，更便于优化,因此，我们通常选择能满足该公式的预估函数，上述文章使用的曼哈顿距离以及欧氏距离都满足这一点
dijkstra算法
概念
Dijkstra（迪杰斯特拉）算法是一种用于求解**单源最短路径问题（Single Source Shortest Path）**的经典算法。
即给定一个节点,Dijkstra算法可以计算这个点到图中其他所有节点的最短距离
每次选距离a最近的点，然后更新
step1
d(a-b) = 2 , d(a-c) = 5 取min,也就是d(a-b)，接下来以b为出发点
step2
d(b-c) = 1 , d(b-d) = 3 此时d(a-c)更新为2+1=3,d(a-d)更新为5，取min,也就是d(a-c),接下来以c为出发点
step3
d(c-d) = 3 , d(c-e) = 4 ,d(c-f) = 1此时d(a-d)不更新(d(a-c-d)>d(a-b-d)),保持5不变,d(a-e) = d(a-c) + d(c-e) = 7 , d(a-f) = 4 选d(a-f)
step4
f无合适到达点，空置，此时已经确定的是{a,b,c,d} d(a-d) = 5 , d(a-e) = 7 选d(a-d)
step5
d(d-e) = 1,d(d-f) = 4 更新d(a-e) d(a-f)
…
最终输出d(a-{x}) , x 包含于 b-f
TIP有点类似于广度优先算法
算法代码实现
def dijkstra(graph, start): """ Dijkstra 最短路径算法
参数: graph: 邻接表 { 节点: [(邻居, 权重), ...] } start: 起点
返回: dist: 从 start 到所有节点的最短距离 prev: 最短路径前驱节点 """
# 初始化距离 dist = {node: float('inf') for node in graph} dist[start] = 0
# 记录路径 prev = {node: None for node in graph}
# 优先队列：(当前距离, 当前节点) heap = [(0, start)]
while heap: current_dist, u = heapq.heappop(heap)
# 如果取出的不是最新距离，跳过 if current_dist > dist[u]: continue
# 遍历邻居 for v, weight in graph[u]: new_dist = current_dist + weight
# 松弛操作 if new_dist < dist[v]: dist[v] = new_dist prev[v] = u
# 加入优先队列 heapq.heappush(heap, (new_dist, v))
return dist, prevbilibili教程
Q&A
广度优先算法
概念
广度优先算法（Breadth-First Search，简称 BFS）是一种用于遍历图、寻找最短路径的算法。它的核心思想是
像水波一样一层一层向外扩散，先访问离起点近的节点，再访问更远的节点。 第一个时间步能访问到哪些节点，第二个时间步…以此类推 由于这里很好理解，就不过多说明,有需要的参考外链,点击前往
算法代码实现
from collections import deque
def bfs(start): queue = deque([start]) visited = set([start])
while queue: node = queue.popleft()
print(node)
for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)
bfs("A")深度优先算法DFS
概念
深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历图、搜索路径以及解决组合优化问题的经典算法。
它的核心思想是：
沿着一条路径不断向更深层节点探索，直到无法继续前进时，再回退（Backtracking）到上一个节点，尝试其他分支。
与广度优先算法 BFS 不同，DFS 不会优先探索距离起点较近的所有节点，而是优先探索当前路径上的深层节点。
算法代码实现
def dfs(graph, start, visited=None): """ 深度优先搜索 DFS graph: 邻接表 start: 起始节点 visited: 已访问节点集合 """
if visited is None: visited = set()
# 标记当前节点 visited.add(start) print(start, end=" ")
# 遍历邻接节点 for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited)
return visited
# 测试图graph = { "A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}
dfs(graph, "A")NOTE也就是先遍历A第一个临近节点B,然后再去遍历B的第一个临近节点D,D没有临近节点,再去遍历B的临近节点E 然后依次是F , C ，该算法同样会遍历所有情况，只是优先去探索的深度，适合去验证路线的连通性
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时