广度优先搜索（图7-8）尝试在不重复访问状态的情况下，寻找到一条最短路径。广度优先搜索保证如果存在一条到目标状态的路径，那么找到的肯定是最短路径。
图 7-8 广度优先搜索详解事实上，深度优先搜索和广度优先搜索的唯一不同就是广度优先搜索使用队列来保存开放集，而深度优先搜索使用栈。每次迭代时，广度优先搜索从队列头拿出一个未访问的状态，然后从这个状态开始，计算后继状态。如果达到了目标状态，那么搜索结束。任何已经在闭合集中的后继状态将会被抛弃。剩余的未访问棋面状态将会放入开放集队列尾部，然后继续搜索。
使用如下状态作为八数码游戏的初始状态：
图7-9是计算出的搜索树，我们可以看到算法是如何在搜索所有4步长的路径之后，找到了一个5步长路径的解（几乎所有5步长的路径都被探测过）。图中20个灰黑色的棋面状态是在开放集中等待被搜索的。总共处理了25个棋面状态。
图 7-9 八数码问题的广度优先搜索树输入/输出
输入
算法从一个初始棋面状态开始，寻找一个目标状态。算法假设在给定棋面状态下可以尝试所有的可行走法。
输出
返回一个走法的序列，表示从初始状态到目标状态的开销最小的路径（或者只是输出是否存在一个解）。