在一个与或图中 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 标记。

以下是使用 AO* 算法求解的搜索图 G，其中每个节点的 q 值已经标明：

               +---------+          
               |    s    |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+----------+   
         |                     |   
    +----+----+           +----+----+
    |    n1   |           |    n2   |
    |  q=2    |           |  q=3    |
    +----+----+           +----+----+
         |                     |    
    +----+----+           +----+----+
    |    n3   |           |    n4   |
    |  q=4    |           |  q=1    |
    +----+----+           +----+----+
         |                /   |   \  
    +----+----+     +----+----+  +----+----+
    |    n6   |     |    n5   |  |    n7   |
    |  q=8    |     |  q=6    |  |  q=1    |
    +----+----+     +----+----+  +----+----+
         |                |         |    
    +----+----+     +----+----+    SOLVED  
    |    n8   |     |    n9   |           
    |  q=0    |     |  q=0    |           
    +----+----+     +----+----+           
         |                |               
         +----------------+               

其中，节点的 q 值等于该节点到终节点的最小距离加上该节点的启发函数 h(n) 的值。在这个例子中，终节点 n8、n9、n10 的启发函数 h 值为 0，所以它们的 q 值等于它们到自己的距离（即 0），而其他节点的 q 值等于它们到终节点的最小距离加上它们的启发函数 h 值。例如，节点 n1 到终节点的最小距离是 1（通过 n4 到达），所以它的 q 值为 1 + 2 = 3。

在 AO* 算法的搜索过程中，我们从起始节点 s 开始，计算每个节点的 q 值，并将它们按照 q 值从小到大排序。然后，我们将 q 值最小的节点（即 s）标记为 SOLVED，并考虑从它出发可以到达的所有未标记节点。对于每个未标记节点，我们计算它的 q 值，并将它们加入到当前搜索图 G 中。然后，我们再次按照 q 值从小到大排序，并重复上述步骤，直到终节点全部被标记为 SOLVED。在每个搜索图中，已经被标记为 SOLVED 的节点都不会被再次扩展。

在这个例子中，搜索过程如下：

1. 起始节点 s 的 q 值最小，所以将它标记为 SOLVED。从 s 出发可以到达 n1 和 n2，计算它们的 q 值并加入搜索图 G 中。

               +---------+          
               | SOLVED  |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+----------+   
         |                     |   
    +----+----+           +----+----+
    |    n1   |           |    n2   |
    |  q=2    |           |  q=3    |
    +----+----+           +----+----+

2. 按照 q 值从小到大排序，n1 的 q 值最小，所以将它标记为 SOLVED。从 n1 出发可以到达 n3 和 n4，计算它们的 q 值并加入搜索图 G 中。

               +---------+          
               | SOLVED  |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+----------+   
         |            |          |   
    +----+----+  +----+----+  +----+----+
    | SOLVED  |  |    n2   |  |    n4   |
    |  q=2    |  |  q=3    |  |  q=2    |
    +----+----+  +----+----+  +----+----+
         |                /   |       
    +----+----+     +----+----+      
    |    n6   |     |    n5   |      
    |  q=8    |     |  q=6    |      
    +----+----+     +----+----+      
         |                |         
    +----+----+          |         
    |    n8   |          |         
    |  q=9    |          |         
    +----+----+          |         
                         |         
                      SOLVED      
                      (n1)         

3. 按照 q 值从小到大排序，n4 的 q 值最小，所以将它标记为 SOLVED。从 n4 出发可以到达 n5、n7 和 n2，计算它们的 q 值并加入搜索图 G 中。

               +---------+          
               | SOLVED  |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+          |   
         |                      |   
    +----+----+           +----+----+
    | SOLVED  |           |    n2   |
    |  q=2    |           |  q=3    |
    +----+----+           +----+----+
         |                 /   |       
    +----+----+      +----+----+      
    |    n6   |      | SOLVED  |      
    |  q=8    |      |  q=5    |      
    +----+----+      +----+----+      
         |                |         
    +----+----+     +----+----+      
    |    n8   |     |    n5   |      
    |  q=9    |     |  q=6    |      
    +----+----+     +----+----+      
         |                |         
         |             SOLVED      
         |             (n4)         
         |                          
      +----+----+                   
      |    n7   |                   
      |  q=2    |                   
      +----+----+                   

4. 按照 q 值从小到大排序，n5 和 n2 的 q 值相同，可以任选一个进行扩展。这里选择 n5。从 n5 出发可以到达 n7、n9 和 n10，计算它们的 q 值并加入搜索图 G 中。

               +---------+          
               | SOLVED  |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+          |   
         |                      |   
    +----+----+           +----+----+
    | SOLVED  |           | SOLVED  |
    |  q=2    |           |  q=3    |
    +----+----+           +----+----+
         |                 /   | \    
    +----+----+      +----+----+  +----+----+
    |    n6   |      | SOLVED  |  |    n7   |
    |  q=8    |      |  q=5    |  |  q=2    |
    +----+----+      +----+----+  +----+----+
         |                |         |    
    +----+----+     +----+----+    SOLVED  
    |    n8   |     | SOLVED  |     (n5)  
    |  q=9    |     |  q=6    |           
    +----+----+     +----+----+           
         |                |               
         |             SOLVED             
         |             (n4)                
         |                               
      +----+----+                        
      |    n7   |                        
      |  q=2    |                        
      +----+----+                        

5. 按照 q 值从小到大排序，n7 的 q 值最小，所以将它标记为 SOLVED。从 n7 出发可以到达 n9 和 n10，计算它们的 q 值并加入搜索图 G 中。

               +---------+          
               | SOLVED  |          
               |  q=3    |          
               +----+----+          
                    |               
         +----------+          |   
         |                      |   
    +----+----+           +----+----+
    | SOLVED  |           | SOLVED  |
    |  q=2    |           |  q=3    |
    +----+----+           +----+----+
         |                 /   |      
    +----+----+      +----+----+     
    |    n6   |      | SOLVED  |     
    |  q=8    |      |  q=5    |     
    +----+----+      +----+----+     
         |                |        
    +----+----+     +----+----+    
    |    n8   |     | SOLVED  |    
    |  q=9    |     |  q=6    |    
    +----+----+     +----+----+    
         |                |       
         |             SOLVED     
         |             (n5)       
         |                       
      +----+----+                
      | SOLVED  |                
      |  q=3    |                
      +----+----+                

6. 终节点 n8、n9、n10 都已经被标记为 SOLVED，搜索结束。最短路径为 s -> n2 -> n4 -> n7 -> n9、s -> n1 -> n4 -> n7 -> n9、s -> n1 -> n4 -> n7 -> n10，长度均为 8。