算法-图搜索
概述
图搜索 最初用于遍历图内节点，现在往往用于最优解搜索等问题。
我们在此介绍五种搜索算法 —— DFS (深度优先搜索) 、BFS (广度优先搜索)、IDDFS (迭代深化深度优先搜索)、A*、IDA*。
我们在此仅讨论搜索算法用于求解最优解搜索问题。随后在可行解内找具有最小代价的最优解。
DFS
DFS 属于盲目搜索，它会遍历解空间中所有解，故而其也是一种暴力搜索。
当用其解决最优解搜索问题时，首先需要找到解空间内所有可行解，随后在可行解内找具有最小代价的最优解。
BFS
BFS 属于有目的搜索，它会按层次搜索解空间中的解。
当用其解决最优解搜索问题时，只要搜索到解，那么该解一定是最优解。
最优解搜索问题中有一类称为最短路径搜索。该问题用于查找图中两点间最短路径。
如果图中任意两点间边代价相同，则从起点开始，BFS 动态搜索止点，一旦搜索到止点，其搜索路径就是最短路径。
IDDFS
对于 DFS 而言，深度越深，递归层级越高，此时容易栈溢出；对于 BFS 而言，广度越广，队列所需空间越大，此时容易内存溢出。当需要寻找最优解时，由于 DFS 往往需要遍历解空间，故而使得其时间复杂度过高。
实际中，内存溢出远比栈溢出容易 (深度越深，大概率意味着广度越广)。为在内存空间有限条件下快速搜索最优解，IDDFS (迭代深化深度优先搜索，即带有深度限制地深度优先搜索) 被提出，它借助于 DFS 以模拟 BFS，从而达到搜索效率和内存空间两不误。
我们简单描述其过程如下：
- 初始化深度限制为 1，使用 DFS 搜索最优解。
- 如果 DFS 搜索得到最优解或者深度限制已达最大深度限制，则退出循环，否则设置深度限制为当前深度限制加一，重新进行 DFS 搜索最优解。
深度加一，解空间应当呈指数增加，之前搜索部分的时间复杂度便可忽略不计，故而 IDDFS 的时间复杂度主要由最优解所在深度那层深搜决定；BFS 同样需要搜索到最优解所在深度，但是由于它一次搜索到位，故而其时间复杂度仅略好于 IDDFS 。
这里简单说明一下 IDDFS 的适用场景：深度未知、广度很大、同时最优解深度又比较低。
A*
当进行最短路径搜索时，BFS 会将当前搜索点的所有未搜索邻居点加入至队列 (简称为扩展当前搜索点)，然后按序取出队列内容进行扩展，这种扩展方式略显愚笨。
按照人们直观理解来看，我们应当优先扩展距离目标点更近地搜索点。那么这种搜索算法就称为 最佳优先搜索。
最佳优先搜索问题在于：没有考虑搜索点到起始点情况。在 A* 中，它优先扩展具有最小代价值 (该代价值与起始点和目标点均相关) 的搜索点，其中代价值基于启发函数确定。
在 A* 算法中，启发函数表示为 $f(x) = g(x) + h(x)$，其中 $g(x)$ 指代起始点至当前节点的所需代价，$h(x)$ 指代当前节点至目标点的预估代价。
$g(x)$ 在搜索过程中可以得到，而 $h(x)$ 通常需要精心设计。我们在此列举 $h(x)$ 的常见形式：
- 如果图中搜索节点时仅允许上下左右探索，则其应为曼哈顿距离。
- 如果图中搜索节点时仅允许八方向 (即上、下、左、右、左上、右上、左下、右下) 探索，则其应为对角距离。
- 如果图中搜索节点时允许任意方向移动，则其应为欧几里得距离。
IDA*
A* 算法等价于 BFS + 启发函数，IDA* 则等价于 IDDFS + 启发函数。
在 IDA* 中，启发函数可用于两处：1. 根据启发函数动态增加深度，而非每次加一。2. 根据启发函数判断当前解情况下是否需要继续进行深度优先搜索。
我们在此简单介绍一些避免无效搜索地操作：
记忆化搜索
如果搜索过程发生重复搜索，我们可以现行保存搜索结果，随后直接使用搜索结果替代搜索。
可行性剪枝
如果当前解已经无法满足要求，则无需再进行搜索。
最优性剪枝
如果当前解比已知最优解更差，则无需再进行搜索。