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