| 查看: 1381 | 回复: 9 | |||
| 当前主题已经存档。 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
gggwww荣誉版主 (著名写手)
|
[交流]
何谓启发式搜索算法
|
||
|
何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。 [ Last edited by 幻影无痕 on 2006-10-30 at 08:02 ] |
回复此楼» 猜你喜欢
考研复试调剂，过国家线的同学都可报名
已经有5人回复
-
085600 英一数二272求调剂
已经有13人回复
-
理学，工学，农学调剂，少走弯路，这里欢迎您！
已经有5人回复
-
接收调剂
已经有7人回复
-
一志愿华南理工大学材料与化工326分，求调剂
已经有3人回复
-
290求调剂
已经有5人回复
-
清华大学 材料与化工 353分求调剂
已经有4人回复
-
材料284求调剂，一志愿郑州大学英一数二专硕
已经有12人回复
-
化学，材料，环境类求调剂
已经有3人回复
-
材料化工调剂
已经有14人回复
小狗
荣誉版主 (知名作家)
我是妖人，我怕人妖
- 应助: 0 (幼儿园)
- 贵宾: 1.8
- 金币: 2394.6
- 红花: 5
- 帖子: 5815
- 在线: 9.5小时
- 虫号: 152837
- 注册: 2006-01-02
- 性别: GG
- 专业: 可再生与替代能源利用中的
8楼2006-01-26 11:51:00
yuefour
金虫 (正式写手)
- 应助: 0 (幼儿园)
- 贵宾: 9.5
- 金币: 1310.7
- 帖子: 838
- 在线: 17小时
- 虫号: 64621
- 注册: 2005-04-16
- 性别: GG
- 专业: 中医内科
2楼2005-06-03 12:09:59
3楼2005-06-09 17:53:17
启发式搜索算法（解题）最早是由G.波利亚提出，其主要针对数学题的解题及方法（前提为有解存在）。而现代启发式搜索算法要解决的问题，其解的存在往往呈现不确定性，亦或问题（或问题内部）的初始与目标系统看起来是明显矛盾的。对于后一种情况，h(n)<4楼2006-01-16 13:41:49
