但是，如果我们规定一棵解树的代价是该树的总边数（即相邻两结点之间代价设为1）。那么宽度优先搜索不保证找到代价最小的解。
6.4.2 与／或树的深度优先搜索，
这种搜索是要求在一定深度限制内寻找一棵解树，对超过深度要求的结点，不再扩展，并将其标志为不可解结点，并在搜索过程中实行可解标志与不可解标志过程。与／或树深度优先搜索算法如下：
1.起始结点s送open表。
2.若s为叶结点，则成功结束，否则继续。
3.取open表第一个结点，送closed表，并记为n。
4.若结点n深度等于界限，则将n标志为不可解结点，并转10，否则继续。
5.扩展结点n，生成全部后继结点，置于open表前面，置指向n的返回指针；如果n无后继结点，则标志为不可解结点，并转10，否则继续。
6.若有后继结点为叶结点，则将这些叶结点标志为可解结点，并继续，否则转3。
7.实行可解标志过程。
8.若起始结点为可解结点，则算法成功结束，否则，继续下一步。
9.从open表中删去含有可解先辈结点的结点，并转3。
10.实行不可解标志过程。
11.若起始结点为不可解，则失败结束，否则，继续下一步。
12.从open表中删去含有不可解先辈结点的结点。
展开
