搜索的方法：按行搜索：即从上到下，逐层搜索。
双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐。
层搜索（从目标状态到中间状态），找到相同的中间状态。
即可。回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回。
到上一层。搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要。
再次加入到树中重新搜索。
12.2 广度优先搜索（bfs）
又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。如果所有节点均被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。
算法过程：1、首先将根结点放入队列中。
2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据：
如果如果是目标结点，则结束算法并返回结果。
如果不是目标结点，则检查它是否已在搜索树**现过，未出现就将它作为尚未检查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。
3、重复步骤2。
4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找。
不到目标”的信息。
算法细化：1、 用哈希数组判断新生成的结点数据是否已出现过。
2、 队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），用于最后输出过程。
3、 如数据规模过大，需要使用循环队列（后果是无法记录父亲）。
算法框架：function creat(i)
begincase i of
1:creat:=按照第一产生式规则生成新状态数据；
2:creat:=按照第二产生式规则生成新状态数据；
end;end;
procedure bfs;
beginjoin(起始状态);
while not(队空) do
begin当前处理状态：=deq;
for i:=第一产生式规则 to 最大产生式规则 do
begin新状态：=creat(i);
if 新状态=目标状态 then
beginprint;
exit;end
else if not(haxi[新状态]) then
beginjoin(新状态);
haxi[新状态]:=true;
end;end;
end;end;
空间复杂度：线性队列：o(最大可能状态数)
循环队列：o(最大可能状态数/2)
时间复杂度：最差情形下，bfs必须寻找所有到可能结点的所有路径。
o(最大可能状态数)
完全性：广度优先搜索算法具有完全性。只要目标存在，则bfs一定会找到。但是，若。
目标不存在，且问题规模为无限大，则bfs将不收敛（不会结束）。
适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。
如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解。
也是最优解。
例一：将一个马从m*n的棋盘的左下角跳到右上角，需要的最少步数是多少？
分析：1、用一个[1..2,1..m*n]的数组作为工作队列，用于存储搜索树。
2、使用m*n的二维哈希数组判重。
3、生成搜索树的同时，记录父节点的序号和新结点的层数。
4、最后从目标结点向起始结点回朔，用一个栈存储回朔的中间状态。
例二：在一个2n+1的一维棋盘上，有n个黑色棋子和n个白色棋子，初始状态如。
图：规定棋子移动规则如下：
1、 如果某棋子的旁边正好为空，这枚棋子可以移动到空位置上。
2、 如果某棋子的一侧有棋子，二那枚棋子的另一侧为空位置，这枚棋子可以跳过那枚棋子到空位置上。
问：最少经过多少步，可以将棋盘状态变成。
分析：1、 用2n+1位三进制数表示状态，如初始状态为：222201111，目标状态。
为111102222。转化为十进制进行存储，另记录空格位置。
2、 产生式规则：将棋子移动转化为空格的移动。
1） 空格向左移动。
2） 空格向右移动。
3） 空格向左跳动。
4） 空格向右跳动。
3、 用一个[1..3^2n+1]的哈希数组判重。
例三：八数码问题。在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在。
其中的格子里，如图１所示。现在要求实现这个问题：将该九宫格调整为如图2
所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一。
个数字平移到空格中。试编程实现这一问题的求解。
图一图二。分析：1、字符串表达状态，另开一变量w记录空格位置。
2、空格移动规则：
1）向下移动：w’=w+3。
2）向上移动：w’=w-3。
3）向左移动：w’=w-1。
4）向右移动：w’=w+1。
3、用穷举法判重。（将来可以用排序二叉树判重）
12.3 深度优先搜索（dfs）
深度优先搜索是从根结点出发，沿着树的深度遍历树的结点。如果当前新产生的结点还有以此为根的下一层结点，则沿此路继续下去，直到无法再深入访问时，回朔到上一层的结点，选另一条路继续深入访问。反复此过程，直到所有结点都被访问到为止。
算法过程：1、 首先将根结点放入栈中。
2、 取出栈顶结点，按照产生式规则生成新的结点数据，每产生一个：
检查是否是目标结点，如果是且比保存的数据更优，刷新所保存的数据。
检查该结点是否已搜过，如果是且比已保存的数据更优，则刷新所保存的数据，然后该结点进栈；如没有搜过，则保存数据并进栈。
3、 转第二步。
4、 如果栈空，则算法结束。
细化说明：1、 一般用回朔法，利用递归使用系统栈。
2、 哈希数组不仅用于判断新结点是否出现过，还用于保存到达该结点时的中间数据。
算法框架：procedure dfs(结点数据);
var i:integer;
beginfor i:=产生式规则一 to 最大产生式规则 do
begin新结点数据：=creat(i);
if (新结点数据没有搜到过)or(新结点数据虽已搜过但本次搜索结果更优)
then begin
更新新结点搜索结果；
dfs(新结点数据);
end;end;
procedure dfs(结点数据);
var i:longint;
beginfor i:=1 to 最大产生式规则 do
begin新结点：=creat(i);
if 新结点是目标结点 then
begin传回新结点；
t:=true;
exit;end;
if 新结点更优 then
begin更新新结点数据；
dfs(新结点);
if t then exit;
end;end;
end;空间复杂度：o(最大状态数) （主要用于存储各结点搜索结果）
时间复杂度：o(最大产生式规则数^最大状态数)
深度优先搜索的理论依据是建立在穷举基础上的，所以时间是几何级数级的，其优化剪枝是非常必要的，因此，深搜的主要算法设计是在于如何剪枝，如何既高效地抛弃不必要的子树，又不至于将最优解剪掉，将是深搜的最大难点。
适用范围：在缺乏有效的数学方法、递推算法，不符合动态规划要求，也没有专用算法。
可以应对，一般考虑使用深搜；得分情况将取决于优化剪枝的技巧（30-100
分）。例一：有a、b、c、d、e 5本书，要分给张、王、刘、赵、钱5位同学，每人只能选1本。
每个人都将自己喜爱的书填写在下表中。请你设计一个程序，打印出让每个人都满意的所有分书方案。
│ 张0 0 1 1 0
│ 王1 1 0 0 1
│ 刘0 1 1 0 0
│ 赵0 0 0 1 0
│ 钱0 1 0 0 1
分析：1、朴素的穷举法：产生5本书的所有全排列，共有5！=120个，逐个检查各种排列是否。
符合所有人的要求，符合则输出，否则丢弃。