何谓启发式搜寻算法

在说它之前先提状态空间搜寻。状态空间搜寻，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜寻。

常用的状态空间搜寻有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。

前面说的广度和深度优先搜寻有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜寻了。

启发式搜寻就是在状态空间中的搜寻对每一个搜寻的位置进行评估，得到最好的位置，再从这个位置进行搜寻直到目标。这样可以省略大量无谓的搜寻路径，提高了效率。在启发式搜寻中，对位置的估价是十分重要的。採用了不同的估价可以有不同的效果。

启发中的估价是用估价函式表示的，如：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)，而提高效率。

启发算法有： 蚁群算法，遗传算法、模拟退火算法等 　蚁群算法是一种来自大自然的随机搜寻寻优方法，是生物界的群体启发式行为，现己陆续套用到组合最佳化、人工智慧、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分散式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。