通过搜索进行问题求解

小咪咪 2023-06-12 08:35 126阅读 0赞

要进行问题求解，首先要讨论的是对问题及其解的精确定义。然后我们介绍一些求解此类问题的通用的搜索算法。  
首先讨论**无信息的**（uninformed）搜索算法-----无信息是指除了问题定义本身没有任何其他信息。尽管这些算法可以求解任何问题，但此类算法效率都不好。另一方面，有信息的搜索算法，利用给定的知识引导能够更有效地找到解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70]

## 贪婪最佳优先搜索 ##

**贪婪最佳优先搜索**（greedy best-first search）试图扩展离目标最近的结点，理由是这样可能可以很快找到解。因此，他只用启发式信息，即f(n) = h(n)。  
将此算法应用在罗马尼亚问题中；使用**直线距离**启发式，记 为 h S L D h\_\{SLD\} hSLD，如果目的地是Bucharest，我们需要知道到达Bucharest的直线距离，如下图所示。如 h S L D ( I n ( A r a d ) ) = 366 h\_\{SLD\}(In(Arad ))=366 hSLD(In(Arad))=366，要注意的是 h S L D h\_\{SLD\} hSLD不是有问题本身描述计算得到的。而且，有经验可知， h S L D h\_\{SLD\} hSLD和实际路程相关，因此这是一个有用的启发式。

<table> 
 <thead> 
  <tr> 
   <th>Arad</th> 
   <th>366</th> 
   <th>Mehadia</th> 
   <th>241</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Bucharest</td> 
   <td>0</td> 
   <td>Neamt</td> 
   <td>234</td> 
  </tr> 
  <tr> 
   <td>Craiov</td> 
   <td>160</td> 
   <td>Orade</td> 
   <td>380</td> 
  </tr> 
  <tr> 
   <td>Drobeta</td> 
   <td>242</td> 
   <td>Pitesti</td> 
   <td>100</td> 
  </tr> 
  <tr> 
   <td>Eforie</td> 
   <td>161</td> 
   <td>Rimnicu Vilcea</td> 
   <td>193</td> 
  </tr> 
  <tr> 
   <td>Fagaras</td> 
   <td>176</td> 
   <td>Sibiu</td> 
   <td>253</td> 
  </tr> 
  <tr> 
   <td>Giurgiu</td> 
   <td>77</td> 
   <td>Timisoara</td> 
   <td>329</td> 
  </tr> 
  <tr> 
   <td>Hirsova</td> 
   <td>151</td> 
   <td>Urziceni</td> 
   <td>80</td> 
  </tr> 
  <tr> 
   <td>lasi</td> 
   <td>226</td> 
   <td>Vaslui</td> 
   <td>199</td> 
  </tr> 
  <tr> 
   <td>Lugoj</td> 
   <td>244</td> 
   <td>Zerind</td> 
   <td>374</td> 
  </tr> 
 </tbody> 
</table>

图 3.2 图3.2 图3.2  
图3.23给出了使用 h S L D h\_\{SLD\} hSLD的贪婪最佳优先搜索寻找从Arad到 Bucharest的路的过程。从Arad出发最先扩展的结点为 Sibiu,因为与 Zerind和 Timisoara相比,它距离 Bucharest最近。下一个扩展的结点是 Fagaras,因为它是离目标最近的。 Fagaras接下来生成了 Bucharest,也就是目标结点。对于这个特殊问题,使用hsD的贪婪最佳优先搜索在没有扩展任何不在解路径上的结点前就找到了问题的解;所以,它的搜索代价是最小的。然而却不是最优的经过 Sibiu到 Fagaras到 Bucharest I的路径比经过 Rimnicu Vilcea到 Pitesti到 Bucharest的路径要长32公里。这说明了为什么这个算法被称为“贪梦的”一一在每一步它都要试图找到离目标最近的结点。  
贪婪算法之所以叫贪婪算法，是因为他每一步都试图找到离目标点最近的结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 1]

