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