非完美算法学习.pptx

《非完美算法学习.pptx》由会员分享，可在线阅读，更多相关《非完美算法学习.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、什么是非完美算法？什么是非完美算法？第1页/共35页什么是非完美算法？什么是非完美算法？从字面上理解：不完美的算法用来骗分的算法不是std的算法当然，不仅仅这么简单上面的理解是错误的和片面的第2页/共35页非完美算法的方法非完美算法的方法纯随机爬山法模拟退火遗传算法第3页/共35页纯随机纯随机不考虑题目的任何条件，利用rand函数+模拟来解决问题第4页/共35页例题：例题：click玩游戏看题目第5页/共35页例题：例题：click该怎么做？第6页/共35页第7页/共35页爬山法爬山法纯随机算法的劣势显而易见，它只能适用于极少数的题目，因此我们要在此基础上进行改进，即爬山法（应用很广泛）爬山法

2、：采用一定的方法逐步降低初始状态和目标状态的距离（通常通过随机调整来实现），以达到问题解决的一种方法。第8页/共35页爬山法爬山法爬山法中需要特别注意的是：需要多次随机初始状态，随机生成初始状态的次数和随机调整的次数需要通过实践来把握爬山法一般适用于最优化问题第9页/共35页例题：例题：overlap十分经典的题目这题我们后面会讲第10页/共35页第11页/共35页模拟退火模拟退火模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metro

3、polis准则，粒子在温度T时趋于平衡的概率为E-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。第12页/共35页模拟退火模拟退火很可怕吧？其实就是爬山法。第13页/共35页模拟退火模拟退火1.初始化：初始温度

4、T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L2.对k=1，L做第3至第6步：3.产生新解S4.计算增量t=C(S)-C(S)，其中C(S)为评价函数5.若t0，然后转第2步第14页/共35页第15页/共35页遗传算法遗传算法这是一个更加复杂的算法遗传算法（Genetic Algorithms，以下简称GA）是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。这里不再详细介绍感兴趣的同学可以自己了解第16页/共35页第17页/共35页什么时候该用到随机化？什么时候该用到随机化？消除理论最坏情况没有多项式算法多元函数求最值（可能没有多项式）条件复杂，状态巨大的问题比赛

5、中想不出的做法第18页/共35页消除理论最坏情况消除理论最坏情况经典应用随机化快速排序二叉平衡树treap第19页/共35页没有多项式算法没有多项式算法TSP问题第20页/共35页例题：例题：TSP问题问题设有n个城市，用数码1,n代表。城市i和城市j之间的距离为d(i，j)i,j=1,n找出遍访每个域市恰好一次的一条回路，且其路径总长度为最短。怎么随机？模拟退火！第21页/共35页第22页/共35页条件复杂，状态巨大的问题条件复杂，状态巨大的问题第23页/共35页例题：有道难题现场赛例题：有道难题现场赛 problem D有道农场题目很长，就不写了第24页/共35页例题：有道难题现场赛例题：

6、有道难题现场赛 problem D又该怎么做？第25页/共35页第26页/共35页比赛中想不出的做法比赛中想不出的做法NOI2007追捕盗贼贪心可以拿90分第27页/共35页例题：表达式等价判断例题：表达式等价判断给出一个包含+-*/和未知数x的表达式，判断他们是否等价第28页/共35页第29页/共35页多元函数求最值多元函数求最值领域搜索比如：线性规划单纯性第30页/共35页例题：例题：overlap在平面上放一个圆和一个三角形。圆和三角形重叠的面积随着它们的位置关系改变而改变。求最大重叠面积 第31页/共35页例题：例题：overlap能够解决吗？第32页/共35页第33页/共35页第34页/共35页lqp18_lqp18_31感谢您的观看！第35页/共35页