第三篇 计算机是如何找到最优路径的（二）
清华大学计算机系 马少平
第二节：宽度优先搜索算法
艾博士：小明，我们首先从宽度优先算法开始介绍。所谓宽度优先算法，就是选择节点深度最浅的节点优先扩展。
小明：什么是节点深度呢？
艾博士解释说：在搜索图中，第一个节点称作根节点，根节点的深度为0，其他节点的深度为其父节点的深度加1。简单地说，根节点深度为0，根节点的子节点深度为1，再下一层子节点深度为2……
艾博士：小明，你说说看，图3.4中几个节点的深度分别多少？
小明回答说：S是根节点深度为0；A、C、E三个节点均为S的子节点，所以它们的深度均为1；B、F均为E的子节点，节点深度均为2。
艾博士接着说：宽度优先搜索就是从根节点开始，每次选择一个节点深度最浅的节点扩展，直到生成出目标节点为止。
小明问到：艾博士，如果深度最浅的节点存在多个时如何选择呢？
艾博士：这种情况下可以随机选择一个深度最浅的节点进行扩展。
下面我们以图3.2为例介绍如何采用宽度优先搜索求解从起点S到终点T的路径。图3.6给出了该问题的搜索图，其中红圈数字表示节点被扩展的次序，这里假定当深度一样时，排在左边的节点优先扩展。
图3.6 宽度优先搜索求解示意图
该搜索过程首先选择深度最浅的根节点S进行扩展，产生了三个子节点A、C、E；由于这时这三个节点深度都是1，我们根据假定优先扩展左边的节点E，产生节点B、F；这时A、C的节点深度最浅，我们选择C扩展，产生节点D；这时A的深度最浅，扩展后产生节点T。而这时T就是终点节点，搜索结束，得到路径S-A-T。
这个问题比较简单，很快就找到了达到终点也就是目标状态的路径。对于复杂一些的情况，需要继续寻找节点深度最浅的节点扩展，直到找到目标为止。
小明问艾博士：宽度优先搜索如何求解其他问题呢？比如前面提到过的八数码问题。
艾博士：当然可以求解，方法是一样的。对于图3.7所示的八数码问题，图3.8给出了用宽度优先搜索求解该八数码问题的搜索图，其中红圈中的数字表示的是该节点被扩展的次序。
图3.7 八数码问题
图3.8 宽度优先搜索求解八数码问题搜索图
艾博士对照着图3.8给出的八数码问题搜索图说：我们来看看用宽度优先搜索求解八数码问题的搜索过程。开始只有初始节点S，对S进行扩展，生成A、B、C三个子节点。由于A、B、C三个节点的深度是一样的，深度均为1，按照约定选择最左边的节点A扩展，生成D、E、F三个子节点。这时节点B、C的深度最浅，同样选择排在左边的节点B扩展，生成出子节点G。再选择深度最浅的节点C扩展，生成出子节点H。此时深度最浅的节点有D、E、F、G、H等5个节点，深度均为2。同样依次扩展节点D、E、F、G，当扩展到节点G时，其子节点中出现了目标节点，搜索到此结束。通过搜索图，可以得到该八数码问题的解，也就是为达到目标状态将牌的移动方法：将牌2右移，将牌1上移，将牌8左移。
小明听着艾博士的讲解，有些不太明白地问：艾博士，这种方法为什么叫宽度优先搜索呢？
艾博士解释说：小明你看图3.8中所示的节点扩展次序，是沿着“横向”进行的，先优先扩展第一层节点，再扩展第二层、第三层……这就是宽度优先名称的由来。
小明：明白了。那么宽度优先搜索有什么特点呢？
艾博士：宽度优先搜索有一个重要的结论，就是在单位代价下，当问题有解时，可以找到问题的最优解，也就是路径总代价最小的解。
小明：单位代价是什么意思呢？
艾博士：我们先解释一下什么是代价。所谓代价就是父节点到子节点的广义“距离”。比如从路口A到路口B距离多少公里可以是代价，需要用多长时间也是代价，花费多少钱也是代价。而单位代价指的是任何两个父子节点间的代价总是为1。比如在上面的八数码例子中，如果移动一个将牌的代价为1的话，则该问题就是单位代价的。在单位代价下，我们用宽度优先搜索得到的八数码问题的解，就是总代价最小的，也就是将牌的移动次数最少的解。
对于地图上求两个地点间的一条路径，如果认为两个相邻路口的代价为1，则找到的是经过的路口最少的路径。当每个路口都有红绿灯时，实际上就是经过的红绿灯最少的路径。在城市中，寻找一条红绿灯最少的路径也是很有意义的。
小明问：为什么在单位代价下宽度优先搜索得到的就是代价最小的路径呢？
艾博士解释说：如同前面说过的，宽度优先搜索在搜索图上体现的是“横着”走，先扩展深度为1的节点，再扩展深度为2的节点……逐步加深扩展节点的深度。假设从初始节点到目标节点存在不同的路径，通过这些路径到达目标节点的深度也不相同。宽度优先搜索优先选择深度最浅的节点扩展，所以当第一次出现目标节点时，一定是经过这条路径计算的目标节点深度最浅。在单位代价下，节点深度就是初始节点到目标节点的总代价，所以宽度优先搜索可以找到总代价最小的路径。
小明：经您这么一解释就明白了。在单位代价条件下，从初始节点到达一个节点的总代价等于该节点所处的深度，宽度优先搜索算法的思想是选择深度最浅的节点扩展，也就是选择总代价最小的节点优先扩展，所以当第一次遇到目标节点时，一定就找到了到达目标节点的最短路径。
小明读书笔记
宽度优先搜索算法是一种常用的路径搜索算法，其特点是每次选择节点深度最浅的节点优先扩展。当问题是单位代价时，也就是任何相邻节点之间的代价均为1时，可以找到从初始节点到目标节点代价最小的最优路径。
未完待续