论坛网站如何建设,一个域名怎么做网站,东莞哪里的网站建设效果好,兄弟们拿走不谢文章目录 局部搜索算法内存限制局部搜索算法示例#xff1a;n-皇后爬山算法随机重启爬山模拟退火算法局部剪枝搜索遗传算法小结 局部搜索算法 在某些规模太大的问题状态空间内#xff0c;A*往往不够用 问题空间太大了无法访问 f 小于最优的所有状态通常#xff0c;甚至无法储… 文章目录 局部搜索算法内存限制局部搜索算法示例n-皇后爬山算法随机重启爬山模拟退火算法局部剪枝搜索遗传算法小结 局部搜索算法 在某些规模太大的问题状态空间内A*往往不够用 问题空间太大了无法访问 f 小于最优的所有状态通常甚至无法储存整个边缘队列 解决方案 设计选择更好的启发式函数Greedy hill-climbing (fringe size 1)Beam search (limited fringe size)
内存限制
瓶颈内存不足无法存储整个边缘队列爬山搜索 只有“最佳”节点保留在周围没有边缘队列通常按h优先选择继任者贪婪的爬山与贪婪的回溯相比它仍然有边缘队列 剪枝搜索有限内存搜索 介于两者之间保持边缘中的K个节点根据需要转储优先级最低的节点可以单独按h贪婪剪枝搜索或hg有限内存A*进行优先级排序
局部搜索算法
在许多优化问题中通往目标的路径是不相关的目标状态本身就是解决方案状态空间“完整”配置集(完全状态 查找满足约束的配置例如n皇后 在这种情况下我们可以使用本地搜索算法保持一个单一的“当前”状态尝试改善它 直到你无法让它变得更好 恒定空间适合在线和离线搜索通常效率更高但不完备
示例n-皇后
将n个皇后区放在n×n板上同一行、同一列或同一对角线上没有两个皇后区#
爬山算法
简单、概括的想法 从任何地方开始总是选择最好的邻居如果没有邻居的分数比当前分数高退出 这在理论上效果很糟糕因为他不具有完备性(算法不会陷入死循环即一定能结束)也不保证得到最优解问题根据初始状态可能会陷入局部最大值 随机重新开始爬山算法一定程度克服了局部最大值随机侧向移动逃离肩膀但可能在最大值处循环
随机重启爬山 非常简单的修改 当被卡住时随机选择一个新的启动状态然后从那里重新运行爬山重复此操作k次返回k个局部最优值中的最佳值 可以做到非常高效 每当使用爬山时都应该尝试 快速、易于实施对于解决方案空间表面不太“颠簸”即不太多局部最大值的许多应用来说效果很好 仍然以8皇后问题为例 h直接或间接相互攻击的成对皇后数量对于上述状态h17一个局部最优解如下h1
模拟退火算法 思想: 通过允许一些“坏”动作但逐渐降低其频率来逃避局部最大值 可以证明如果T下降得足够慢那么模拟退火搜索将找到概率接近1的全局最优 广泛应用于超大规模集成电路布局、航空公司调度等
局部剪枝搜索
跟踪k个状态而不仅仅是一个。从k个随机生成的状态开始。在每次迭代时生成所有k个状态的所有后续状态。如果任何一个是目标状态则停止否则从完整列表中选择k个最佳继任者然后重复。像贪婪搜索一样但始终保持K状态多种实用设置中的最佳选择与并行运行的k个搜索不同找到好状态的搜索会招募其他搜索加入他们变量分支大小鼓励多样性问题通常情况下所有k个状态最终都在同一个局部山丘上思想随机选择k个继任者偏向于优秀的继任者
遗传算法
遗传算法使用自然选择隐喻通过组合两个父状态生成后续状态从k个随机生成的状态开始总体种群)状态表示为有限字母表上的字符串通常是0和1的字符串评价函数适应度函数适应度函数). 值越高状态越好。通过选择、交叉和突变产生下一代状态(选择杂交变异示例每个状态由8个数字表示按照概率随机选择两对交叉适应度就是互不攻击的皇后对数概率就是适应度的占比
小结
局部搜索算法——通往目标的路径是不相关的目标状态本身就是解决方案保持单一的“当前”状态并尝试改进它登山搜索 根据初始状态可能会陷入局部最大值 模拟退火搜索 通过允许一些“坏”的移动来逃避局部最大值但逐渐降低其频率 局部剪枝搜索 跟踪k个状态而不仅仅是一个 好的启发式搜索能大大提高搜索性能但由于启发式搜索需要抽取与问题本身有关的特征信息而这种特征信息的抽取有时会比较困难因此盲目搜索仍不失为一种有用的搜索策略好的搜索策略应该 引起运动—避免原地踏步系统—避免兜圈运用启发函数—缓解组合爆炸 搜索树 vs 搜索图 搜索树结点有重复但登记过程简单搜索图结点无重复但登记过程复杂每次都要查重省空间费时间。
