浅谈“调整”思想在信息学竞赛中的应用.docx

《浅谈“调整”思想在信息学竞赛中的应用.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈“调整"思越在信息学竞赛中的应用浙江省绍兴市笫一中学唐文斌摘要当前信息学竞赛中的题目难度越来越大、数据关系越来越复杂，往往很难找到一种直接求得最优解的方法。退而求其次，先任意找到一个可行解，再对这个可行解通过一系列调整、变换，不断地对方案进行改进，最终符合我们的要求，这便是一种“调整”的思想。这种思想在信息学竞赛中有着相当广泛的应用，在一些非最优化的开放性问题中更有着杰出的表现,但是它在各类问题中的表现形式又是多种多样的。本文将选取几个具有代表性的例题，说明“调整”思想在各类问题中的应用，并提炼

2、出它们的共同点。关键字信息学竞赛调整思想随机化调整/改进/变换非最优化问题引入“调整”这个词语，大家应该都不会陌生，因为在LI常的生活工作小经常能听到。例如我们平时洗澡的时候，如果水太烫，那么我们就把水温调低；如果水太凉，就把水温调高,这就定一种“调整”。“调整”的本意为“改变原有的情况，使之更适应客观坏境和耍求”-例如“产业结构调整”、“军事战略调整”等等都是通过对结构、战略的调整改良，使Z更加优秀，从而赢得更大的利益。这种思想，在计算机科学中口然并不少见。例如解决线性规划问题的经典算法——“单纯

3、形算法”，以及冃前很流行的“模拟退火算法”，都用到了这一思想。那么，让我们来看看这一思想在信息学竞赛解题中的糟彩表现把！“调整思想”在一类构造问题中的应用［例题一］远程通信(Baltic2001)波罗的海上有两个小岛：Bornholm和Gotland。在每个小岛上都有一些神奇的远程通信端口，每个通信端口可以运行在两种模式下一一发送模式和接收模式。Bornholm和Gotkmd分别有n和m个这样的端口，每个端口都连接着另一个小岛某个端口，称为“目标端口”。请设置这n+m个端口的模式，使得所有端口都处于

4、工作状态，UP：•对于处于接收模式的端口A,另一个小岛上至少有一个以A为目标端口的端口被设置成发送模式。•对于处于发送模式的端UB,它的标端口必须处于接收状态。其中lWn,mW50000。如下图(每个点指向的点表示它的目标端口)：ornholmGotland〃个加个那么它的一种设置方案为:摘白《现代汉语词典》omholmGotland加个即Bornholm岛上1号、4号端口与Gotland岛上2号、5号端口被设置为接收状态,其他端口被设置为发送状态。［分析］我们先来观察一下样例，也许能带给我们一些比

5、较有用的信息。可以发现，Gotland±的1号、4号端口，没有其他端口以它们为目标端口。因为所有端口都必须处于工作状态，所以这两个端口必须被设置为发送状态。由于Gotland±的1号、4号端口被设置成发送状态，它们的目标端口（即Bornholm±的1号端口）必须为设置为接收模式。因为Bornhome±1号端口被设置为接收模式，从而导致了Gotland.上的3号端口必须被设置为发送模式……以此类推，我们就可以得出答案。然而这个简单的事实并不总是能帮我们找到方案，如下图：ornholmGotland23

6、4上图中在每个岛中各有4个端口，并口对于每个端口都有其他端口以它为目标端口。事实上上图存在两个方案:Bornholm上的端口都设置为发送模式且Gotland上的端口都设置为接收模式，或者反一下，Bornholm±的端口都设置为接收模式而Gotland±的端口都设置为发送模式。也就是说，对于上图，没有哪个端口的模式可以被点接确定，那么我们先前提到的事实就不能帮助我们求得方案了。虽然上面的事实看起来很有用，但是我们无法百接利用它得到方案。现在我们放弃这条思路，來看-•种更简单的方法：我们设所有Bornh

7、olm上的端口都处于发送状态，所HGotland上的端口都处于接收状态。显然这样设置并不一定满足条件，因为冇些Gotland±处于接收状态的端口可能是无用的。那么，我们将通过一种“调整”的方法，改进方案使Z满足耍求。我们用伪代码来描述这个“调整”算法：1:设置Bornholm上所有端口为发送状态2:设置Gotland上所有端口为接收状态3:whileGotlandJ1存在一个无效的接收端口xdo4:改变端IJx的状态，设置为发送状态5:设置端口x的目标端口的状态为接收状态第4行与第5行两部分就是执行

8、我们所谓的“调整”过程。很显然，经过一次调整，Gotland±的接收端口数目减少一，所以这个算法肯定是会结束的。那么，算法执行得到的方案一定可行么？我们来证明一下：［证明］•对于Gotland±的接收端口，必然每一个都是有效的，不然算法不会结束•对于Gotland上的发送端口,我们在第5行设置它的II标端口为接收状态并且其状态不会被改变，所以Gotland上的发送端口也处于工作状态。•对于Bornholm上的接收端口，它会被设置为接收状态的原因在Gotland上有一个