算法合集之《非完美算法初探》

非完美算法的应用——河北唐山一中任一恒在平时的练习和考试中，我们都是尽量设计出完全正确的算法来解决问题。可是，实际中很多问题都是不能完美解决的，还有很多问题完美解决所需要的时间&空间是根本无法接受的，所以，非完美的算法在实际中有着很广的应用。随着竞赛的题目越来越接近时际，以按优劣计分的题目为代表的考察非完美算法的题目越来越多，本文将讨论一些常用的非完美算法，希望给读者一些启发。1、贪心算法贪心算法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。这样我们就得到了一个解，但是我们无法保证解是最优的。下面我们来看看贪心算法的表现。例题1NOI2007追捕盗贼某国家要追捕一个大盗，该国家的城市网络是一棵树，现在要你通过在某城市空降警察，让警察从某城市移动到有道路连接的城市，收回某警察来达到捕捉到盗贼的目的。用到的警察越少越好。这道题的标准算法用到了很多高等知识，而且实现也是相当复杂的，在限定的时间内完美的解决这道题可以说是不能完成的任务，那么我们贪心算法在这道题上的表现如何呢？我们不妨将原树想象为一棵有根的树，先在根结点空降一个警察，然后再次在根结点空降一个警察，让这个警察走向某棵子树，对这棵子树重复上面的过程，这样一棵子树一棵子树的排除，直到整棵树被排除。这里可以采取一个十分有效的优化就是在只剩一棵子树的时候，不用再安排新的警察，直接让一直守在根结点的那个警察走过去即可。所以不妨安排需要警察最多的那颗子树最后走，这样可以使结果得到很大优化。由于结点数不超过1000，所以我们可以枚举每个结点为根结点，找出其中需要警察最少的那个。这个算法虽然存在着反例，但是由于那个十分有用的优化，可以使结果十分接近标准结果。通过数据试验的结果，有90%的结果和标准算法产生的结果一致，10%不一致的相差也是十分的小。可以说贪心算法在这道题目上发挥的很好。贪心算法的优点在于实现容易，时间效率高，而其缺点则是在很多时候和标准算法的差距过大，精确度不够。所以我们要尽量优化贪心算法。优化贪心算法主要从两个方面来着手：1、多和完美算法结合，可以通过在部分使用完美算法而总体使用贪心的方法，通过贪心来结合若干部分的最优结果，尽量的接近真正最优的结果；2、贪心权值的选择，一个贪心算法的关键就是所选的策略，所以在选择权值时我们要尽可能的包含更多的能对全局产生影响的信息，使最终解能更加接近最优解。二、随机算法和上面的贪心算法相同，随机算法也是使用较多的一种算法。下面我们来看一道例题。例题2SPOJ1481Yetanothercomputernetworkproblem给你一个n个点，m条边的无向图，让你构建一棵生成树,但是每个点的度数不能超过一个给定的限制b，求所能构建的最小生成树。（1=n=10^4,1=m=10^5,1=b=n）如果没有度数的限制，那么这道题就是一个十分简单的最小生成树，有了这道题之后我们应该如何处理呢？我们不妨在考虑每个点连出的边选取不超过b的前提下用kruskal算法计算出一棵生成树。然后，能对结果产生优化的变化必然是用一条由度数已经达到b的点连出的一条边和某条边替换另一条由该度数达到b的点连出的边和另一条边。所以我们不妨随机一个度数达到b的点，随机选取它的一条被选中的边和未被选中的边交换，然后添加一条边，这时图中产生了一个环，在环中删除长度最长的边，如果结果比之前更优则保留结果。实践证明，此方法对于该题目能产生十分优秀的结果。其实，随机算法很少单独应用，更多时候是和其它算法相结合，来使我们的非完美算法产生更加优秀的解。三、抽样测试法抽样，即从统计总体中，任意抽出一部分单位作为样本，并以其结果推算总体的相应指标。在某些问题中，需要让我们检查一系列测试元s，如果s中的某个测试元满足了某个条件，那么则说s满足了某个性质。在大度数情况下，我们需要将s中的测试元一个一个的进行验证，才能确定s是否满足该性质。但是如果s满足如下性质，要不s中不含满足条件的测试元，要不满足某条件的测试元很多，则可以直接选取几个具有代表性的测试元进行测试，通过这几个测试元来确定s是否满足该性质。例题3SPOJ919PrimeChecker存在一个数列，第一项为1，以后各项根据公式ai=(ai-1+1234567890)mod231推出，问这个数列的各项是否为质数。如果是质数的就输出0，是合数的就输出1，在时间限制内输出的越多，得到的分数越多。看到这个题目，我们首先想到的是最为朴素的做法，先求出1-100000的素数表，然后对于每个数ai，用1-trunc(sqrt(ai))间质数去除这个数，如果某个质数能够整除ai，则ai为合数，如果均不能整除，则ai为质数。这种方法实现起来无疑是十分简便的，但是由于复杂度较高，所以在时间限制内仅能完成200000多一点的数。下面我们来看一个使用抽样测试法的质数判断方法。对于一个整数n，设n-1=d*2^s(d是奇数)，对于给定的基底a，如果存在a^d=1(modn)或者对于0=rs，存在a^(d*2^r)=-1(modn)则称n是以a为基底的强伪质数。一个质数n以所有小于n的整数为底都是强伪质数，而一个合数n，以小于n的数为底，n最多有1/4的机会成为强伪质数。根据这条，我们不妨随机地抽取小于n的数为底，如果抽取了k个数，则正确的概率为1-1/4^k，k取到几十的时候一般不会出错了。如果我们不采用随机的方法而是直接抽样特殊底——最小的几个质数，情况怎样呢？经过试验发现，如果以2为底，第一个不符合的数为2047；如果以2、3为底，第一个不符合的数为1373653；如果以2、3、5为底，第一个不符合的数为25326001；如果以2、3、5、7为底，则2^31内的数均符合了。所以，对于本题，我们直接以2、3、5、7为底进行测试即可。时间复杂度变为了O(NlogN)，比之前的朴素算法有了很多的提高。四、模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为E-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。模拟退火的基本思想:(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，……，L做第3至第6步：(3)产生新解S′(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数(5)若Δt′0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(7)T逐渐减少，且T-0，然后转第2步。例题4TSP问题设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j)i,j=1,…,n．找出遍访每个域市恰好一次的一条回路，且其路径总长度为最短。求解TSP的模拟退火算法模型可描述如下：解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2,……，wn)，并记wn+1=w1。初始解可选为(1，……，n)目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数的最小值。新解的产生随机产生1和n之间的两相异数k和m，若km，则将(w1,w2,…，wk,wk+1,…，wm,…，wn)变为：(w1,w2,…，wm,wm-1,…，wk+1,wk,…，wn).如果是km，则将(w1,w2,…，wm,wm+1,…，wk,…，wn)变为：(wm,wm-1,…，w1,wm+1,…，wk-1,wn,wn-1,…，wk).上述变换方法可简单说成是“逆转中间或者逆转两端”。代价函数差设将(w1,w2,……，wn)变换为(u1,u2,……，un),则代价函数差为：[d(u1,u2)+d(u2,u3)+…+d(un-1,un)+d(un,u1)]-[d(w1,w2)+d(w2,w3)+…+d(wn-1,wn)+d(wn,w1)]。将这些部分代入模拟退火算法的基本过程即可解决TSP问题了。模拟退火算法的应用很广泛，在应用的时候主要注意以下3点：(1)温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一，初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。(2)退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。(3)温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)＝k×T(t)式中k为正的略小于1.00的常数，t为降温的次数。实践例题5百度之星2007紧急修复某市的k家公司瘫痪，要在T小时之后才能自动修复，每家公司每小时都在受到损失，第i家公司每小时受损为P(i)，现在派遣n只维修队进行抢修，力求在自动修复之前将损失降到最小。城市被划分为r*c的网格，现给出了每个公司的坐标，每个维修队的初始坐标，每个公司的受损程度。每小时每个维修队可以移动（最多s格），也可以维修它所处在的格子，现在希望你设计一种方案使损失降低到最小。对于这道题目，并不存在一个完美的算法，所以我们要想出一个尽可能优秀的算法。首先，我们要进行一个bfs，计算两点间的距离，由于每个维修队肯定都是以一个公司为某段行程的终点，所以并不需要计算任意两点间的距离，只需要算出每个点到每个公司的距离即可，这一步的时间复杂度为O(RCK)。按照题目要求，我们在T时间之前修理完越多的公司越好。所以我们不妨安排一个要修理的公司的顺序，按照顺序依次全力修理完每个公司。对于当前选中的公司，如果某个修理队赶到那里能提前结束维修，就让他赶过去修理。如果不能，他就可以前往下一个公司了。公司顺序的选择关系到了我们算法的优秀程度，我们可以使用前面提到的模拟退火方法来实现公司顺序的选择，这样整个算法的结果就十分优秀了。总结本文介绍了几种常用的非完美算法，通过以上问题的分析，我们可以看出，非完美算法有着很广泛的应用，它有着时空消耗低，编程复杂度低，思维容易的优点，而且在处理很多题目时，有着不逊于甚至优于完美算法的表现。所以，合理的使用非完美算法能给我们满意的结果。由于学识有限，所以本文的探讨比较肤浅，非完美算法还需要大家在学习时更多的探讨和总结。参考文献《非最优化算法初探》杨培2000年论文。《浅析非完美算法在信息学竞赛中的应用》胡伟栋2005年论文。楼天成百度之星解题报告。《SAA，模拟退火算法》。【附录】例题原题NOI2007DAY2追捕盗贼问题描述魔法国度MagicLand里最近出现了一个大盗Frank，他在MagicLand四处作案，专门窃取政府机关的机密文件（因而有人怀疑Frank是敌国派来的间谍）。为了捉住Frank，MagicLand的安全局重拳出击！MagicLand由N个城市组成，