注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

启发式搜索和盲目式搜索  

2011-01-04 21:40:16|  分类: 人工智能 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

        启发式搜索在搜索过程中利用与问题有关的信息来引导搜索,搜索空间小,搜索速度快。

       启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。

      在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。

  启发中的估价是用估价函数表示的,如:最佳优先搜索的最广为人知的形式称为A*搜索(发音为“A星搜索”).它把到达节点的耗散g(n) 和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:f(n)=g(n)+h(n)

  因为以g(n)给出了从起始节点到节点n的路径耗散,而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值,因此f(n)=经过节点n的最低耗散解的估计耗散.这样,如果我们想要找到最低耗散解,首先尝试找到g(n)+h(n)值最小的节点是合理的。可以发现这个策略不只是合理的:倘若启发函数h(n)满足一定的条件,A*搜索既是完备的也是最优的。

  如果把A*搜索用于Tree-Search,它的最优性是能够直接分折的。在这种情况下,如果h(n)是一个可采纳启发式--也就是说,倘若h(n)从不会过高估计到达目标的耗散--A*算法是最优的。可采纳启发式天生是最优的,因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散,我们得到一个直接的结论:f(n)永远不会高估经过节点n的解的实际耗散.

    盲目搜索又叫做无信息搜索,在搜索过程中不利用与问题有关的信息来引导搜索,搜索空间大,搜索速度慢。

    盲目搜索方法主要有宽度优先搜索和深度优先搜索

 

http://wenku.baidu.com/view/d5d48c6eb84ae45c3b358cc1.html

  评论这张
 
阅读(1172)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017