Local search algorithms (局部搜索算法)
局部搜索算法内存限制局部搜索算法示例:n-皇后爬山算法随机重启爬山模拟退火算法局部剪枝搜索遗传算法小结局部搜索算法
在某些规模太大的问题状态空间内,A*往往不够用
问题空间太大了无法访问 f 小于最优的所有状态通常,甚至无法储存整个边缘队列
解决方案
设计选择更好的启发式函数Greedy hill-climbing (fringe size = 1)Beam search (limited fringe size)
内存限制
瓶颈:内存不足,无法存储整个边缘队列爬山搜索: 只有“最佳”节点保留在周围,没有边缘队列通常按h优先选择继任者(贪婪的爬山)与贪婪的回溯相比,它仍然有边缘队列 剪枝搜索(有限内存搜索) 介于两者之间:保持边缘中的K个节点根据需要转储优先级最低的节点可以单独按h(贪婪剪枝搜索)或h+g(有限内存A*)进行优先级排序局部搜索算法
在许多优化问题中,通往目标的路径是不相关的;目标状态本身就是解决方案状态空间=“完整”配置集(完全状态) 查找满足约束的配置,例如n皇后 在这种情况下,我们可以使用本地搜索算法保持一个单一的“当前”状态,尝试改善它 直到你无法让它变得更好 恒定空间,适合在线和离线搜索通常效率更高(但不完备)示例:n-皇后
将n个皇后区放在n×n板上,同一行、同一列或同一对角线上没有两个皇后区#爬山算法
简单、概括的想法: 从任何地方开始总是选择最好的邻居如果没有邻居的分数比当前分数高,退出 这在理论上效果很糟糕,因为他不具有完备性(算法不会陷入死循环,即一定能结束)也不保证得到最优解问题:根据初始状态,可能会陷入局部最大值 随机重新开始爬山算法一定程度克服了局部最大值随机侧向移动逃离肩膀但可能在最大值处循环随机重启爬山
非常简单的修改:
当被卡住时,随机选择一个新的启动状态,然后从那里重新运行爬山重复此操作k次返回k个局部最优值中的最佳值
可以做到非常高效
每当使用爬山时都应该尝试
快速、易于实施;对于解决方案空间表面不太“颠簸”(即不太多局部最大值)的许多应用来说,效果很好
仍然以8皇后问题为例:
h=直接或间接相互攻击的成对皇后数量对于上述状态,h=17一个局部最优解如下:h=1
模拟退火算法
思想: 通过允许一些“坏”动作,但逐渐降低其频率,来逃避局部最大值
可以证明:如果T下降得足够慢,那么模拟退火搜索将找到概率接近1的全局最优
广泛应用于超大规模集成电路布局、航空公司调度等