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

浅谈在信息学中的应用浙江绍兴一中唐文斌“调整”思想引入“调整”的本义为：改变原有的情况，使之更适应客观环境和要求产业结构调整军事战略调整引入题目难度越来越大数据关系越来越复杂目标已知不满足要求的初始解更优解更优解更优解调整调整调整调整信息学中的“调整”思想[例一]远程通信（Baltic2001）波罗的海上有两个小岛每个小岛上都有一些远程通信端口每个端口都连接着对方小岛上的一个端口,称为“目标端口”每个端口可以工作在发送模式(黄色标记)接收模式(蓝色标记)A岛B岛123412345n个m个123412345[例一]远程通信请设置这n+m个端口的工作模式，使得所有端口都处于工作状态。(n+m105)即要求:对于发送端口A，其目标端口必须处于接收模式对于接收端口B,至少存在另一个端口以B为目标端口且处于发送模式n个m个发送端口接收端口先从样例下手A岛B岛发出去的数据有人接有数据可收AB123412345[例一]远程通信从样例下手:A岛的2号B岛的1号、4号只能设置为发送模式其目标端口必须为接收模式A岛的3号和B岛的3号n个m个A岛B岛发送端口接收端口[例一]远程通信这个简单的事实，看起来似乎很有用!那它是否总是能帮助我们找到解答呢？答案是否定的1234A岛B岛1234从一个不满足要求的“初始解”开始发送端口接收端口1234[例一]远程通信“调整”算法(1)设置初始解(不一定满足要求)设A岛上的所有端口都是发送模式设B岛上的所有端口都是接收模式(2)WhileB岛上存在无用接收端口xDo(3)改变x的状态，设为发送模式(4)设置x的目标端口为接收模式A岛B岛12345“调整”操作:[例一]远程通信“调整”算法可行性:每一次”调整”操作,会把B岛上的一个接收端口改为发送端口B岛上最初一共有m个接收端口,所以调整次数不会超过m次算法必然会结束，即算法可行“调整”算法正确性:可采用“分类讨论”的方法很简单地证明[例一]远程通信更优:B岛上接收端口数目减少因为问题总是出现在B岛的接收端口上解答已知不满足要求的初始解更优解更优解更优解调整调整调整调整A1,1,A1,2,A1,3…A1,mA2,1,A2,2,A2,3…A2,m…An,1,An,2,An,3…An,mSum1Sum2…Sumn[例三]零件装配（CTSC2004提交答案）给定一个N*M的整数矩阵A(N,M≤500)同一列中的两个数可以调换请求出一个经过若干次调换的矩阵使得最大的行和最小可交换最大和最小可交换贪心算法:最大和最小，等价与让所有的和都尽量平均。一个直观的贪心思想：把最大和最小凑一起依次安排每一列。当我们安排第c列时，前c-1列已经被安排好。TabForthisLevel常规算法：动态规划:状态是指数级别的搜索:N,M过大,搜索不可能出解贪心算法:[例三]零件装配前c-1列第c列……从小到大排序从小到大排序[例三]零件装配然而这个贪心算法得到的解并不优。请看下面例子:11422633881012118226334局部的最优，可能导致全局的不优10[例三]零件装配A1,1,A1,2,A1,3…A1,mA2,1,A2,2,A2,3…A2,m…An,1,An,2,An,3…An,m尝试交换Sum1’Sumn’如果满足|Sum1’-Sum2’||Sum1-Sumn|我们称此方案“可调整”调整算法:“极优”方案Sum1Sum2…SumnSum1’=Sum1-A1,3+An,3Sumn’=Sumn-An,3+A1,3[例三]零件装配调整算法:(1)得到一个随机的初始方案A(2)While方案A“可调整”DO(3)寻找数对进行调整操作(4)得到“极优”方案A由于不同的初始方案可能得到不同的“极优”方案,所以我们可以采用多次随机初始方案，得到若干个极优方案从中取最优的方法，效果非常好。A1,3…A1,mA2,3…A2,m………An,3…An,m[例三]零件装配把最大的和最小的凑在一起第二种”调整”方法A1,1,A2,1,…An,1,A1,2,A2,2,…An,2,基准列从小到大排序从小到大排序按照贪心思想分配每次调整，方案很可能会更优，至少不会变差[例三]零件装配局部调整整体调整极优方案初始可行方案回顾与总结[例一]调“不可行”为“可行”一类构造性问题[例二]《混合图欧拉回路问题》[例三]调“可行”为“更优”一类非最优化的开放性问题中[例四]Ural著名难题《皇帝的困惑》从无到有从有到优「调整」思想的精髓模拟退火算法简介(1)模拟退火算法来源于固体退火原理。将固体加温至温度充分高，再让其徐徐冷却.加温时，固体内部粒子随着温度升高变为无序状，内能增大；而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡状态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为()(*EekBoltzmannT内能改变量常数)模拟退火算法简介(2)(1)初始化:初始温度T(足够大),初始解(S),L(2)Fork=1LDo(3)产生新解S’(4)计算增量dt’=C(S’)–C(S)(5)如果dt’0接受新解S’作为当前解否则以概率exp(-dt’/T)接受S’(6)如果满足终止条件则终止(7)温度T减小(但保证T0),回到第(2)步[例一]调整算法正确性证明(2)WhileB岛上存在无用接收端口xDo(3)改变x的状态，设为发送模式(4)设置x的目标端口为接收模式B岛上的接收端口B岛上的发送端口A岛上的接收端口A岛上的发送端口√√√√任意输入均有解[例二]混合图欧拉回路给定一个混合图(有的边是有向边,有的边是无向边)，求其欧拉回路。首先将所有无向边任意定向调整操作:从一个出度大于入度的点开始，沿着被定向的无向边走到一个入度大于出度的结点。把一路上所有边均反向。