对于如下给定的无向状态空间图,给出如下搜索策略的节点扩展顺序,以及算法返回的最终路径。如果两个节点存在冲突,则按字母顺序解决冲突。s a b c d g (1)深度优先搜索(DFS) (2)广度优先搜索(BFS) (3)一致代价搜索(UCS) (4)考虑以下启发式函数,哪一个是不可容许的,为什么? (5)A*搜索:使用(4)中可容许的启发式函数

先画出状态空间图：

     s
   / | \
  a  b  c
 /     / \
d     g   d

节点扩展顺序和最终路径如下：

1. 深度优先搜索(DFS)

节点扩展顺序：s-a-d-b-g-c-d

最终路径：s-a-d

2. 广度优先搜索(BFS)

节点扩展顺序：s-a-b-c-d-g

最终路径：s-a-d

3. 一致代价搜索(UCS)

节点扩展顺序：s-a-b-c-d-g

最终路径：s-a-d

4. 启发式函数

h(n) 表示从 n 到目标节点的估计代价，h(n) 越小，n 距离目标节点越近。

h1(n)：节点 n 到目标节点的距离，不可容许，因为它会低估剩余代价。

h2(n)：如果 n 是 s、a、b、c 中的一个，则 h2(n) = 0；如果 n 是 d，则 h2(n) = 1；如果 n 是 g，则 h2(n) = 2。

h3(n)：h2(n) 的反函数，可容许。

5. A*搜索

使用 h3(n) 作为启发式函数。

节点扩展顺序：s-a-b-c-d-g

最终路径：s-a-d