在一个与或图中 s 为起始节点,n8、n9、n10为终节点。s连接n1、n2,n1连接n3、n4,n2连接n4、n5,n3连接n6、n8,n6连接n8,n7连接n4、n5、n9、n10。各节点的启发函数 h ( n )的值为:h(s)=3,h(n1)=2,h(n2)=3,h(n3)=4,h(n4)=1,h(n5)=6,h(n6)=8,h(n7)=1,h(n8)=h(n9)=h(n10)=0。设每条边的耗散值为1,试画出用 AO 算法求解该问题时每一步的搜索图 G ,并在其中标明每个节点的 q 值(或 h ( s , n )值),有标记的连接符和 SOLVED 标记。(写出步骤)
时间: 2024-02-03 07:12:40 浏览: 33
1. 初始时,搜索图 G 中只有起始节点 s,标记 SOLVED 的节点为空。
```
G: s(q=3)
SOLVED: {}
```
2. 扩展节点 s,生成子节点 n1 和 n2,并计算它们的 q 值。
```
G: s(q=3) - n1(q=5), n2(q=6)
SOLVED: {s}
```
3. 选择 q 值最小的节点 n1,扩展它,生成子节点 n3 和 n4,并计算它们的 q 值。
```
G: s(q=3) - n1(q=5) - n3(q=9), n4(q=6), n2(q=6)
SOLVED: {s, n1}
```
4. 选择 q 值最小的节点 n4,扩展它,生成子节点 n5 和 n7,并计算它们的 q 值。
```
G: s(q=3) - n1(q=5) - n3(q=9), n4(q=6) - n5(q=12), n7(q=7), n2(q=6)
SOLVED: {s, n1, n4}
```
5. 选择 q 值最小的节点 n7,扩展它,生成子节点 n9 和 n10,并计算它们的 q 值。
```
G: s(q=3) - n1(q=5) - n3(q=9), n4(q=6) - n5(q=12), n7(q=7) - n9(q=8), n10(q=1), n2(q=6)
SOLVED: {s, n1, n4, n7}
```
6. 选择 q 值最小的节点 n10,扩展它,生成子节点 n8,并计算它的 q 值。
```
G: s(q=3) - n1(q=5) - n3(q=9), n4(q=6) - n5(q=12), n7(q=7) - n9(q=8), n10(q=1) - n8(q=0), n2(q=6)
SOLVED: {s, n1, n4, n7, n10}
```
7. 选择 q 值最小的节点 n8,它是终止节点之一,搜索结束。
```
G: s(q=3) - n1(q=5) - n3(q=9), n4(q=6) - n5(q=12), n7(q=7) - n9(q=8), n10(q=1) - n8(q=0), n2(q=6)
SOLVED: {s, n1, n4, n7, n10, n8}
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)