算法合集之《浅谈“调整”思想在信息学竞赛中的应用》

1、浅谈 在信息学中的应用浙江绍兴一中 唐文斌“调整”思想引入n“调整”的本义为：n改变原有的情况，使之更适应客观环境和要求 n产业结构调整n军事战略调整“调整” ? ?单纯形算法模拟退火算法引入n题目难度越来越大n数据关系越来越复杂目标已知x不满足要求的初始解更优解更优解更优解调整调整调整调整信息学中的“调整”思想例一远程通信（Baltic2001）n波罗的海上有两个小岛n每个小岛上都有一些远程通信端口n每个端口都连接着对方小岛上的一个端口,称为 “目标端口”n每个端口可以工作在n发送模式(黄色标记)n接收模式(蓝色标记)A岛岛B岛岛123412345n个m个123412345例一远程通信n请设

2、置这n+m个端口的工作模式，使得所有端口都处于工作状态。(n+m105)n即要求:n对于发送端口A，其目标端口必须处于接收模式n对于接收端口B,至少存在另一个端口以B为目标端口且处于发送模式n个m个发送端口接收端口先从样例下手A岛岛B岛岛发出去的数据有人接有数据可收AB123412345例一远程通信n从样例下手:nA岛的2号nB岛的1号、4号n只能设置为发送模式n其目标端口必须为接收模式nA岛的3号和B岛的3号n个m个A岛岛B岛岛发送端口接收端口例一远程通信n这个简单的事实，看起来似乎很有用!n那它是否总是能帮助我们找到解答呢？n答案是否定的1234A岛岛B岛岛1234从一个不满足要求的“初始

3、解”开始发送端口接收端口1234例一远程通信n“调整”算法n(1)设置初始解(不一定满足要求)设A岛上的所有端口都是发送模式设B岛上的所有端口都是接收模式n(2) While B岛上存在无用接收端口x Don(3)改变x的状态，设为发送模式n(4)设置x的目标端口为接收模式A岛岛B岛岛12345“调整”操作:例一远程通信n“调整”算法可行性 :n每一次”调整”操作,会把B岛上的一个接收端口改为发送端口nB岛上最初一共有m个接收端口,所以调整次数不会超过m次n算法必然会结束，即算法可行n“调整”算法正确性 :n可采用“分类讨论”的方法很简单地证明例一远程通信n更优: B岛上接收端口数目减少 因为

4、问题总是出现在B岛的接收端口上解答已知x不满足要求的初始解更优解更优解更优解调整调整调整调整初步想法调“不可行”为“可行”A1,1, A1,2, A1,3A1,mA2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,mSum1Sum2Sumn例三零件装配（CTSC2004提交答案）n给定一个N*M的整数矩阵A(N,M500)n同一列中的两个数可以调换n请求出一个经过若干次调换的矩阵n使得最大的行和最小可交换最大和 最小可交换n贪心算法:n最大和最小，等价与让所有的和都尽量平均。n一个直观的贪心思想： 把最大和最小凑一起n依次安排每一列。n当我们安排第c列时，前c-1列

5、已经被安排好。nTab For this Leveln常规算法：n动态规划:状态是指数级别的n搜索:N,M 过大,搜索不可能出解n贪心算法:例三零件装配前c-1列第c列从小到大排序从小到大排序例三零件装配n然而这个贪心算法得到的解并不优。n请看下面例子:114226338810121 1 82 2 63 3 4局部的最优，可能导致全局的不优10例三零件装配A1,1, A1,2, A1,3A1,mA2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,m尝试交换Sum1Sumn如果满足 |Sum1-Sum2| |Sum1-Sumn|我们称此方案“可调整”n调整算法:“极优

6、”方案 Sum1 Sum2 SumnSum1= Sum1-A1,3+An,3Sumn= Sumn-An,3+A1,3例三零件装配n调整算法:n(1) 得到一个随机的初始方案An(2) While 方案A“可调整” DOn(3)寻找数对进行调整操作n(4) 得到“极优”方案An由于不同的初始方案可能得到不同的“极优”方案,所以我们可以采用多次随机初始方案，得到若干个极优方案从中取最优的方法，效果非常好。A1,3A1,mA2,3A2,m An,3An,m例三零件装配n把最大的和最小的凑在一起n第二种”调整”方法A1,1, A2,1, An,1, A1,2,A2,2, An,2,基准列从小到大排序从

7、小到大排序按照贪心思想分配按照贪心思想分配每次调整，方案很可能会更优，至少不会变差例三零件装配n局部调整n整体调整极优方案初始可行方案“调整”操作调“可行”为“更优”回顾与总结例一调“不可行” 为“可行”一类构造性问题例二混合图欧拉回路问题例三调“可行”为“更优”一类非最优化的开放性问题中例四Ural著名难题皇帝的困惑从无到有从有到优调整思想的精髓模拟退火算法简介(1)n模拟退火算法来源于固体退火原理。n将固体加温至温度充分高，再让其徐徐冷却.n加温时，固体内部粒子随着温度升高变为无无序状序状，内能增大；而徐徐冷却时粒子渐趋有有序序，在每个温度都达到平衡状态，最后在常温时达到基态，内能减为最小。n根据Metropolis准则，粒子在温度T时趋于平衡的概率为 ()(*Eek BoltzmannT内能改变量常数)模拟退火算法简介(2)n(1)初始化: 初始温度T(足够大),初始解(S),Ln(2)For k = 1 L Don(3)产生新解Sn(4)计算增量dt = C(S) C(S)n(5)如果dt 0),回到第(2)步“调整”思想例一调整算法正确性证明n(2) While B岛上存在无用接收端口x Don(3)改变x的状态，设为发送模式n(4)设置x的目标端口为接收模式B岛上的接收端口B岛上的发送端口A岛上的接收端口A岛上的发