启发式搜索

DNA图谱 / 问答 / 标签

什么是启发式搜索?并以八数码难题为例,说明其原理

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。   启发中的估价是用估价函数表示的,如:   最佳优先搜索的最广为人知的形式称为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的解的实际耗散.   启发算法有: 蚁群算法,遗传算法、模拟退火算法等   蚁群算法是一种来自大自然的随机搜索寻优方法,是生物界的群体启发式行为,现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统,隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看,它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。

什么是启发式搜索?并以八数码难题为例,说明其原理

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。  启发中的估价是用估价函数表示的,如:  最佳优先搜索的最广为人知的形式称为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的解的实际耗散.  启发算法有:蚁群算法,遗传算法、模拟退火算法等  蚁群算法是一种来自大自然的随机搜索寻优方法,是生物界的群体启发式行为,现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统,隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看,它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。