10.刘家骅《浅谈随机化在信息学竞赛中的应用》

广东省韶关市第一中学刘家骅信息学竞赛的题目日新月异新型算法层出不穷随机化算法作为一种新兴算法犹如新生的太阳在信息学竞赛的广阔天空上焕发光芒引言简单问题的另类算法•有一个多边形A1A2…AN，在每条边AiAi+1上向多边形外做一个等腰三角形AiMiAi+1使得角AiMiAi+1=αi•由αi组成的集合满足其任何非空子集的角度和不是360度的倍数•给出N(3≤N≤50)，所有Mi的坐标和αi，写一个程序，输出多边行的顶点的坐标例题Geometricaldreams(Ural1046)例题Geometricaldreams(Ural1046)•一般方法——简单解方程•有没有其他方法呢？•让我们换一个角度思考问题•只要确定了一个顶点的坐标，多边形的其他顶点的坐标就能够通过简单计算得到，那么问题就转化为确定多边形的一个顶点的坐标例题Geometricaldreams(Ural1046)确定一个顶点的位置？随机化当第一个顶点的位置被暂时确定通过计算能够得到第N+1个顶点的位置当第N+1个顶点越接近第1个顶点这个顶点的位置就越接近其实际位置例题Geometricaldreams(Ural1046)•我们每次可以在当前最优位置旁边随机化确定第一个顶点的位置，然后计算此时第N+1个顶点与第1个顶点的距离•如果这个距离比当前最优距离更小，那么我们就用这个位置更新当前最优位置•显然，当第1个顶点与第N+1个顶点重合时，此时第1个顶点的位置即为其实际位置事实证明这种方法能够通过这道题目例题Geometricaldreams(Ural1046)•虽然这样的方法显然在任何方面都要比前面提到的普通做法要复杂•对于解决这道题目没有太大的意义•但是，它提供给我们一种崭新的思路——随机化•随机化算法对于这样的题目没有优势，但它在很多问题上都能得到运用，下面，我们一起来进一步领略随机化算法的魅力吧小试牛刀•从山顶到山脚的路上有n棵老树，现在政府决定砍掉它们，为了不浪费木材，每一棵树都会被转运到锯木场•树只能往一个方向运输——向下例题：Twosawmills(CEOI2004)例题：Twosawmills(CEOI2004)•在路的尽头有一个锯木场。两个额外的锯木场可以在路上任意一棵老树位置上•你必须选择在哪里建造，使得运输的费用达到最少•运输费用是一分每米每千克木材例题：Twosawmills(CEOI2004)•这道题目的标准算法将数据转化为图象，用栈进行处理求出两个矩形的最大覆盖面积，时间复杂度为O(N)。•但是，这种算法对能力要求不小，不太容易想到。•我们看下随机化算法在这题上的表现例题：Twosawmills(CEOI2004)•首先最容易想到的随机化当然就是直接随机寻找两个点，计算出以这两个点为锯木场时的总运费，多次随机后将总费用最小的输出•我们可以进行预处理，将计算的时间复杂度降为O(1)，那么在时限内我们可以随机几百万次甚至几千万次，但是相对于总状态的四亿来说，寻找到最优解的几率不是很大例题：Twosawmills(CEOI2004)•我们刚才是用随机化算法直接出解，准确性不太好•为了增加准确性，那么我们尝试一下用随机化来缩小区域范围有没有更好的方法呢？例题：Twosawmills(CEOI2004)•我们建立一个矩阵P，P[X,Y]表示第一个锯木场建立在X，第二个锯木场建立在Y时的总运费例题：Twosawmills(CEOI2004)•一开始时，矩阵的边长为N•我们随机寻找一定数量的点，计算出它们的值例题：Twosawmills(CEOI2004)•选取值最小的点•以这个点为新矩阵的中心，以现在矩阵的边长的固定比例长度作为新矩形的边长(如图中取3/4)，从原来的矩阵中取出一块作为新矩阵的范围例题：Twosawmills(CEOI2004)•然后继续在新矩阵中重复这样的操作，直至新矩阵足够小时，我们即可枚举新矩阵上的每一个点，取其中最小值作为答案。例题：Twosawmills(CEOI2004)•我们惊喜地发现，这种随机化算法对于测试数据能够全部通过！例题：Twosawmills(CEOI2004)•随机化算法的灵活多变使得它的具有更为广阔的运用范围•而这样的多变性也使得我们需要灵活恰当地运用随机化算法才能发挥出它的优势•随机化算法并不只是简单地随便乱来，使用随机化算法的时候与其他算法一样值得细细斟酌，需要匠心独运通过这道题目可以看出：下面让我们来看看随机化算法在实际比赛中的运用解析实战解析•题目大意是给出由N个点、M条边组成的图，求最大生成树•在图1所示例子中黑色边组成的树即为最优方案例题：小H的聚会(NOI2005)例题：小H的聚会(NOI2005)•但是，为了减轻每个顶点的负担，题目设定了每个顶点的最大连接边数ki•还是用图1的例子，若我们为1至5每个点分别加上了ki=1,1,4,2,2的限制，则上述方案就不能满足要求了。此时的最优方案如图2所示例题：小H的聚会(NOI2005)•这是一道提交答案题，题目数据分为三种类型•第一种类型包括第1-3个数据，每个点的度限制均为N-1，等同于没有限制，直接用最小生成树算法即可解决•第二种类型包括第4-6个数据，其中N-1个点的度限制为N-1，只有一个点有度限制，可以使用最小度限制生成树算法解决。例题：小H的聚会(NOI2005)•题目数据的第三种类型包括第7-10个数据，数据中所有点都有度限制,没有太好的准确算法•而这个题目又是不要求最优解的开放性题目•这种问题实在是随机化算法自由翱翔的广阔天空。•我们可以采取随机化算法结合不同算法解决这个题目。例题：小H的聚会(NOI2005)•我们用Kruskal算法计算出符合点的度限制的一棵生成树•由于有了度限制，所以这样得出的生成树不一定是最优的•我们可以在按边权大小排序后，再随机打乱部分边的顺序，再用Kruskal算法，以求得到更优的解。方法一：基于Kruskal的随机化算法例题：小H的聚会(NOI2005)•在每次得到这样一棵较大的生成树后，我们再随机化选取一条不在生成树上的边，加入生成树上得到一个圈•再在这个圈上试图删除一条边使得生成树仍然满足度限制并且结果更优•如此重复多次，以得到不能再通过这种方法得到更优解的极优解。方法一：基于Kruskal的随机化算法例题：小H的聚会(NOI2005)•多次使用Kruskal算法后输出计算出的最优解方法一：基于Kruskal的随机化算法例题：小H的聚会(NOI2005)•先用Prim算法计算出一个不考虑度限制的最大生成树•在这棵生成树上，每次随机选取一个不满足度限制的点，并试图寻找不在生成树上边替代在生成树内并且连接到这个点的边以降低这个点的度方法二：基于Prim的随机化算法例题：小H的聚会(NOI2005)•多次重复直至将这棵树修改到满足度限制或者无法再用这样的方法降低这棵树不满足度限制的点的度的时候停止•重新在原最大生成树上重复上述操作多次，输出计算出的最优解方法二：基于Prim的随机化算法例题：小H的聚会(NOI2005)两种算法的比较例题：小H的聚会(NOI2005)使用随机化算法在开放性题目能够得到很好的结果使用随机化算法结合不同的算法会得到不同的结果在解题时运用恰当的算法配合随机化算法能提高程序的准确性通过上面例题可以看出：总结o针对不同情况灵活运用随机化算法，充分发挥其灵活多变的特点o注意应用随机化算法与恰当的算法结合以激发更大的活力•注意随机决策和调整的效率，充分利用题目所给出的限制时间从上述的题目中可以看出，随机化算法具有灵活多变的特点，应用随机化算法应该注意几点：总结最后，让我们展开创造性思维的翅膀，在信息学的广阔蓝天上自由翱翔，划出一道亮丽的风景