国家集训队2006论文集 唐文斌

《国家集训队2006论文集 唐文斌》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、，前c-1列已经被安排好。TabForthisLevel常规算法：动态规划:状态是指数级别的搜索:N,M过大,搜索不可能出解贪心算法:[例三]零件装配前c-1列第c列……从小到大排序从小到大排序[例三]零件装配然而这个贪心算法得到的解并不优。请看下面例子:11422633881012118226334局部的最优，可能导致全局的不优10[例三]零件装配A1,1,A1,2,A1,3…A1,mA2,1,A2,2,A2,3…A2,m…An,1,An,2,An,3…An,m尝试交换Sum1’Sumn’如果满足

6、Sum1’-Sum2’

7、<

8、Sum1-Sumn

9、我们称此方案“可

10、调整”调整算法:“极优”方案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

11、,A2,2,…An,2,基准列从小到大排序从小到大排序按照贪心思想分配每次调整，方案很可能会更优，至少不会变差[例三]零件装配局部调整整体调整极优方案初始可行方案“调整”操作调“可行”为“更优”回顾与总结[例一]调“不可行”为“可行”一类构造性问题[例二]《混合图欧拉回路问题》[例三]调“可行”为“更优”一类非最优化的开放性问题中[例四]Ural著名难题《皇帝的困惑》从无到有从有到优「调整」思想的精髓ThankYou!模拟退火算法简介(1)模拟退火算法来源于固体退火原理。将固体加温至温度充分高，再让其徐徐冷却.加温时，固体内部粒子随着温度升高变为无序状，内能增大

12、；而徐徐冷