在上面确定h(x)时，尽管并不知道h*(x)具体为多少，但当采用单位代价时，通过对不在目标状态中相应位置的数码个数的估计，可以得出至少需要移动h(x)步才能够到达目标，显然h(x)≤h*(x)。因此它满足A*算法的要求。
最优搜索路径: 如图粗线所示。 (2) 此时8数码搜索图可表示为：
这时，显然有h(x)≤p(x)≤h*(n)，相应的搜索过程也是A*算法。然而，p(x)比h(n)有更强的启发式信息，由w(x)=p(x)构造的启发式搜索树，比w(x)=h(x)构造的启发式搜索树节点数要少。
（3）若w(x)=0，该问题就变为宽度优先搜索问题。
3.9 如图3.3所示，是5个城市之间的交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中的数字，求从A到E的最小费用交通路线。
5
4 A 3 4 B 5 2 3 D C E
图3.3 旅行交通图
本题是考察代价树搜索的基本概念，了解这种搜索方法与深度优先和宽度优先的不同。首先将旅行交通图转换为代价树如图3.4所示。
图3.4 交通图的代价树
(1) 如果一个节点已经成为某各节点的前驱节点，则它就不能再作为该节点的后继节点。例如节点B相邻的节点有A和D，但由于在代价树中，A已经作为B的前驱节点出现，则它就不再作为B的后继节点。
(2) 除了初始节点A外，其它节点都有可能在代价树中多次出现，为了区分它们的多次出现，分别用下标1、2、3…标出，但它们都是图中同一节点。例如C1和C2都代表图中节点C。
对上面所示的代价树做宽度优先搜索，可得到最优解为：
A→C1→D1→E2
代价为8。由此可见，从A城市到E城市的最小费用路线为：
A→C→D→E
如果采用代价树的深度优先搜索，也会得到同样的结果：
A→C→D→E
但注意：这只是一种巧合，一般情况下，这两种方法得到的结果不一定相同。再者，代价树的深度优先搜索可能进入无穷分支路径，因此也是不完备的。
3.10 对于图3.4所示的状态空间图，假设U是目标状态，试给出宽度优先搜索与深度优搜索的OPEN表和CLOSED表的变化情况。
6
图3.5 状态空间图
[解] 宽度优先搜索的OPEN表和CLOSED表的变化情况：
1. OPEN=[A]; CLOSED=[ ] 2. OPEN=[B,C,D]; CLOSED=[A] 3. OPEN=[C,D,E,F]; CLOSED=[B,A] 4. OPEN=[D,E,F,G,H]; CLOSED=[C,B, A] 5. OPEN=[E,F,G,H,I,J]; CLOSED=[D,C,B, A] 6. OPEN=[F,G,H,I,J,K,L]; CLOSED=[E,D,C,B,A] 7. OPEN=[G,H,I,J,K,L,M]（由于L已在OPEN中）;
CLOSED=[F,E,D,C,B,A] 8. OPEN=[H,I,J,K,L,M,N]; CLOSED=[G,F,E,D,C,B,A] 9. 以此类推，直到找到了U或OPEN=[ ]。 深度优先搜索的