一、深度优先搜索 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。 二、 重排九宫问题游戏 在一个3乘3的九宫中有1-8的8个数及一个空格随机摆放在其中的格子里。如下面左图所示。现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式。调整规则是：每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中。试编程实现。 | 2 | 8 | 3 | | 1 | 2 | 3 | - | 1 | | 4 | | 8 | | 4 | | 7 | 6 | 5 | | 7 | 6 | 5 | 深度优先搜索的路径示意图： 　 三、广度优先搜索 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 广度优先搜索路径示意图： 四、航班问题（来自《The Art of Java》) 一位顾客要预定一张从New York到Los Angeles的航班机票，下面是航班线路，请你为顾客找一种购票方案。 航班 距离 New York到Chicago 900英里 Chicago到Denver 1000英里 New York到Toronto 500英里 New York到Denver 1800英里 Toronto到Calgary 1700英里 Toronto到Los Ange