近似、随机与局部搜索的相关.pdf

近似、随机与局部搜索近似、随机与局部搜索资料由网上搜集，最终解释权属作者所有近似算法近似算法?许多NP难的问题不能用回溯法有效地解 决?求一个与精确解相差不算太多的近似解?效率比较高近似度近似度?绝对近似度：近似解与最优解不超过某 个常数相对近似度：近似解与最优解不超过某 个比例极少NP难的问题具有绝对近似度装箱问题装箱问题?最先适配法（FF）：把物品放入第一个 能装下的箱子里?最优适配法（BF）：把物品放入最空的 一个箱子里?递减最先适配（FFD）：先将物品从大到 小排序，然后用FF?递减最佳适配（BFD）：先将物品从大 到小排序，然后用BFFF的近似度的近似度?可以把问题转化为每个物品体积在[0, 1] 区间内，箱子容积为1半空的箱子（装的物品体积和=∑Vi?FF(I)/OPT(I)=|M|多机任务调度多机任务调度?给定一个任务集合以及它们的执行所需 时间要在m台机器上执行这些任务，使 得完成时间最短贪心法：每次选择第一台可用的机器?近似度为2-1/m?将任务按照执行时间从大到小排序?近似度为4/3-1/3m平面图的平面图的k中心中心?给定一个平面点集，选择其中k个点使得 其他点到这k个点的最小距离尽可能地小 。

贪心法，每次选择一个离已经选中的点 最远的一个点?近似度为2背包问题背包问题?思路：把所有物品的体积都增加为某个 整数k的倍数，从而可以把体积统一转换 为较小的整数用动态规划求解随机算法随机算法?Las Vegas：总是给出正确的解，或者找 不到解Monte Carlo：总是有解，但不一定正确 随机快速排序随机快速排序?在每次递归时随机选择一个元素和第一 个元素进行交换，然后执行通用的快速 排序算法素数测试素数测试?费马小定理：如果n是素数，那么对于所 有不是n的倍数的整数a，有an-1≡1(mod n)?思路：随机选择多个整数进行检验求求am(mod n)?result := 0;?b := 1;?while m > 0 do?begin?b := (b * a) mod n;?if Odd(m) then result := (result + b) mod n;?m := m div 2;?end;?return result;素数测试算法素数测试算法?随机选择多个整数进行测试，对于通过 测试的数再用完整的素数验证算法进行 验算事实上存在出错概率更小的素数测试算 法字符串匹配字符串匹配?为简化问题，只考虑01串。

基本思想：可以把字符串看成一个整数 一个01串其实就是一个整数的2进制 表 示随机选择一个质数p那么两个01串 A、B相等的必要条件是A≡B(mod p)算法算法?读入01串A、B?假设A长度>B?随机选择素数p?计算X=B mod p、Y=substr(A, 0, len(B)) mod p以及 Z=2len(B)mod p?for 每个起始位置i do?if X=Y then return 当前位置?Y = Y * 2 - Ai* Z + Ai+len(B)?return 找不到任何匹配改进改进?通过选择多个素数同时求模可以减少出 错的概率?每次出现模相等时都进行一次完整的比 较来验算通过选择适当的素数可以把出错概率控 制在1/n之内?算法复杂度=O(n + m)表达式表达式?给定两个只包含+-*运算符的表达式，问 它们是否等价例如(X+Y)*(X-Y)和X*X-Y*Y是完全等价 的一种思路：可以给变量随机赋值，检查 两个表达式得到的结果是否相等随机化贪心随机化贪心?在使用贪心算法时，往往可以加入随机 化因子，从而在一定程度上避免过分贪 心的缺陷for A←局部最优解to 局部最差解?以概率p返回A?return 局部最差解并行计算并行计算?输入一个由+，-，，，(，)，变量(大写 字母)组成的四则运算表达式，输出一段 指令，控制有两个运算器的并行计算机 在尽量短的时间内正确计算表达式的值 。

贪心方案贪心方案?每次选取耗时长的运算符?每次选取最早空闲的运算器?加入随机因子，并非完全贪心局部搜索局部搜索?基本思想：通过局部调整来达到某个极 大值SAT?目标：尽可能减少一个CNF公式中值为 假的子句数目?随机产生一组变量赋值?每次改变一个变量的赋值，如果值为假 的子句数目减少，就接受，否则重新选 取变量n皇后问题皇后问题?目标：使能够相互攻击的皇后对数目尽 可能地小?随机生成一个布局?每次改变一个皇后的位置如果能够相 互攻击的皇后对数目减小，则接受，否 则重新选取皇后和位置贪婪局部搜索贪婪局部搜索?局部搜索往往配合贪心法，即选择当前 最好的调整方法SAT：选择使为假子句减少最快的方案?n皇后：选择与其他皇后冲突最小的方案 局部搜索的缺点局部搜索的缺点?容易遇到局部最大值?侧向移动：在无法找到一个更好的解的 时候，选择一个相等的解需要限制侧 向移动的步数，因为很容易陷入死循环 随机行走：在无法找到一个更好的解的 时候，对局部做随机调整禁忌搜索禁忌搜索?禁忌搜索是对局部搜索的一种改进，它 的主要思想是禁止连续进行某些重复的 局部调整操作禁忌搜索算法描述禁忌搜索算法描述?选定一个初始解。

禁忌表为空若满足停止规则，停止计算；否则在满 足禁忌要求的候选集中选出一个评价值 最佳的解更新禁忌表，并进行局部调整01串串?给定7个整数N,A0,B0,L0,A1,B1,L1，要求设计一个01串 S=s1s2…si…sN，满足：?si=0或si=1，1−+ ⎪⎩⎪⎨⎧−=11 1111111111111 0000000000010),(),(),(0),(),(),(),(),(0),(),()(LNiLNiAixgixgABixgABixgBixgAixgixgABixgABixgBixgxf定义定义操作12345678910评价值222018★18181818182022禁忌长度0000000000第一步第一步操作12345678910评价值171624T141312★12121416禁忌长度0030000000第二步第二步操作12345678910评价值111018T9918T87★810禁忌长度0020030000第三步第三步操作12345678910评价值6513T4★412T712T56禁忌长度0010020300第四步第四步第五步第五步操作12345678910评价值3587T78T49T2★3禁忌长度0003010200第六步第六步操作12345678910评价值1★365T5655T4T4禁忌长度0002000130第七步第七步操作12345678910评价值2T544T45443T3★禁忌长度3001000020第八步第八步操作12345678910评价值4T7666763★2T1T禁忌长度2000000013第九步第九步操作12345678910评价值4T766680★3T64T禁忌长度1000000302特赦规则特赦规则?某些时候，被禁止的操作能够让目标函 数值大幅变优，此时可以取消该禁忌。

模拟退火算法模拟退火算法?模拟退火算法是把局部搜索和随机化思想结合 起来应用在每次选择局部调整的时候，随机选择一个调 整方案如果调整方案得到的解优于当前解， 则接受否则以某个小于1的概率接受这个 概率和解的“恶劣程度”成指数关系，越“恶劣” 则越小并且随着迭代的深入，这个概率也会 越来越小模拟退火算法描述模拟退火算法描述?for t := 1 to MAX do?begin?T := f(t);?if T = 0 then 返回当前解;?随机选择一种局部调整方案?ΔE=调整方案值-当前解值?if ΔE > 0 then 进行局部调整?else 以eΔE/T的概率进行局部调整?end;。