路径规划算法笔记和Python代码实现：贝尔曼-福特（Bellman-Ford）、狄克斯特拉(Dijkstra)、Astar
·
一、贝尔曼-福特算法（Bellman-Ford）
1. 有向加权图
图结构分析：
- 节点V（Vertices）：节点0-7
- 边E（Edges）：带权重的有向边13个
- 正权边：实线箭头，
- 负权边：虚线箭头，表示权重为负
- 起点：节点0（源点）用绿色高亮显示
- 负权边：边4→2（权重-2）和边7→3（权重-1）
注意：这个图不包含从源点0可达的负权环，因为边4→2虽然权重为负，但从0到4的最短路径是7，从4到2是-2，但2到4的路径权重是6，所以没有形成可以减少无限次的循环。
常见图类型的V-E关系：
| 图类型 | 边数量级 | 说明 |
|---|---|---|
| 稀疏图 | E ≈ O(V) | 边数接近顶点数，如树、网格图 |
| 稠密图 | E ≈ O(V²) | 边数接近顶点数的平方 |
| 完全图 | E = V(V-1)/2 | 每个顶点都与其他所有顶点相连 |
2. 算法讲解说明
算法原理
贝尔曼-福特算法是一种用于计算单源最短路径的算法，由Richard Bellman和Lester Ford Jr.提出。与迪杰斯特拉算法不同，贝尔曼-福特算法可以处理带有负权重的边，并能够检测图中是否存在从源点可达的负权环。
核心思想：通过反复松弛（relaxation）所有边，逐渐逼近最短路径。在含有V个顶点的图中，最短路径最多包含V-1条边，因此最多需要进行V-1轮松弛操作。
松弛操作：对于边(u, v, w)，如果dist[u] + w < dist[v]，则更新dist[v] = dist[u] + w。
负权环检测：在完成V-1轮松弛后，再进行一轮松弛。如果仍有边可以松弛，说明图中存在从源点可达的负权环。
松弛概念
-
基本定义
松弛是最短路径算法的核心操作，指通过一条边来尝试改进（缩短）到某个顶点的距离估计。 -
松弛的数学性质
# 三角不等式
对于任意边(u,v,w)，松弛后保证：
dist[v] ≤ dist[u] + w
# 路径松弛性质
如果存在从s到v的最短路径：
s → v₁ → v₂ → ... → v
按顺序松弛这些边，最终dist[v] = 最短距离
出边概念
- 基本定义
出边（Outgoing Edge）是有向图中的一个基本概念，指从一个顶点出发指向其他顶点的边。在数学上，对于有向边 (u, v)，我们称这是顶点 u的一条出边，同时也是顶点 v的一条入边。 - 出边的数学表示
有向图 G = (V, E)，其中 V 是顶点集合，E 是有向边集合
边 e = (u, v) ∈ E 表示从 u 到 v 的有向边
对于顶点 u，其出边集合为：Out(u) = {(u, v) | (u, v) ∈ E}
时间复杂度
- 最坏情况：O(V × E)
- V-1轮循环，每轮遍历所有E条边
- 负权环检测需要额外遍历所有E条边
- 最好情况：O(E)
- 当第一轮松弛后没有更新时，可提前终止
空间复杂度
- 主要存储：O(V + E)
- 距离数组：O(V)
- 边列表：O(E)
- 辅助空间：O(1)
- 仅需少量标志变量
算法特点
| 特性 | 说明 |
|---|---|
| 适用范围 | 有向图/无向图（无向边需转换为两条有向边） |
| 权重限制 | 支持负权重 |
| 负权环 | 能够检测并报告 |
| 效率 | 比迪杰斯特拉算法慢，但更通用 |
| 应用场景 | 路由算法、金融套利检测、图论分析 |
算法步骤总结
- 初始化：源点距离为0，其他顶点距离为∞
- 主循环：进行V-1轮松弛操作
- 提前终止：如果某轮没有更新，可提前结束
- 负权环检测：额外进行一轮松弛检查
- 输出结果：最短路径距离或负权环警告
3. 算法流程图
4. Python代码实现
"""
贝尔曼-福特算法 (Bellman-Ford Algorithm)
功能：计算单源最短路径，支持负权边，可检测负权环
"""
def bellman_ford(edges, num_v):
"""
贝尔曼-福特算法主函数
参数：
edges: 边列表，每个元素为[起点, 终点, 权重]
num_v: 顶点总数
返回：
dist: 从源点（顶点0）到各顶点的最短距离列表
has_negative_cycle: 布尔值，是否存在从源点可达的负权环
"""
# 初始化距离数组：所有顶点距离为无穷大，源点距离为0
dist = [float('inf')] * num_v # 创建长度为num_v的列表，所有元素初始化为无穷大
dist[0] = 0 # 设置源点（顶点0）到自身的距离为0
# 打印算法开始信息
print("=" * 60)
print("贝尔曼-福特算法执行过程")
print("=" * 60)
print(f"顶点数: {num_v}, 边数: {len(edges)}")
print(f"源点: 顶点0")
print()
# 打印表头
print("迭代状态".ljust(12), end="")
for v in range(num_v):
print(f"顶点{v}".center(10), end="")
print()
print("-" * (12 + 10 * num_v))
# 打印初始状态（第0轮迭代前）
print("初始状态".ljust(12), end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print()
# 主循环：最多进行num_v-1轮松弛操作
for i in range(num_v - 1):
updated = False # 标记本轮是否发生更新
# 遍历所有边进行松弛操作
for u, v, w in edges: # u: 起点, v: 终点, w: 权重
# 如果从源点可到达u，且通过u到v的路径更短，则更新dist[v]
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w # 松弛操作：更新最短距离
updated = True # 标记有更新发生
# 打印本轮迭代后的距离数组
iter_name = f"第{i+1}轮"
print(iter_name.ljust(12), end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print(f" 更新: {'是' if updated else '否'}")
# 如果本轮没有更新，提前终止循环（已收敛）
if not updated:
print(f"提前终止：第{i+1}轮后无更新，算法收敛")
break
print("-" * (12 + 10 * num_v))
# 检测负权环：额外进行一轮松弛操作
has_negative_cycle = False
for u, v, w in edges:
# 如果还能继续松弛，说明存在负权环
if dist[u] != float('inf') and dist[u] + w < dist[v]:
has_negative_cycle = True
break
# 输出检测结果
if has_negative_cycle:
print("⚠️ 警告：检测到从源点可达的负权环！")
print(" 最短路径可能不存在（无限减小）")
else:
print("✓ 未检测到负权环")
return dist, has_negative_cycle
def print_shortest_paths(dist, has_negative_cycle):
"""打印最终的最短路径结果"""
print("\n" + "=" * 60)
print("最短路径结果")
print("=" * 60)
if has_negative_cycle:
print("由于存在负权环，以下距离可能不是最终最短路径：")
for i, d in enumerate(dist):
if d == float('inf'):
print(f"顶点0 → 顶点{i}: 不可达")
else:
print(f"顶点0 → 顶点{i}: {d:.2f}")
# 边集格式：[起点, 终点, 成本]，使用有向图
edges = [
[0, 1, 3], # 边0-1，权重3
[0, 2, 5], # 边0-2，权重5
[1, 2, 1], # 边1-2，权重1
[1, 3, 2], # 边1-3，权重2
[2, 3, 4], # 边2-3，权重4
[2, 4, 6], # 边2-4，权重6
[3, 4, 2], # 边3-4，权重2
[3, 5, 1], # 边3-5，权重1
[4, 6, 3], # 边4-6，权重3
[5, 6, 4], # 边5-6，权重4
[6, 7, 2], # 边6-7，权重2
[4, 2, -2], # 边4-2，权重-2（负权边，用于演示）
[7, 3, -1] # 边7-3，权重-1（负权边，但不形成环）
]
# 设置顶点数量
num_vertices = 8
# 执行算法
print("图信息：")
print(f"顶点: 0-{num_vertices-1}")
print("边列表（起点, 终点, 权重）:")
for i, edge in enumerate(edges):
print(f" 边{i:2d}: {edge[0]} → {edge[1]} (权重: {edge[2]:3d})")
print()
distances, negative_cycle = bellman_ford(edges, num_vertices)
print_shortest_paths(distances, negative_cycle)
输出：
图信息：
顶点: 0-7
边列表（起点, 终点, 权重）:
边 0: 0 → 1 (权重: 3)
边 1: 0 → 2 (权重: 5)
边 2: 1 → 2 (权重: 1)
边 3: 1 → 3 (权重: 2)
边 4: 2 → 3 (权重: 4)
边 5: 2 → 4 (权重: 6)
边 6: 3 → 4 (权重: 2)
边 7: 3 → 5 (权重: 1)
边 8: 4 → 6 (权重: 3)
边 9: 5 → 6 (权重: 4)
边10: 6 → 7 (权重: 2)
边11: 4 → 2 (权重: -2)
边12: 7 → 3 (权重: -1)
============================================================
贝尔曼-福特算法执行过程
============================================================
顶点数: 8, 边数: 13
源点: 顶点0
迭代状态 顶点0 顶点1 顶点2 顶点3 顶点4 顶点5 顶点6 顶点7
--------------------------------------------------------------------------------------------
初始状态 0.00 INF INF INF INF INF INF INF
第1轮 0.00 3.00 4.00 5.00 7.00 6.00 10.00 12.00 更新: 是
第2轮 0.00 3.00 4.00 5.00 7.00 6.00 10.00 12.00 更新: 否
提前终止：第2轮后无更新，算法收敛
--------------------------------------------------------------------------------------------
✓ 未检测到负权环
============================================================
最短路径结果
============================================================
顶点0 → 顶点0: 0.00
顶点0 → 顶点1: 3.00
顶点0 → 顶点2: 4.00
顶点0 → 顶点3: 5.00
顶点0 → 顶点4: 7.00
顶点0 → 顶点5: 6.00
顶点0 → 顶点6: 10.00
顶点0 → 顶点7: 12.00
二、狄克斯特拉算法（Dijkstra）
1. 有向加权图
2. 算法讲解说明（双重循环实现）
算法原理
狄克斯特拉算法双重循环实现是最基础的版本，不依赖于优先队列等高级数据结构，通过两层循环实现：
- 外层循环：遍历所有顶点
- 内层循环1：查找未访问顶点中距离最小的顶点
- 内层循环2：更新当前顶点的邻居距离
算法核心思想
- 贪心策略：每次选择当前距离最小的未访问顶点
- 松弛操作：通过选中的顶点更新其邻居的距离
- 确定性：一旦顶点被标记为已访问，其最短距离就确定了
算法步骤详细说明
步骤1: 初始化
- 距离数组dist: 源点距离0，其他顶点∞
- 访问标记visited: 全False
步骤2: 主循环（执行V次）
a. 在未访问顶点中查找dist最小的顶点u
b. 如果找不到，结束循环
c. 标记u为已访问
d. 遍历u的所有邻居v
e. 如果v未访问，尝试更新dist[v]
dist[v] = min(dist[v], dist[u] + w(u,v))
步骤3: 结束
- 输出dist数组
时间复杂度分析
双重循环实现的时间复杂度：
1. 外层循环：执行V次
2. 内层循环1：查找最小距离顶点，需要O(V)时间
3. 内层循环2：遍历所有邻居，总共需要O(E)时间
总时间复杂度 = V × O(V) + O(E) = O(V² + E)
详细分析：
- 查找最小距离顶点：V次循环，每次O(V) → O(V²)
- 更新邻居距离：每条边最多被处理一次 → O(E)
- 总时间复杂度：O(V² + E)
与顶点数和边数的关系：
1. 稀疏图（E ≈ V）：O(V²)
2. 稠密图（E ≈ V²）：O(V²)
3. 最坏情况：O(V²)
空间复杂度分析
空间复杂度：
1. 距离数组dist: O(V)
2. 访问标记visited: O(V)
3. 邻接表edges: O(V + E)
4. 临时变量: O(1)
总空间复杂度：O(V + E)
与优先队列实现的对比
| 特性 | 双重循环实现 | 优先队列实现 |
|---|---|---|
| 时间复杂度 | O(V²) | O((V+E)logV) |
| 空间复杂度 | O(V+E) | O(V+E) |
| 查找最小顶点 | 线性扫描O(V) | 堆取最小O(logV) |
| 适用场景 | 小规模图，顶点数V<1000 | 大规模图，顶点数V较大 |
| 实现难度 | 简单 | 中等 |
| 性能特点 | V较小时快，V大时急剧变慢 | V大时性能稳定 |
算法执行过程示例
以给定图为例：
初始: [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
第1轮: 选择顶点0（距离0）
- 更新顶点1: 0+3=3
- 更新顶点2: 0+5=5
第2轮: 选择顶点1（距离3）
- 更新顶点2: min(5, 3+1)=4
- 更新顶点3: 3+2=5
第3轮: 选择顶点2（距离4）
- 更新顶点3: min(5, 4+4)=5
- 更新顶点4: 4+6=10
第4轮: 选择顶点3（距离5）
- 更新顶点4: min(10, 5+2)=7
- 更新顶点5: 5+1=6
第5轮: 选择顶点5（距离6）
- 更新顶点6: 6+4=10
第6轮: 选择顶点4（距离7）
- 更新顶点2: 7+2=9（但不更新，因为4<9）
- 更新顶点6: min(10, 7+3)=10
第7轮: 选择顶点6（距离10）
- 更新顶点7: 10+2=12
第8轮: 选择顶点7（距离12）
- 更新顶点3: 12+1=13（不更新，因为5<13）
最终结果: [0, 3, 4, 5, 7, 6, 10, 12]
算法局限性
- 负权边问题：不能处理负权边，否则可能得到错误结果
- 效率问题：时间复杂度O(V²)，不适合大规模图
- 无负权环检测：无法检测负权环
- 内存访问模式：线性扫描查找最小顶点，缓存不友好
优化方向
- 使用优先队列：将查找最小顶点的时间从O(V)降为O(logV)
- 斐波那契堆：理论最优O(VlogV + E)，但实现复杂
- 双向搜索：从源点和目标同时搜索
- A*算法：加入启发式函数，加速搜索
算法正确性证明
- 贪心选择性质：每次选择当前距离最小的顶点，其距离已是最短
- 最优子结构：最短路径的子路径也是最短路径
- 松弛操作安全性：松弛操作只减少距离估计，不会增加
- 数学归纳法：可以通过归纳法证明算法正确性
3. 算法流程图（双重循环版本）
4. Python代码实现
"""
狄克斯特拉算法 (Dijkstra's Algorithm) - 双重循环实现
功能：计算单源最短路径，使用最简单的双重循环实现
"""
def dijkstra_double_loop(edges, num_v):
"""
狄克斯特拉算法主函数 - 双重循环实现
参数：
edges: 邻接表表示的图，格式为edges[u] = [(v1, w1), (v2, w2), ...]
num_v: 顶点总数
返回：
dist: 从源点（顶点0）到各顶点的最短距离列表
"""
# 步骤1：初始化距离数组
# 创建长度为num_v的列表，所有元素初始化为无穷大
dist = [float('inf')] * num_v
# 设置源点（顶点0）到自身的距离为0
dist[0] = 0
# 步骤2：标记已访问节点
# 记录哪些顶点的最短路径已确定，初始都为False
visited = [False] * num_v
# 步骤3：打印算法开始信息
print("=" * 60)
print("狄克斯特拉算法（双重循环实现）")
print("=" * 60)
print(f"顶点数: {num_v}, 源点: 顶点0")
print()
# 步骤4：打印表头
# 创建表头：迭代、当前顶点、各顶点距离、状态
print("迭代".center(6) + "|" + "当前顶点".center(10) + "|", end="")
for v in range(num_v):
print(f"顶点{v}".center(10), end="")
print("|" + "状态".center(10))
# 打印分隔线
print("-" * (6 + 10 + 10 * num_v + 10 + 3))
# 步骤5：记录迭代次数并打印初始状态
iteration = 0
# 打印初始状态（第0次迭代）
print(f"{iteration}".center(6) + "|" + "初始".center(10) + "|", end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print("|" + "开始".center(10))
# 步骤6：主循环，每次处理一个顶点，共处理num_v次
for _ in range(num_v):
iteration += 1
# 步骤7：第一重循环 - 在所有未访问的顶点中找到距离最小的顶点
min_dist = float('inf') # 初始化最小距离为无穷大
min_vertex = -1 # 初始化最小距离顶点为-1（表示未找到）
# 遍历所有顶点
for v in range(num_v):
# 如果顶点v未访问且其距离小于当前最小距离
if not visited[v] and dist[v] < min_dist:
min_dist = dist[v] # 更新最小距离
min_vertex = v # 更新最小距离顶点
# 步骤8：如果没有找到可处理的顶点，提前结束循环
if min_vertex == -1:
# 打印结束状态
print(f"{iteration}".center(6) + "|" + "无".center(10) + "|", end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print("|" + "结束".center(10))
break
# 步骤9：标记当前顶点为已访问
visited[min_vertex] = True
current_vertex = min_vertex # 记录当前处理的顶点
# 步骤10：打印当前选择的顶点
print(f"{iteration}".center(6) + f"|选择顶点{current_vertex}".center(10) + "|", end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print(f"|已访问".center(10))
# 步骤11：第二重循环 - 遍历当前顶点的所有邻居，进行松弛操作
# 遍历当前顶点的所有邻居（出边）
for neighbor, weight in edges[current_vertex]:
# 只处理未访问的邻居顶点
if not visited[neighbor]:
# 计算通过当前顶点到达邻居的新距离
new_dist = dist[current_vertex] + weight
# 如果新距离比当前记录的距离更短，更新距离
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
# 打印更新信息
iteration += 1
print(f"{iteration}".center(6) + f"|更新{dist[current_vertex]:.2f}+{weight}".center(10) + "|", end="")
for d in dist:
if d == float('inf'):
print("INF".center(10), end="")
else:
print(f"{d:.2f}".center(10), end="")
print(f"|{current_vertex}→{neighbor}".center(10))
# 步骤12：打印结束分隔线
print("-" * (6 + 10 + 10 * num_v + 10 + 3))
# 步骤13：返回最终的距离数组
return dist
# 邻接表表示的图
edges = [
[(1, 3), (2, 5)], # 顶点0的出边：到顶点1(权重3)，到顶点2(权重5)
[(2, 1), (3, 2)], # 顶点1的出边：到顶点2(权重1)，到顶点3(权重2)
[(3, 4), (4, 6)], # 顶点2的出边：到顶点3(权重4)，到顶点4(权重6)
[(4, 2), (5, 1)], # 顶点3的出边：到顶点4(权重2)，到顶点5(权重1)
[(6, 3), (2, 2)], # 顶点4的出边：到顶点6(权重3)，到顶点2(权重2)
[(6, 4)], # 顶点5的出边：到顶点6(权重4)
[(7, 2)], # 顶点6的出边：到顶点7(权重2)
[(3, 1)] # 顶点7的出边：到顶点3(权重1)
]
# 顶点数量
num_vertices = 8
# 执行算法
print("图信息：")
print(f"顶点: 0-{num_vertices-1}")
print("邻接表：")
for i, neighbors in enumerate(edges):
if neighbors:
neighbor_str = ", ".join(f"顶点{v}(权重{w})" for v, w in neighbors)
print(f" 顶点{i}: [{neighbor_str}]")
else:
print(f" 顶点{i}: []")
print()
distances = dijkstra_double_loop(edges, num_vertices)
# 打印最终结果
print("\n" + "=" * 60)
print("狄克斯特拉算法结果")
print("=" * 60)
print("顶点 | 最短距离")
print("-" * 20)
for v in range(num_vertices):
if distances[v] == float('inf'):
print(f"{v:4d} | {'INF':>10s}")
else:
print(f"{v:4d} | {distances[v]:>10.2f}")
输出：
图信息：
顶点: 0-7
邻接表：
顶点0: [顶点1(权重3), 顶点2(权重5)]
顶点1: [顶点2(权重1), 顶点3(权重2)]
顶点2: [顶点3(权重4), 顶点4(权重6)]
顶点3: [顶点4(权重2), 顶点5(权重1)]
顶点4: [顶点6(权重3), 顶点2(权重2)]
顶点5: [顶点6(权重4)]
顶点6: [顶点7(权重2)]
顶点7: [顶点3(权重1)]
============================================================
狄克斯特拉算法（双重循环实现）
============================================================
顶点数: 8, 源点: 顶点0
迭代 | 当前顶点 | 顶点0 顶点1 顶点2 顶点3 顶点4 顶点5 顶点6 顶点7 | 状态
-------------------------------------------------------------------------------------------------------------
0 | 初始 | 0.00 INF INF INF INF INF INF INF | 开始
1 |选择顶点0 | 0.00 INF INF INF INF INF INF INF |已访问
2 |更新0.00+3 | 0.00 3.00 INF INF INF INF INF INF |0→1
3 |更新0.00+5 | 0.00 3.00 5.00 INF INF INF INF INF |0→2
4 |选择顶点1 | 0.00 3.00 5.00 INF INF INF INF INF |已访问
5 |更新3.00+1 | 0.00 3.00 4.00 INF INF INF INF INF |1→2
6 |更新3.00+2 | 0.00 3.00 4.00 5.00 INF INF INF INF |1→3
7 |选择顶点2 | 0.00 3.00 4.00 5.00 INF INF INF INF |已访问
8 |更新4.00+6 | 0.00 3.00 4.00 5.00 10.00 INF INF INF |2→4
9 |选择顶点3 | 0.00 3.00 4.00 5.00 10.00 INF INF INF |已访问
10 |更新5.00+2 | 0.00 3.00 4.00 5.00 7.00 INF INF INF |3→4
11 |更新5.00+1 | 0.00 3.00 4.00 5.00 7.00 6.00 INF INF |3→5
12 |选择顶点5 | 0.00 3.00 4.00 5.00 7.00 6.00 INF INF |已访问
13 |更新6.00+4 | 0.00 3.00 4.00 5.00 7.00 6.00 10.00 INF |5→6
14 |选择顶点4 | 0.00 3.00 4.00 5.00 7.00 6.00 10.00 INF |已访问
15 |选择顶点6 | 0.00 3.00 4.00 5.00 7.00 6.00 10.00 INF |已访问
16 |更新10.00+2| 0.00 3.00 4.00 5.00 7.00 6.00 10.00 12.00 |6→7
17 |选择顶点7 | 0.00 3.00 4.00 5.00 7.00 6.00 10.00 12.00 |已访问
-------------------------------------------------------------------------------------------------------------
============================================================
狄克斯特拉算法结果
============================================================
顶点 | 最短距离
--------------------
0 | 0.00
1 | 3.00
2 | 4.00
3 | 5.00
4 | 7.00
5 | 6.00
6 | 10.00
7 | 12.00
三、Astar算法
1. A*算法讲解说明
算法原理
A*（A-Star）算法是一种启发式搜索算法，结合了最佳优先搜索和Dijkstra算法的优点，用于在图中寻找从起点到目标点的最短路径。
核心思想：使用评估函数 f(n) = g(n) + h(n) 来决定搜索方向
- g(n)：从起点到节点n的实际成本
- h(n)：从节点n到目标的估计成本（启发式函数）
- f(n)：通过节点n的路径的估计总成本
算法步骤
1. 初始化
- g_score[起点] = 0
- f_score[起点] = h(起点)
- 开放集 = {起点}
- 关闭集 = {}
- 前驱节点记录表
2. 主循环
while 开放集非空:
a. 从开放集中取出f值最小的节点n
b. 如果n是目标节点，重构路径并返回
c. 将n加入关闭集
d. 遍历n的所有邻居m:
如果m在关闭集中，跳过
计算 tentative_g = g_score[n] + cost(n,m)
如果 tentative_g < g_score[m]:
更新 g_score[m] = tentative_g
更新 f_score[m] = g_score[m] + h(m)
记录前驱节点 m的前驱 = n
如果m不在开放集中，加入开放集
3. 结束
- 如果开放集为空且未找到目标，返回无解
启发式函数要求
可采纳性（Admissible）：h(n) ≤ 从n到目标的实际成本
一致性（Consistent）：h(n) ≤ cost(n,m) + h(m) （三角不等式）
常用启发式函数：
- 曼哈顿距离：|x₁-x₂| + |y₁-y₂|（网格中允许四方向移动）
- 欧几里得距离：√[(x₁-x₂)² + (y₁-y₂)²]（允许任意方向移动）
- 切比雪夫距离：max(|x₁-x₂|, |y₁-y₂|)（允许八方向移动）
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最坏情况 | O(b^d) | b-分支因子，d-解深度 |
| 使用优化数据结构 | O(E log V) | 类似Dijkstra |
| 启发式函数质量好 | 远小于O(E log V) | 减少搜索空间 |
详细分析：
- 每个节点最多被处理一次
- 优先队列操作：O(log V)每次插入/删除
- 总操作次数取决于启发式函数质量
- 最坏情况退化为Dijkstra算法
空间复杂度
- 开放集（优先队列）：O(V)最坏情况
- 关闭集：O(V)
- g_score数组：O(V)
- f_score数组：O(V)
- 前驱节点数组：O(V)
- 总空间复杂度：O(V)
算法特性
- 完备性：如果解存在，一定能找到
- 最优性：使用可采纳启发式时保证最优
- 高效性：好的启发式能显著减少搜索空间
- 灵活性：可适应不同启发式函数
优化技术
- 双向A*：从起点和目标同时搜索
- 迭代深化A*：结合深度优先和A*
- 权重A*：w×h(n)加速，牺牲最优性
- 跳点搜索：网格地图优化
- 分层路径查找：预处理层次结构
实际应用
- 游戏开发：NPC寻路（RTS、RPG游戏）
- 机器人导航：自动导引车路径规划
- 地图应用：GPS导航系统
- 物流规划：仓库拣货路径优化
- 网络路由：数据包传输路径选择
算法局限性
- 内存消耗：需要存储所有探索过的节点
- 启发式质量：差的启发式退化为Dijkstra
- 动态障碍：不适合频繁变化的环境
- 连续空间：需要离散化处理
变体和扩展
- IDA*：迭代深化A*，节省内存
- D*：动态A*，处理环境变化
- ARA*：随时A*，时间有限时返回次优解
- Theta*：任意角度路径规划
2. 算法流程图
3. Python代码实现
"""
A*算法 (A-Star Algorithm) 实现
功能：在有向图中寻找从起点到终点的最短路径，使用启发式函数加速搜索
"""
import heapq
import random
import math
def heuristic_manhattan(node1, node2, grid_size):
"""
计算两个节点之间的曼哈顿距离
曼哈顿距离：|x1-x2| + |y1-y2|
参数：
node1: 节点1的坐标 (row1, col1)
node2: 节点2的坐标 (row2, col2)
grid_size: 网格列数，用于将节点编号转换为坐标
返回：
曼哈顿距离
"""
# 将节点编号转换为网格坐标
row1, col1 = divmod(node1, grid_size)
row2, col2 = divmod(node2, grid_size)
# 计算曼哈顿距离
return abs(row1 - row2) + abs(col1 - col2)
def generate_grid_map(rows, cols, obstacle_probability=0.2, start_node=0, end_node=None):
"""
生成随机网格地图
参数：
rows: 网格行数
cols: 网格列数
obstacle_probability: 障碍物生成概率
start_node: 起点节点编号
end_node: 终点节点编号，如果为None则设置为右下角
返回：
nodes: 节点列表，包含每个节点的启发式值
edges: 邻接表，每个节点的邻居和成本
obstacles: 障碍物位置列表
"""
if end_node is None:
end_node = rows * cols - 1 # 默认终点为右下角
total_nodes = rows * cols
# 1. 生成随机障碍物
obstacles = []
for node in range(total_nodes):
# 起点和终点不能是障碍物
if node != start_node and node != end_node:
if random.random() < obstacle_probability:
obstacles.append(node)
# 2. 生成节点启发式值（到终点的曼哈顿距离）
nodes = []
for node in range(total_nodes):
# 如果是障碍物，启发式值为无穷大（表示不可通行）
if node in obstacles:
nodes.append(float('inf'))
else:
nodes.append(heuristic_manhattan(node, end_node, cols))
# 3. 生成邻接表
edges = [[] for _ in range(total_nodes)]
# 定义可能的移动方向：上、下、左、右
directions = [
(-1, 0, 1.0), # 上，成本1.0
(1, 0, 1.0), # 下，成本1.0
(0, -1, 1.0), # 左，成本1.0
(0, 1, 1.0), # 右，成本1.0
# 对角线方向（可选）
# (-1, -1, 1.414), # 左上，成本√2≈1.414
# (-1, 1, 1.414), # 右上，成本√2≈1.414
# (1, -1, 1.414), # 左下，成本√2≈1.414
# (1, 1, 1.414), # 右下，成本√2≈1.414
]
for node in range(total_nodes):
# 如果是障碍物，没有出边
if node in obstacles:
continue
row, col = divmod(node, cols)
for dr, dc, cost in directions:
new_row, new_col = row + dr, col + dc
# 检查新位置是否在网格内
if 0 <= new_row < rows and 0 <= new_col < cols:
neighbor = new_row * cols + new_col
# 检查邻居是否是障碍物
if neighbor not in obstacles:
edges[node].append((neighbor, cost))
return nodes, edges, obstacles, start_node, end_node
def astar_with_trace(edges, nodes, start, goal):
"""
A*算法主函数，带详细追踪
参数：
edges: 邻接表，格式edges[u] = [(v1, cost1), (v2, cost2), ...]
nodes: 节点列表，nodes[i] = 节点i到目标的启发式估计值
start: 起点节点编号
goal: 目标节点编号
返回：
path: 从起点到目标的最短路径（节点列表），如果找不到返回空列表
cost: 路径总成本
trace_info: 追踪信息，用于打印过程
"""
# 初始化
num_nodes = len(nodes)
# g_score: 从起点到当前节点的实际成本
g_score = [float('inf')] * num_nodes
g_score[start] = 0
# f_score: g_score + 启发式值，即估计的总成本
f_score = [float('inf')] * num_nodes
f_score[start] = nodes[start]
# 前驱节点，用于重构路径
came_from = [-1] * num_nodes
# 优先队列，存储(f_score, g_score, 节点, 路径)
open_set = []
heapq.heappush(open_set, (f_score[start], g_score[start], start, [start]))
# 追踪信息
trace_steps = []
# 已访问节点集合
closed_set = set()
print("=" * 80)
print("A*算法执行过程")
print("=" * 80)
print(f"起点: 节点{start}, 目标: 节点{goal}")
print(f"节点总数: {num_nodes}")
print()
# 打印表头
print("步骤".center(5) + "|" + "当前节点".center(10) + "|" + "g(n)".center(10) + "|" +
"h(n)".center(10) + "|" + "f(n)".center(10) + "|" + "开放集大小".center(10) + "|" + "路径".center(30))
print("-" * 85)
step = 0
while open_set:
# 从开放集中取出f值最小的节点
current_f, current_g, current_node, current_path = heapq.heappop(open_set)
# 记录步骤信息
step += 1
open_size = len(open_set)
current_h = nodes[current_node]
print(f"{step:^5}|{current_node:^10}|{current_g:^10.2f}|"
f"{current_h:^10.2f}|{current_f:^10.2f}|{open_size:^10}|{'→'.join(map(str, current_path))}")
trace_steps.append({
'step': step,
'node': current_node,
'g': current_g,
'h': current_h,
'f': current_f,
'path': current_path.copy()
})
# 如果到达目标节点，返回路径
if current_node == goal:
print("-" * 85)
print(f"✓ 找到目标节点 {goal}！")
print(f"总步骤数: {step}")
print(f"路径成本: {current_g}")
print(f"路径: {' → '.join(map(str, current_path))}")
return current_path, current_g, trace_steps
# 将当前节点加入关闭集
closed_set.add(current_node)
# 遍历所有邻居
for neighbor, move_cost in edges[current_node]:
# 如果邻居已在关闭集中，跳过
if neighbor in closed_set:
continue
# 计算从起点经过当前节点到邻居的成本
tentative_g = current_g + move_cost
# 检查这个路径是否更好
if tentative_g < g_score[neighbor]:
# 记录新路径
came_from[neighbor] = current_node
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + nodes[neighbor]
# 创建新路径
new_path = current_path + [neighbor]
# 添加到开放集
heapq.heappush(open_set, (f_score[neighbor], tentative_g, neighbor, new_path))
print("-" * 85)
print("✗ 未找到路径到达目标节点！")
return [], float('inf'), trace_steps
def print_grid(rows, cols, obstacles, path, start, goal):
"""
打印网格地图
参数：
rows: 网格行数
cols: 网格列数
obstacles: 障碍物列表
path: 路径节点列表
start: 起点节点编号
goal: 终点节点编号
"""
print("\n" + "=" * 80)
print("网格地图可视化")
print("=" * 80)
print("图例: S=起点, G=目标, █=障碍物, ·=路径, ○=开放节点")
print()
# 创建网格表示
grid = [[' ' for _ in range(cols)] for _ in range(rows)]
# 标记障碍物
for node in obstacles:
r, c = divmod(node, cols)
grid[r][c] = '█'
# 标记路径
if path:
for node in path:
r, c = divmod(node, cols)
if node != start and node != goal:
grid[r][c] = '.'
# 标记起点和终点
start_r, start_c = divmod(start, cols)
goal_r, goal_c = divmod(goal, cols)
grid[start_r][start_c] = 'S'
grid[goal_r][goal_c] = 'G'
# 打印网格
print(" " + " ".join(str(i) for i in range(cols)))
print(" " + "══" * cols + "═")
for r in range(rows):
print(f"{r:2}║", end="")
for c in range(cols):
print(f"{grid[r][c]} ", end="")
print(f"║ {r}")
print(" " + "══" * cols + "═")
print(" " + " ".join(str(i) for i in range(cols)))
# 打印统计信息
print(f"\n网格大小: {rows}×{cols} = {rows*cols}个节点")
print(f"障碍物数量: {len(obstacles)} ({len(obstacles)/(rows*cols)*100:.1f}%)")
print(f"起点: 节点{start} ({start_r},{start_c})")
print(f"终点: 节点{goal} ({goal_r},{goal_c})")
if path:
print(f"路径长度: {len(path)-1}步")
print(f"路径节点数: {len(path)}")
def print_heuristic_table(nodes, cols, goal):
"""
打印启发式值表
参数：
nodes: 节点列表，包含启发式值
cols: 网格列数
goal: 目标节点编号
"""
rows = len(nodes) // cols
print("\n" + "=" * 80)
print("启发式值表（曼哈顿距离）")
print("=" * 80)
print(f"目标节点: {goal}")
print("每个节点的启发式值 h(n):")
print()
for r in range(rows):
for c in range(cols):
node = r * cols + c
h_value = nodes[node]
if h_value == float('inf'):
print(f"节点{node:2d}(∞)", end=" ")
else:
print(f"节点{node:2d}({h_value:2.0f})", end=" ")
print()
# 生成随机网格地图
print("生成随机网格地图...")
rows, cols = 6, 8 # 6行8列的网格
start_node = 0 # 起点为左上角
goal_node = rows * cols - 1 # 终点为右下角
nodes, edges, obstacles, start_node, goal_node = generate_grid_map(
rows, cols,
obstacle_probability=0.2, # 20%的概率生成障碍物
start_node=start_node,
end_node=goal_node
)
# 打印地图信息
print_grid(rows, cols, obstacles, [], start_node, goal_node)
print_heuristic_table(nodes, cols, goal_node)
# 打印邻接表
print("\n" + "=" * 80)
print("邻接表")
print("=" * 80)
# for i in range(min(10, len(edges))):
for i in range(len(edges)):
if edges[i]:
neighbors_str = ", ".join(f"节点{v}({cost})" for v, cost in edges[i][:5])
if len(edges[i]) > 5:
neighbors_str += f", ... (共{len(edges[i])}个邻居)"
print(f"节点{i}: [{neighbors_str}]")
else:
print(f"节点{i}: [] (障碍物或无出边)")
# 运行A*算法
print("\n" + "=" * 80)
print("开始A*算法搜索...")
print("=" * 80)
path, total_cost, trace_info = astar_with_trace(edges, nodes, start_node, goal_node)
# 打印最终结果
if path:
print("\n" + "=" * 80)
print("A*算法最终结果")
print("=" * 80)
print(f"✓ 找到从节点{start_node}到节点{goal_node}的路径")
print(f"路径成本: {total_cost}")
print(f"路径节点数: {len(path)}")
print(f"路径: {' → '.join(map(str, path))}")
# 打印搜索过程摘要
print(f"\n搜索过程摘要:")
print(f" 总步骤数: {len(trace_info)}")
print(f" 探索节点数: {len(set(sum([t['path'] for t in trace_info], [])))}")
# 可视化最终路径
print_grid(rows, cols, obstacles, path, start_node, goal_node)
else:
print("\n" + "=" * 80)
print("A*算法结果")
print("=" * 80)
print(f"✗ 未找到从节点{start_node}到节点{goal_node}的路径")
# 检查是否可达
print("\n检查连通性...")
visited = set()
stack = [start_node]
while stack:
node = stack.pop()
if node == goal_node:
print("✓ 理论上可达（但A*未找到路径，可能因启发式函数问题）")
break
visited.add(node)
for neighbor, _ in edges[node]:
if neighbor not in visited:
stack.append(neighbor)
else:
print("✗ 起点和终点之间没有通路")
输出：
生成随机网格地图...
================================================================================
网格地图可视化
================================================================================
图例: S=起点, G=目标, █=障碍物, ·=路径, ○=开放节点
0 1 2 3 4 5 6 7
═════════════════
0║S █ █ ║ 0
1║ ║ 1
2║ █ ║ 2
3║ █ █ ║ 3
4║ █ ║ 4
5║ █ G ║ 5
═════════════════
0 1 2 3 4 5 6 7
网格大小: 6×8 = 48个节点
障碍物数量: 7 (14.6%)
起点: 节点0 (0,0)
终点: 节点47 (5,7)
================================================================================
启发式值表（曼哈顿距离）
================================================================================
目标节点: 47
每个节点的启发式值 h(n):
节点 0(12) 节点 1(11) 节点 2(10) 节点 3( 9) 节点 4( 8) 节点 5( 7) 节点 6(∞) 节点 7(∞)
节点 8(11) 节点 9(10) 节点10( 9) 节点11( 8) 节点12( 7) 节点13( 6) 节点14( 5) 节点15( 4)
节点16(10) 节点17( 9) 节点18( 8) 节点19( 7) 节点20(∞) 节点21( 5) 节点22( 4) 节点23( 3)
节点24( 9) 节点25( 8) 节点26( 7) 节点27(∞) 节点28( 5) 节点29( 4) 节点30(∞) 节点31( 2)
节点32( 8) 节点33( 7) 节点34(∞) 节点35( 5) 节点36( 4) 节点37( 3) 节点38( 2) 节点39( 1)
节点40( 7) 节点41(∞) 节点42( 5) 节点43( 4) 节点44( 3) 节点45( 2) 节点46( 1) 节点47( 0)
================================================================================
邻接表
================================================================================
节点0: [节点8(1.0), 节点1(1.0)]
节点1: [节点9(1.0), 节点0(1.0), 节点2(1.0)]
节点2: [节点10(1.0), 节点1(1.0), 节点3(1.0)]
节点3: [节点11(1.0), 节点2(1.0), 节点4(1.0)]
节点4: [节点12(1.0), 节点3(1.0), 节点5(1.0)]
节点5: [节点13(1.0), 节点4(1.0)]
节点6: [] (障碍物或无出边)
节点7: [] (障碍物或无出边)
节点8: [节点0(1.0), 节点16(1.0), 节点9(1.0)]
节点9: [节点1(1.0), 节点17(1.0), 节点8(1.0), 节点10(1.0)]
节点10: [节点2(1.0), 节点18(1.0), 节点9(1.0), 节点11(1.0)]
节点11: [节点3(1.0), 节点19(1.0), 节点10(1.0), 节点12(1.0)]
节点12: [节点4(1.0), 节点11(1.0), 节点13(1.0)]
节点13: [节点5(1.0), 节点21(1.0), 节点12(1.0), 节点14(1.0)]
节点14: [节点22(1.0), 节点13(1.0), 节点15(1.0)]
节点15: [节点23(1.0), 节点14(1.0)]
节点16: [节点8(1.0), 节点24(1.0), 节点17(1.0)]
节点17: [节点9(1.0), 节点25(1.0), 节点16(1.0), 节点18(1.0)]
节点18: [节点10(1.0), 节点26(1.0), 节点17(1.0), 节点19(1.0)]
节点19: [节点11(1.0), 节点18(1.0)]
节点20: [] (障碍物或无出边)
节点21: [节点13(1.0), 节点29(1.0), 节点22(1.0)]
节点22: [节点14(1.0), 节点21(1.0), 节点23(1.0)]
节点23: [节点15(1.0), 节点31(1.0), 节点22(1.0)]
节点24: [节点16(1.0), 节点32(1.0), 节点25(1.0)]
节点25: [节点17(1.0), 节点33(1.0), 节点24(1.0), 节点26(1.0)]
节点26: [节点18(1.0), 节点25(1.0)]
节点27: [] (障碍物或无出边)
节点28: [节点36(1.0), 节点29(1.0)]
节点29: [节点21(1.0), 节点37(1.0), 节点28(1.0)]
节点30: [] (障碍物或无出边)
节点31: [节点23(1.0), 节点39(1.0)]
节点32: [节点24(1.0), 节点40(1.0), 节点33(1.0)]
节点33: [节点25(1.0), 节点32(1.0)]
节点34: [] (障碍物或无出边)
节点35: [节点43(1.0), 节点36(1.0)]
节点36: [节点28(1.0), 节点44(1.0), 节点35(1.0), 节点37(1.0)]
节点37: [节点29(1.0), 节点45(1.0), 节点36(1.0), 节点38(1.0)]
节点38: [节点46(1.0), 节点37(1.0), 节点39(1.0)]
节点39: [节点31(1.0), 节点47(1.0), 节点38(1.0)]
节点40: [节点32(1.0)]
节点41: [] (障碍物或无出边)
节点42: [节点43(1.0)]
节点43: [节点35(1.0), 节点42(1.0), 节点44(1.0)]
节点44: [节点36(1.0), 节点43(1.0), 节点45(1.0)]
节点45: [节点37(1.0), 节点44(1.0), 节点46(1.0)]
节点46: [节点38(1.0), 节点45(1.0), 节点47(1.0)]
节点47: [节点39(1.0), 节点46(1.0)]
================================================================================
开始A*算法搜索...
================================================================================
================================================================================
A*算法执行过程
================================================================================
起点: 节点0, 目标: 节点47
节点总数: 48
步骤 | 当前节点 | g(n) | h(n) | f(n) | 开放集大小 | 路径
-------------------------------------------------------------------------------------
1 | 0 | 0.00 | 12.00 | 12.00 | 0 |0
2 | 1 | 1.00 | 11.00 | 12.00 | 1 |0→1
3 | 8 | 1.00 | 11.00 | 12.00 | 2 |0→8
4 | 2 | 2.00 | 10.00 | 12.00 | 2 |0→1→2
5 | 9 | 2.00 | 10.00 | 12.00 | 3 |0→1→9
6 | 16 | 2.00 | 10.00 | 12.00 | 3 |0→8→16
7 | 3 | 3.00 | 9.00 | 12.00 | 3 |0→1→2→3
8 | 10 | 3.00 | 9.00 | 12.00 | 4 |0→1→2→10
9 | 17 | 3.00 | 9.00 | 12.00 | 4 |0→1→9→17
10 | 24 | 3.00 | 9.00 | 12.00 | 4 |0→8→16→24
11 | 4 | 4.00 | 8.00 | 12.00 | 4 |0→1→2→3→4
12 | 11 | 4.00 | 8.00 | 12.00 | 5 |0→1→2→3→11
13 | 18 | 4.00 | 8.00 | 12.00 | 5 |0→1→2→10→18
14 | 25 | 4.00 | 8.00 | 12.00 | 5 |0→1→9→17→25
15 | 32 | 4.00 | 8.00 | 12.00 | 5 |0→8→16→24→32
16 | 5 | 5.00 | 7.00 | 12.00 | 5 |0→1→2→3→4→5
17 | 12 | 5.00 | 7.00 | 12.00 | 5 |0→1→2→3→4→12
18 | 19 | 5.00 | 7.00 | 12.00 | 4 |0→1→2→3→11→19
19 | 26 | 5.00 | 7.00 | 12.00 | 3 |0→1→2→10→18→26
20 | 33 | 5.00 | 7.00 | 12.00 | 2 |0→1→9→17→25→33
21 | 40 | 5.00 | 7.00 | 12.00 | 1 |0→8→16→24→32→40
22 | 13 | 6.00 | 6.00 | 12.00 | 0 |0→1→2→3→4→5→13
23 | 14 | 7.00 | 5.00 | 12.00 | 1 |0→1→2→3→4→5→13→14
24 | 21 | 7.00 | 5.00 | 12.00 | 2 |0→1→2→3→4→5→13→21
25 | 15 | 8.00 | 4.00 | 12.00 | 2 |0→1→2→3→4→5→13→14→15
26 | 22 | 8.00 | 4.00 | 12.00 | 2 |0→1→2→3→4→5→13→14→22
27 | 29 | 8.00 | 4.00 | 12.00 | 1 |0→1→2→3→4→5→13→21→29
28 | 23 | 9.00 | 3.00 | 12.00 | 2 |0→1→2→3→4→5→13→14→15→23
29 | 37 | 9.00 | 3.00 | 12.00 | 2 |0→1→2→3→4→5→13→21→29→37
30 | 31 | 10.00 | 2.00 | 12.00 | 4 |0→1→2→3→4→5→13→14→15→23→31
31 | 38 | 10.00 | 2.00 | 12.00 | 4 |0→1→2→3→4→5→13→21→29→37→38
32 | 45 | 10.00 | 2.00 | 12.00 | 4 |0→1→2→3→4→5→13→21→29→37→45
33 | 39 | 11.00 | 1.00 | 12.00 | 4 |0→1→2→3→4→5→13→14→15→23→31→39
34 | 46 | 11.00 | 1.00 | 12.00 | 4 |0→1→2→3→4→5→13→21→29→37→38→46
35 | 47 | 12.00 | 0.00 | 12.00 | 3 |0→1→2→3→4→5→13→14→15→23→31→39→47
-------------------------------------------------------------------------------------
✓ 找到目标节点 47！
总步骤数: 35
路径成本: 12.0
路径: 0 → 1 → 2 → 3 → 4 → 5 → 13 → 14 → 15 → 23 → 31 → 39 → 47
================================================================================
A*算法最终结果
================================================================================
✓ 找到从节点0到节点47的路径
路径成本: 12.0
路径节点数: 13
路径: 0 → 1 → 2 → 3 → 4 → 5 → 13 → 14 → 15 → 23 → 31 → 39 → 47
搜索过程摘要:
总步骤数: 35
探索节点数: 35
================================================================================
网格地图可视化
================================================================================
图例: S=起点, G=目标, █=障碍物, ·=路径, ○=开放节点
0 1 2 3 4 5 6 7
═════════════════
0║S . . . . . █ █ ║ 0
1║ . . . ║ 1
2║ █ . ║ 2
3║ █ █ . ║ 3
4║ █ . ║ 4
5║ █ G ║ 5
═════════════════
0 1 2 3 4 5 6 7
网格大小: 6×8 = 48个节点
障碍物数量: 7 (14.6%)
起点: 节点0 (0,0)
终点: 节点47 (5,7)
路径长度: 12步
路径节点数: 13
四、A* vs Dijkstra vs BFS vs Bellman-Ford 算法对比
1. 算法对比总表
| 特性 | BFS | Dijkstra | Bellman-Ford | A* |
|---|---|---|---|---|
| 类型 | 无权图搜索 | 单源最短路径 | 单源最短路径 | 启发式搜索 |
| 数据结构 | 队列 | 优先队列 | 数组/队列 | 优先队列 |
| 权重处理 | 不支持权重 | 非负权重 | 任意权重 | 非负权重 |
| 负权边 | 不适用 | ❌ 不支持 | ✅ 支持 | ❌ 不支持 |
| 负权环 | 不适用 | ❌ 不检测 | ✅ 可检测 | ❌ 不检测 |
| 时间复杂度 | O(V+E) | O((V+E)logV) | O(VE) | O(b^d) 最坏 O((V+E)logV) 平均 |
| 空间复杂度 | O(V) | O(V) | O(V) | O(V) |
| 启发式 | 无 | 无 | 无 | ✅ 有 |
| 最优性 | ✅ 是（无权） | ✅ 是 | ✅ 是 | ✅ 是（h可采纳） |
| 完备性 | ✅ 是 | ✅ 是 | ✅ 是 | ✅ 是 |
| 搜索方向 | 均匀扩展 | 距离优先 | 边松弛 | 启发式引导 |
| 主要应用 | 无权图、树搜索 | 路由协议、地图 | 负权图、金融 | 游戏AI、导航 |
2. 算法选择决策树
这里是“一人公司”的成长家园。我们提供从产品曝光、技术变现到法律财税的全栈内容，并连接云服务、办公空间等稀缺资源，助你专注创造，无忧运营。
更多推荐
36
0- 0
已为社区贡献2条内容
所有评论(0)