## A\*搜索：缩小总评估代价 ##

最佳优先搜索的最广为人知的形式称为**A\*搜索**，它对结点的评估结合了g(n)，即到达此结点已经花费的代价，和h(n)，从该结点到目标结点所花代价  
 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n) f(n)=g(n)\+h(n)  
由于g(n)是从开始结点到结点n的路径代价，而h(n)是从结点n到目标结点的最小代价路径的估计值，因此  
 f ( n ) = 经 过 结 点 n 的 最 小 代 价 解 的 估 计 值 f(n) = 经过结点n的最小代价解的估计值 f(n)=经过结点n的最小代价解的估计值  
这样，如果我们想找到一个最小代价的解，**首先扩展g(n) + h(n)值得最小的结点是合理的**。可以发现这个策略不仅仅合理:假设启发式函数h(n)满足特定条件，A\* 搜索既是完备的也是最优的。算法与一致代价搜索类似，除了A\*使用g+h而不是g。

**保证最优性的条件：可采纳性和一致性**

保障最优性的第一个条件是h(n)是一个可采纳启发式。可采纳启发式是指它从不会过高估计到达目标的代价。因为g(n)是当前路径到达结点n的实际代价,而f(n)=g(n)+h(n)，我们可以得到直接结论:f(n)永远不会超过经过结点n的解的实际代价。可采纳的启发式自然是乐观的，因为*它们认为解决问题所花代价比实际代价小*。可采纳启发式的明显例子就是用来寻找到达 Bucharest的路径的直线距离 h S L D h\_\{SLD\} hSLD。直线距离是可采纳的启发式，因为两点之间直线最短，所以用直线距离肯定不会高估。图3.24给出了通过A\*树搜索求解到达 Bucharest的过程。g值从图3.2给出的单步代价计算得到, h L S D h\_\{LSD\} hLSD值在图3.22中给出。

特别要注意的是, Bucharest首次在步骤(e)的边缘结点集里出现,但是并没有被选中扩展,因为它的f值(450)比 Pitesti的f值(417)高。换个说法就是可能有个经过 Pitesti的解的代价低至417,所以算法将不会满足于代价为450的解。

第二个条件,略强于第一个的条件被称为一致性(有时也称为单调性)，只作用于在图搜索中使用A\*算法。我们称启发式h（n）是一致的，

如果对于每个结点n和通过任一行动a生成的n的每个后继结点n，从结点n到达目标的估计代价不大于从n到n的单步代价与从n到达目标的估计代价之和:h(n)≤c(n,a,n’)+(n)这是一般的三角不等式,它保证了三角形中任何一条边的长度不大于另两条边之和。这里,三角形是由n,n’和离n最近的目标结点Gn构成的。对于可采纳的启发式,这种不等式有明确意义:如果从n经过n’到Gn比An)代价小,就违反了加(n)的性质:它是到达Gn的下界。很容易证明一致的启发式都是可采纳的。虽然一致性的要求比可采纳性更严格,要找到满足可采纳性的但可能不一致的启发式仍然需要艰苦的工作。本章中我们讨论的可采纳的启发式都是一致的。例如,考虑hsD。我们知道当每边都用直线距离来度量时是满足一般的三角不等式的，而且 n n n和 n ′ n^\{'\} n′之间的直线距离不超过 c ( n , a , n ′ c(n,a,n^\{'\} c(n,a,n′)，因此， h S L D h\_\{SLD\} hSLD是一致的启发式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 4]

参考资料：《人工智能：一种现代的方法（第三版）》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70]: /images/20230531/a8e037246a2d45eb9411b678a6d4110c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 1]: /images/20230531/67a4c54c73b24b7eb279963f471a6b30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 2]: /images/20230531/84cb826939e54c5dafd615586d5429e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 3]: /images/20230531/72c61d9f73cf4fefafc2aa0d072d98ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70 4]: /images/20230531/5436a0bfe0c54e039af00d70685cc210.png