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

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

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

2、问题中的应用，并提炼出它们的共同点。关键字信息学竞赛调整思想随机化调整/改进/变换非最优化问题2006年全国信息学冬令营讲座引入“调整”这个词语，大家应该都不会陌生，因为在日常的生活工作中经常能听到。例如我们平时洗澡的时候，如果水太烫，那么我们就把水温调低；如果水太凉，就把水温调高，这就是一种“调整”。“调整”的本意为“改变原有的情况，使之更适应客观环境和要求”摘自《现代汉语词典》，例如“产业结构调整”、“军事战略调整”等等都是通过对结构、战略的调整改良，使之更加优秀，从而赢得更大的利益。这种思想，在计算机科

3、学中自然并不少见。例如解决线性规划问题的经典算法——“单纯形算法”，以及目前很流行的“模拟退火算法”，都用到了这一思想。那么，让我们来看看这一思想在信息学竞赛解题中的精彩表现把！“调整思想”在一类构造问题中的应用[例题一]远程通信（Baltic2001）波罗的海上有两个小岛：Bornholm和Gotland。在每个小岛上都有一些神奇的远程通信端口，每个通信端口可以运行在两种模式下——发送模式和接收模式。Bornholm和Gotland分别有n和m个这样的端口，每个端口都连接着另一个小岛某个端口，称为“目标端口

4、”。请设置这n+m个端口的模式，使得所有端口都处于工作状态，即：l对于处于接收模式的端口A，另一个小岛上至少有一个以A为目标端口的端口被设置成发送模式。l对于处于发送模式的端口B，它的目标端口必须处于接收状态。其中1≤n,m≤50000。如下图（每个点指向的点表示它的目标端口）：BornholmGotland123412345n个m个2006年全国信息学冬令营讲座那么它的一种设置方案为：BornholmGotland123412345n个m个即Bornholm岛上1号、4号端口与Gotland岛上2号、5号端

5、口被设置为接收状态，其他端口被设置为发送状态。[分析]我们先来观察一下样例，也许能带给我们一些比较有用的信息。可以发现，Gotland上的1号、4号端口，没有其他端口以它们为目标端口。因为所有端口都必须处于工作状态，所以这两个端口必须被设置为发送状态。由于Gotland上的1号、4号端口被设置成发送状态，它们的目标端口（即Bornholm上的1号端口）必须为设置为接收模式。因为Bornhome上1号端口被设置为接收模式，从而导致了Gotland上的3号端口必须被设置为发送模式……以此类推，我们就可以得出答案。

6、然而这个简单的事实并不总是能帮我们找到方案，如下图：1234BornholmGotland1234上图中在每个岛中各有4个端口，并且对于每个端口都有其他端口以它为目标端口。事实上上图存在两个方案：Bornholm上的端口都设置为发送模式且Gotland上的端口都设置为接收模式，或者反一下，Bornholm上的端口都设置为接收模式而Gotland上的端口都设置为发送模式。也就是说，对于上图，没有哪个端口的模式可以被直接确定，那么我们先前提到的事实就不能帮助我们求得方案了。虽然上面的事实看起来很有用，但是我们无法

7、直接利用它得到方案。现在我们放弃这条思路，来看一种更简单的方法：我们设所有Bornholm上的端口都处于发送状态，所有Gotland上的端口都处于接收状态。显然这样设置并不一定满足条件，因为有些Gotland上处于接收状态的端口可能是无用2006年全国信息学冬令营讲座的。那么，我们将通过一种“调整”的方法，改进方案使之满足要求。我们用伪代码来描述这个“调整”算法：1:设置Bornholm上所有端口为发送状态2:设置Gotland上所有端口为接收状态3:whileGotland上存在一个无效的接收端口xdo4:

8、改变端口x的状态，设置为发送状态5:设置端口x的目标端口的状态为接收状态第4行与第5行两部分就是执行我们所谓的“调整”过程。很显然，经过一次调整，Gotland上的接收端口数目减少一，所以这个算法肯定是会结束的。那么，算法执行得到的方案一定可行么？我们来证明一下：[证明]l对于Gotland上的接收端口，必然每一个都是有效的，不然算法不会结束l对于Gotland上的发送端口，我们在第5行设置它的目标