图的路径搜索算法

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

本题要求我们找到从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这条路径能顺利到达目的地并且此时的路径最短，我们选择了它。