图的路径搜索算法

首先，我们来看一道路径搜索中的经典问题：罗马尼亚旅行问题。 

本题要求我们找到从Arad到Bucharest的最优路径，右边列表是每一个城市到达终点Bucharest的直线距离， 解决这个问题，我们可以采取无信息搜索和信息搜索两种大的方向。

1.无信息搜索 

无信息搜索也被称为盲目搜索，该术语（无信息、盲目的）意味着该搜索策略没有超出问题定义提供的状态之外的附加信息。所有能做的就是生成后继节点，并且区分一个目标状态或一个非目标状态。所有的搜索策略是由节点扩展的顺序加以区分。

a.广度优先搜索（BFS）

核心原理

• 扩展顺序：按层遍历，优先探索当前层的所有节点，再进入下一层。

• 数据结构：使用队列（FIFO）管理待扩展节点。

• 目标检测：在生成节点时立即检查是否为目标（即“生成即检测”）。

特点

• 完备性：在有限状态空间中总能找到解（若存在）。

• 最优性：在无权图中保证找到最少步数路径。

• 时间复杂度：O(V+E)，V为节点数，E为边数。

• 空间复杂度：O(V)，需存储所有已访问节点。

适用场景

• 社交网络中寻找最短关系链。

• 迷宫问题中找最短路径（所有移动成本相同）。

• 网络爬虫按层级抓取网页。

本题应用

在本题中，应用广度优先搜索，按层拓展，找到最少步数路径，完备且最优（步数最少），但内存占用高（需存储所有已扩展节点）

b.深度优先算法（DFS）

核心原理

• 扩展方式：与DFS类似，但限制最大搜索深度 L。

• 终止条件：达到深度 L 或找到目标。

特点

• 完备性：若解在深度 L 内则完备，否则不完备。

• 最优性：不保证最优（可能因深度限制错过更优解）。

• 空间复杂度：O(L)，仅需存储当前路径。

适用场景

• 已知解深度范围的问题（如棋类游戏有限步数分析）。

• 避免DFS陷入无限深度的图（如循环状态机）。

本题应用

在本题中，深度优先算法，按单一路径深入到底，可能找到非最优路径，内存占用低，但不完备（可能陷入循环），不保证最优。

c.一致代价搜索 （UCS）

核心原理

• 扩展顺序：优先扩展从起点到当前节点累计成本最低的节点。

• 数据结构：使用优先级队列（按路径成本排序）。

• 目标检测：在扩展节点时检查目标。

特点

• 完备性：在非负权重图中总能找到解。

• 最优性：保证找到最小成本路径（类似Dijkstra算法）。

• 时间复杂度：O((V+E)log⁡V（优先队列优化）。

• 空间复杂度：O(V)，需记录所有节点的最小成本。

适用场景

• 交通路线规划（道路长度/时间不同）。

• 资源分配优化（如最小能耗路径）。

• 电网中寻找最低损耗输电路径。

本题应用

在本题中，应用一致代价搜索，优先扩展路径成本最低的节点，完备且最优（成本最低），但内存占用高。

本方法就是让路线不断的向外扩展，将代价从小到达进行逐步叠加，直到找到所需路径位置，如本题所示：

我们从Arad出发，代价最小的一条路是到Zerid，但是我们需要到达的目的地是Bucharest，我们需要继续寻找，发现此时代价最小的路径是到Timisara，但是还不是我们要找的路，接着寻找，然后就是Sibiu，Oradea，直到我们找到了一条Arad- Sibiu-Rimnicu-Pitesti-Bucharest这条路径能顺利到达目的地并且此时的路径最短，我们选择了它。

d.迭代加深深度优先搜索（IDS）

核心原理

• 扩展方式：循环执行DLS，逐次增加深度限制 L=0,1,2,…。

• 结合优势：继承DFS的低内存和BFS的最优性。

特点

• 完备性：在有限状态空间中完备。

• 最优性：在无权图中保证最少步数解。

• 时间复杂度：O(bd)，b为分支因子，d为解深度（与BFS相同）。

• 空间复杂度：O(d)。

适用场景

• 内存受限但需最优解的场景（如嵌入式系统）。

• 解深度未知的搜索问题（如魔方还原）。

本题应用

在本题中，使用迭代加深深度优先搜索，内存低，完备性强，但是重复扩展节点会导致时间开销增加。

最后给大家附上完整的顺序

Arad,  Arad, Sibiu, Timisoara, Zerind, Arad, Sibiu, Fagaras, Oradea, Rimnicu, Timisoara, Lugoj, Zerind, Oradea, Arad, Sibiu, Fagaras, Bucharest. 

e.总结 

2.有信息搜索

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。

a.贪婪最佳优先搜索

核心原理

• 扩展顺序：优先扩展启发式值 h(n)（到目标的估计距离）最小的节点。

• 数据结构：优先级队列（按 h(n) 排序）。

• 目标检测：生成或扩展时检查目标。

• 评价函数f(n)=启发函数h(n)

特点

• 完备性：若避免重复状态且状态空间有限，则完备。

• 最优性：不保证最优解（可能陷入局部最优）。

• 时间复杂度：O(bm)，b 为分支因子，m 为最大深度。

• 空间复杂度：O(bm)。

适用场景

• 快速找到可行解，对最优性要求不高。

• 启发式函数高度准确时（如导航中的直线距离）。

本题应用

每次都选择到达目标城市距离最短的城市

在罗马尼亚旅行问题中，贪婪算法可能选择路径：
Arad → Sibiu → Fagaras → Bucharest（成本450），但实际最优路径为 Arad → Sibiu → Rimnicu → Pitesti → Bucharest（成本418）。 

b.A*搜索 

核心原理

• 扩展顺序：综合路径成本 g(n) 和启发式值 h(n)，优先扩展 f(n)=g(n)+h(n) 最小的节点。

• 数据结构：优先级队列（按 f(n)排序）。

• 目标检测：扩展节点时检查目标。

特点

• 完备性：在有限状态空间中完备。

• 最优性：若启发式函数 h(n)h(n) 可采纳（Admissible）（即 h(n)≤h∗(n)），则保证找到最优解。

• 时间复杂度：O((V+E)log⁡V))（优先队列优化）。

• 空间复杂度：O(V)，需存储所有节点的 f(n)。

关键条件

• 可采纳性：启发式函数不超估真实成本（如曼哈顿距离 ≤ 实际路径）。

• 一致性（Consistency）：对任意边 (n,m)(n,m)，满足 h(n)≤c(n,m)+h(m)，确保A*无需重新扩展节点。

适用场景

• 路径规划（如游戏AI、机器人导航）。

• 拼图问题（如八数码、十五数码）。

本题应用

选择时需要考虑起始点据此实际距离和到终点的直接距离两个方面。

就以第一步的拓展为例，Arad到Sibiu，Timisoara，Zerind的实际距离分别是140，118，和75，到终点的直线距离分别是253，329和374，将两者相加可以得出评估函数的值，比较得出Sibiu的值最小，选择到Sibiu，然后继续进行比较，直到到达终点为止。 

c.总结