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

2006年全国信息学冬令营讲座浅谈“调整”思想在信息学竞赛中的应用浙江省绍兴市第一中学唐文斌摘要当前信息学竞赛中的题目难度越来越大、数据关系越来越复杂，往往很难找到一种直接求得最优解的方法。退而求其次，先任意找到一个可行解，再对这个可行解通过一系列调整、变换，不断地对方案进行改进，最终符合我们的要求，这便是一种“调整”的思想。这种思想在信息学竞赛中有着相当广泛的应用，在一些非最优化的开放性问题中更有着杰出的表现，但是它在各类问题中的表现形式又是多种多样的。本文将选取几个具有代表性的例题，说明“调整”思想在各类问题中的应用，并提炼出它们的共同点。关键字信息学竞赛调整思想随机化调整/改进/变换非最优化问题2006年全国信息学冬令营讲座引入“调整”这个词语，大家应该都不会陌生，因为在日常的生活工作中经常能听到。例如我们平时洗澡的时候，如果水太烫，那么我们就把水温调低；如果水太凉，就把水温调高，这就是一种“调整”。“调整”的本意为“改变原有的情况，使之更适应客观环境和要求”1，例如“产业结构调整”、“军事战略调整”等等都是通过对结构、战略的调整改良，使之更加优秀，从而赢得更大的利益。这种思想，在计算机科学中自然并不少见。例如解决线性规划问题的经典算法——“单纯形算法”，以及目前很流行的“模拟退火算法”，都用到了这一思想。那么，让我们来看看这一思想在信息学竞赛解题中的精彩表现把！“调整思想”在一类构造问题中的应用[例题一]远程通信（Baltic2001）波罗的海上有两个小岛：Bornholm和Gotland。在每个小岛上都有一些神奇的远程通信端口，每个通信端口可以运行在两种模式下——发送模式和接收模式。Bornholm和Gotland分别有n和m个这样的端口，每个端口都连接着另一个小岛某个端口，称为“目标端口”。请设置这n+m个端口的模式，使得所有端口都处于工作状态，即：对于处于接收模式的端口A，另一个小岛上至少有一个以A为目标端口的端口被设置成发送模式。对于处于发送模式的端口B，它的目标端口必须处于接收状态。其中1≤n,m≤50000。如下图（每个点指向的点表示它的目标端口）：那么它的一种设置方案为：1摘自《现代汉语词典》BornholmGotland123412345n个m个2006年全国信息学冬令营讲座即Bornholm岛上1号、4号端口与Gotland岛上2号、5号端口被设置为接收状态，其他端口被设置为发送状态。[分析]我们先来观察一下样例，也许能带给我们一些比较有用的信息。可以发现，Gotland上的1号、4号端口，没有其他端口以它们为目标端口。因为所有端口都必须处于工作状态，所以这两个端口必须被设置为发送状态。由于Gotland上的1号、4号端口被设置成发送状态，它们的目标端口（即Bornholm上的1号端口）必须为设置为接收模式。因为Bornhome上1号端口被设置为接收模式，从而导致了Gotland上的3号端口必须被设置为发送模式……以此类推，我们就可以得出答案。然而这个简单的事实并不总是能帮我们找到方案，如下图：上图中在每个岛中各有4个端口，并且对于每个端口都有其他端口以它为目标端口。事实上上图存在两个方案：Bornholm上的端口都设置为发送模式且Gotland上的端口都设置为接收模式，或者反一下，Bornholm上的端口都设置为接收模式而Gotland上的端口都设置为发送模式。也就是说，对于上图，没有哪个端口的模式可以被直接确定，那么我们先前提到的事实就不能帮助我们求得方案了。虽然上面的事实看起来很有用，但是我们无法直接利用它得到方案。现在我们放弃这条思路，来看一种更简单的方法：我们设所有Bornholm上的端口都处于发送状态，所有Gotland上的端口都处于接收状态。显然这样设置并不一定满足条件，因为有些Gotland上处于接收状态的端口可能是无用的。那么，我们将通过一种“调整”的方法，改进方案使之满足要求。BornholmGotland123412345n个m个1234BornholmGotland12342006年全国信息学冬令营讲座我们用伪代码来描述这个“调整”算法：1:设置Bornholm上所有端口为发送状态2:设置Gotland上所有端口为接收状态3:whileGotland上存在一个无效的接收端口xdo4:改变端口x的状态，设置为发送状态5:设置端口x的目标端口的状态为接收状态第4行与第5行两部分就是执行我们所谓的“调整”过程。很显然，经过一次调整，Gotland上的接收端口数目减少一，所以这个算法肯定是会结束的。那么，算法执行得到的方案一定可行么？我们来证明一下：[证明]对于Gotland上的接收端口，必然每一个都是有效的，不然算法不会结束对于Gotland上的发送端口，我们在第5行设置它的目标端口为接收状态并且其状态不会被改变，所以Gotland上的发送端口也处于工作状态。对于Bornholm上的接收端口，它会被设置为接收状态的原因在Gotland上有一个以它为目标端口的端口被设置为发送状态（第4、5行），所以它也处于工作状态。对于Bornholm上的发送端口，它的目标端口一开始就被设置成接收状态了。上述[证明]不仅证明了“调整”算法的正确性，同时也说明了任意输入都是有解的。那么实现就很简单了，以此检查Gotland上每一个接收端口x，如果它的入度为0（即无用接收端口），则置它为发送状态，如果x的目标端口处于发送状态，则设置x的目标端口y为接收状态，修改y的目标端口z的入度。而这可能使得z变成一个无用的接收端口，则对z再进行类似的调整。由于每一个端口最多被调整一次，所以“调整”操作的平摊复杂度为O(1)，所以总时间复杂度为()Onm，这已经是本问题的时间下界了。[例题二]混合图的欧拉回路问题（经典问题）给出一个N个点和M条边的混合图（即有些边是无向边，有的边是有向边）。试求出它的一条欧拉回路，如果没有，输出无解信息。[分析]由于无向边只能经过一次，所以本题中不能把一条无向边拆成两条方向相反的有向边，因而原来的“套圈”算法变得不可行，我们只能把每条无向边定向，再求定向后的有向图的欧拉回路。我们回想一下有向图存在欧拉回路的充要条件为：基图2连通，且每个节点的入度等于出度。同样的，混合图存在欧拉回路的一个必要条件仍然是基图连通，在此前提下，如果它存在欧拉回路，即我们可以找到一种将无向边定向的方法，使得每个点的入度等于出度。所以2基图就是把所有的有向边变成无向边之后得到的图2006年全国信息学冬令营讲座如果存在下述情况，问题无解：基图不连通设点u在基图中的度数为[]Degu。如果[]Degu为奇数，则无解。如果从u发出的有向边个数或者进入到u点的有向边个数超过了[]2Degu，也无解。而不满足上述情况的混合图，下面我们将知道它是必然有解的。由上可知，我们的目标是“入度等于出度”，这个与网络流的流量平衡条件十分类似，所以本题可以用网络流来做。但是，该方法较为复杂且容易出错。下面我们来介绍一种应用“调整”思想的“无向边任意定向算法”：顾名思义，首先我们把所有无向边任意定向得到一个“方案”。但事实上这个“方案”是不满足要求的，所以我们加了引号。那么现在的问题就在于，能否通过某些操作，使得原来不满足要求的“方案”成为真正的方案呢？这正是我们的“调整”操作！设点u在当前“方案”中的入度为[]InDegu，出度为[]OuDegu。显然存在[][]uGuGInDeguOuDegu。每一次，我们寻找一个出度大于入度的点a，即满足[][]OuDegaInDega。如果找不到这样的点，当前方案已满足要求，因为[][]uGuGInDeguOuDegu。从点a开始，在沿着被定向的无向边，找到一条通往点b的路，满足点b的出度小于入度，即[][]OuDegbInDegb。这样，我们把这条路上所有边的方向都反向，就使得点a出度减小、入度增加，点b出度增加、入度减小，而对于路上的中间点，入度出度都没有改变。这便是我们找寻的“调整”操作。点a、点b出入度的变化意味着，我们现在得到的“方案”，比原有的“方案”出入度更“平衡”。所以只要不断找这样的点a，找路径调整，即可。现在只剩下一个问题，如果存在出度大于入度的点a，是否每次都能沿着被定向的无向边找到一条通往满足出度小于入度的点b的路呢？答案是肯定可以。其实这个也是很显然的，更正式一些，下面我们来给出证明：[证明]我们从一个出度大于入度的点a开始，目标是通过被定向的无向边走向一个入度大于出度的点b。假设我们当前到达了点u，如果u的入度大于出度，那么已经达到目标。否则，u的出度大于等于入度。由于从u发出的有向边个数或者进入到u点的有向边个数都不超过[]2Degu（否则就无解），这说明我们肯定通过被定向的无向边走到另一个点v。又由于总入度等于总出度，所以我们也不可能一直在出度大于等于入度的点上绕圈。那么，从当前点u必然能往下走到v，并且总能走到一个入度大于出度的点b。这个证明也表明了不满足上文中提到的几个条件的混合图是必然有解的。2006年全国信息学冬令营讲座每一次调整的时间复杂度为()Onm，而调整的次数不会超过2m。所以总时间复杂度为(*())Omnm。[小结]对于上述两个例题，有一些线索启发着我们，但是我们却找不到好的方法利用线索直接得到答案。这个时候，我们先得到一个随意的“方案”，而这个“方案”可能是不符合要求的，经过逐步的“调整”，使得方案更加趋向于满足条件，最终得到符合要求的方案。调“不可行”为“可行”，从无到有，正是“调整”思想在这类构造问题中的应用。“调整”思想在非最优化的开放性问题中的应用[例题三]零件装配（提交答案）话说HURRICANE小组在实习中切割好了全部所需的nm个不同的零件之后，又需要把他们装配在一起成为可以使用的产品。现已知每个产品均分为m个部分，每个部分恰好为之前完成的一个零件。在装配产品的一个部分时，可以在为该部分设计出来的n个零件之间任选一个进行安装（但每个零件只能安装一次）。但由于结构上的差异，不可以选择为其他部分所设计的零件进行安装。工厂内恰好有n条装配线可以用作产品的装配，所以可以同时开始n个产品的装配过程加快装配的速度。但不同的零件可能有不同的装配时间，所以我们在装配产品的时候可以通过选择适当的装配方案来减少最晚完成产品的装配时间。你的任务就是给出一个装配方案，使得最晚完成产品的装配线所用时间尽可能少。注：本题是一个提交答案题，一共给出10个输入数据。在最大数据中，n和m高达500。[分析]本题实际上就是给定一个矩阵，矩阵中同一列的数可以互相调换。要求输出一个经过若干次调换后的矩阵，使得矩阵中每行所有数的和中最大的和最小。这个问题实际上是背包问题的一个扩展，因而是NP完全的。所幸题目并不是要我们求最优解，而是求一个尽可能优的解。对于本题，动态规划、搜索显然不能胜任。在本题中动态规划的状态数目就是指数级的；而搜索，对于N=500这种规模也是望尘莫及的。那么我们可以尝试一下贪心算法：要求最大和最小，等价于要求所有和尽量平均。因为如果一个偏小了，必然有另一个偏大了。所以一个很直观的贪心想法就是把最大的和最小的凑在一起。我们一列一列考虑，当我们处理第i列时，前i-1列已经安排好，不妨设第p行中已经安排好的前i-1个数的和为S[p]。对于i列中的n个数，把最大的分配给S[x]最小的第x行，把次大的分割S[y]次小的第y行，以此类推。直到安排完所有数。2006年全国信息学冬令营讲座经测试可以发现，这个贪心算法得到的解并不是很优，因为贪心算法只关心眼前状态，缺乏全局观，而局部的最优，可能导致全局的不优。那是否有其他更好的方法呢？这正是“调整”思想大显身手的时候！我们的目标是使得最大的和最小，也就是让所有的和尽量平均。假设有方案A，设1..[][][]jMSiAij，其中i=1..N。如果存在两个数A[r1][c]和A[r2][c]，使得交换这两个数后，S[r1]与S[r2]将更加平