论文–浅谈逆向思维在解题中的应用

《论文–浅谈逆向思维在解题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

正难则反–浅谈逆向思维在解题中的应用【摘要】逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。本文通过几个例子，总结了逆向思维在信息学解题中的应用。【关键字】逆向思维容斥原理参数搜索二分动态规划记忆化【正文】引言我们先看一个简单的问题：平面上有四个点，构成一个边长为1的正方形。现在进行一种操作，每次可以选择两个点A和B，把A关于B对称到C，然后把A去掉。求证：不可能经过有限次操作得到一个边长大于1的正方形操作后的结果是相当复杂的，如果我们从正面着手，很难证明命题。不妨从反面来看问题：观察可以发现，每一步操作都是可逆的。即，我们如果可以把正方形变大，也可以把正方形变小。证明：不妨设四个顶点都是整点。假设我们可以通过有限次操作得到一个边长大于1的正方形，那么我们把所有操作反过来对原正方形进行操作，我们可以得到一个边长小于1的正方形。因为四个顶点都是整点，操作之后，点的坐标依然是整数。所以我们得到一个边长小于1且四个点都是整点的正方形。这显然不可能。所以假设不成立。命题得证。上面的例子说明了逆向思维在数学问题中的应用。第10页共10页 山重水复疑无路，应用逆向思维，换个角度看问题，便柳暗花明又一村了。例一、DinnerIsReadyZhejiangUniversityOnlineJudge1442(acm.zju.edu.cn)题目大意：妈妈烧了M根骨头分给n个孩子们，第i个孩子有两个参数Mini和Maxi，分别表示这个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。输入：第一行包含两个数n(0Maxi。无法计算，但是，可解！！！我们希望把的计算转化到可解的。于是：这是一种容斥原理的形式。至此，问题已经解决。我们应用逆向思维，在原集合的模不可解的情况下，通过可解的得到答案。并给出了一个基于容斥原理的算法。时间复杂度为O(2n*(n+M))。例二、GreedyPathSaratovStateUniversityOnlineJudge236(acm.sgu.ru)题目大意：有n个城市，被m条路连接着。最近成立了一些旅行社，在这些城市之间给旅行者们提供服务。旅行者从城市i到城市j需要付给旅行社的费用是Ci,j，需要的时间为Ti,j。很多旅行者希望加入旅行社，但是旅行社只有一辆车。于是旅行社的老板决定组织一次旅行大赚一笔。公司里的专家需要提供一条使得贪心函数F(G)最大的回路G。F(G)等于总花费除以总时间。但是没有人找到这样的回路，于是公司的领导请你帮忙。输入：第一行包含两个数n(3≤n≤50),m分别表示点数和边数。接下来m行每行包含一条路的描述。输入四个数,A,B,CA,B,TA,B（0≤CA,B≤100，0≤TA,B≤100）输出：如果不存在这样的路，输出0。否则输出回路中包含的城市个数，然后依次输出通过的城市的顺序。如果有很多条这样的路，输出任意一条。初步分析：题目要求是求一条回路，但不是边权和最大或者最小，所以我们不能直接使用经典算法。设G=(V,E)，S为G中所有回路C=(V’,E’)组成的集合。我们的目标是找到集合S中的一条回路使得F(C)取到最大值：应用逆向思维：如果我们知道C*=(V*,E*)S是一条最优回路，那么第10页共10页 于是我们定义函数o(t):o(t)=我们做一个猜想：如果有o(t*)=0，那么存在C*=(V*,E*)S满足我们认为C*就是一条最优回路。证明：假设存在另一条回路C1=(V1,E1)S更优，则：但是这与o(t*)=0矛盾。所以C*是一条最优回路。如果t*是最优答案，则存在：（性质一）于是我们就得到了算法：我们从一个包含t*的区间(tl,th)开始。（例如tl=,th=）每一次，选取tl与th的中点t,计算O(t)。O(t)的计算方法：对于边eE,设一个新的参数We=Ce–t*Te用Floyd算法计算有向图的最大权值环。该最大权值即O(t)。根据性质一，更新tl或th,得到新的上下界，继续二分，直到达到精度要求。假设二分的次数为K,则算法的时间复杂度为O(K*n3)。这虽然不是一个严格的多项式算法，但是对于题目给定的范围，该算法可以很快地求出答案。例三、BuildingTowersUralOnlineJudge1148(acm.timus.ru)第10页共10页 题目大意：有N块积木，我们需要用这些积木造塔。每个塔有H层，最底层包含M块积木；对于上面的每一层，包含的积木块数必须比下面一层的多1或者少1。下图是一个合法的塔(H=6,M=2,N=13)：你的任务是计算一共可以建造出多少种不同的塔（注意积木不一定要全部用完）。两个塔被认为不同，仅当存在一个i（1≤i≤H），两个塔的第i层包含不同数目的积木。我们用H个正整数来表示一个塔的结构（从底部到顶部）。你还需要输出字典序第K小的建塔方案。输入：第一行包含三个整数,N,H,M(N≤32767,H≤60,M≤10)。接下来每行包含一个正整数K（除了最后一行）。最后一行包含一个-1表示输入的结束。输出：第一行包含可以建造的不同的塔的总数。接下来每一行输出对应的字典序第K小的塔的结构。初步分析：首先，看到题目，思维的惯性让我们下意识的想到了经典、传统的动态规划算法。用F[i,j,k]表示当前层有i块砖，还剩下j层，可用的砖块数量为k的方案总数。可以写出动态规划方程为：F[i,j,k]=F[i+1,j+1,k-i]+F[i-1,j+1,k-i]边界条件:F[M,H,N]=1,其他为０很容易看出，这个动态规划方程一共涉及了N*M*K个状态，最大约为60*70*2400=10M。如果每个状态用一个double来保存信息，则至少需要80M的内存（注意，因为我们需要输出字典序第K小的塔，所以我们无法使用滚动储存的优化）。不论是时间复杂度还是空间复杂度，都让人难以接受。至此，动态规划算法失败了。应用逆向思维：自底向上的动态规划在时空上都难以让人承受。我们不妨在处理时“反个方向”，看看自顶向下的搜索算法。搜索算法向来是“低效”、“指数”的代名词。然而，如果加入记忆化因子，则正好是一个“逆向动态规划”的过程。将动态规划的顺序作一个反转，其好处在于：首先，自顶向下的看问题，有“一览众山小”的开阔视野，可以顺利地为如何搜，先搜什么后搜什么，以及如何剪枝等作合理的布局。在本题中，这一点体现为第10页共10页 搜索过程不会搜索到很多荒唐的状态，例如砖块数目明显不够，奇偶性差异等等。而在一些最优化的问题中，搜索记忆化的方法可以有效地配合最优性剪枝，避免许多明显没有价值的状态，而这正是正向的动态规划所不能企及的。第二，在类似于本题的计数问题中，可以采用部分记忆化的方法，即只记录那些比较容易被多次搜索到的状态。这样一来，减少了存储的状态量，加快了查询的速度。实现的时候，我们用三元组（N，H，M）来表示一个状态，即当前层有M块砖，还剩下H层，可用的砖块数量为N。F(N,H,M)表示该状态下的方案数。用Hash表存储，并加入以下一些优化：1）可以事先计算出当前状态最多和最少还需要的砖块数目。如果N小于最小的需求量，那么显然答案为0；如果N大于最大需求量，那么可以把N设置为该最大需求量，以避免等同状态的重复存储。2）如果N不小于最大需求量且H≤M，则答案为2H。3）为了减少存储的状态量，我们设一个存储上界，即仅当F(N,H,M)不大于该上界时才将其存入Hash表。为什么这样做是有效的呢？观察可以发现，搜索的状态树是以指数的形式往下展开的。也就是说，在树越深的地方，状态量会越多，进入查询也越频繁，而接近根的地方，状态的分布比较稀疏，当F(N,H,M)较大时，访问它们的频率就会相应的降低。所以我们可以重复搜索这些状态，从而减少存储状态量，加快Hash表检索速度。我们不妨来看一下“逆向动态规划”的表现：NHM正向动态规划所需要处理的状态数量逆向动态规划中Hash表中所存储的状态量正逆向规划中状态数目的比值1000401012000003055392.801500501026250005371488.741200601028800004987557.741500601036000003801894.69即便是在最坏情况下，逆向动态规划也只需要处理大约1/50的状态。至此，我们已经完美地解决了这个问题。【总结】例一，是一种补集转化的思想，我们对原集合无从下手，转而去求原集合的补集，从反面看问题，得到答案。例二，我们没有去看问题的反面，而是去看一个事实的反面。我们现在不知道答案，如果知道答案又将如何呢？例三，在经典的动态规划无法解决问题的情况下，我们将规划顺序颠倒，得到了逆向动态规划的方法，从而避免许多无效状态，在时间和空间上都取得了质的飞跃。上述三个例子，都是逆向思维的一些简单应用。“正难则反”的逆向思维，帮助我们打破思维定势，以退为进，避其锋芒，攻其软肋。让我们在山重水复疑无路时柳暗花明又一村；第10页共10页 在踏破铁鞋无觅处时得来全不费功夫；让我们在为伊消得人憔悴后蓦然发现那人却在灯火阑珊处。所谓反弹琵琶成新曲，愿逆向思维助你一臂之力，更上一层楼！【感谢】特别感谢安徽芜湖一中周源同学的帮助，感谢所有帮助过我的人。Acm.sgu.ruAcm.timus.ruAcm.zju.edu.cn【参考文献】刘汝佳，黄亮《算法艺术与信息学竞赛》清华大学出版社GunnarW.Klau等《TheFractionalPrize-CollectingSteinerTreeProblemOnTrees》任初农《说说逆向思维》【附件】例三《BuildingTower》一题的源程序Tower.cpp【附录】[例一原题]DinnerIsReadyDinnerisready!WishingBone'sfamilyrushtothetable.WishingBone'smotherhaspreparedmanydeliciousbones.WishingBonehasseveralbrothers,namelyWishingTwoBones,WishingThreeBones.WishingBonewantsatleastonebone,WishingTwoBonestwoandWishingThreeBonesthree.:-PButastheyarenottoogreedy(ortheywanttokeepshape),theydecidethattheywantatmosttwiceoftheirminimalrequirement.Nowlet'ssupposemotherhasprepared7bones,onewaytodistributethemis2-2-3,theothertwowaysare1-3-3and1-2-4.Ofcoursemotherdoesn'twanttowasteanybones,soifshehadprepared13bones,shewouldendupwithoutanyfeasibledistribution.AscuriousasWishingBone,motherwantstoknowhowmanydifferentwaysshecandistributethosebones.InputThefirstlineofinputisapositiveintegerN<=100,whichisthenumberoftestcases.Thefirstlineofeachcasecontainstwointegersnandm(0B).Notethatorderoftownsinrouteissignificant-route(i,j)isnotequaltoroute(j,i).Thereisatmostoneroute(inonedirection)betweenanytwotowns.OutputYoumustoutputrequestedpathGinthefollowingformat.OnthefirstlineofoutputfileyoumustoutputK-numberoftownsinthepath(2<=K<=50),onthesecondline-numbersofthesetownsinorderofpassingthem.Iftherearemanysuchways-outputanyoneofthem,iftherearenosuchways-output"0"(withoutquotes).Sampletest(s)Input第10页共10页 45125123353411415224110Output41234[例三原题]BuildingTowersTimeLimit:2secondMemoryLimit:1000KBThereareNcubesinatoyboxwhichhas1-unitheight,thewidthisdoubletheheight.Theteacherorganizesatower-buildinggame.Thetowerisbuiltbythecubes.TheheightofthetowerisH(hlevels).ThebottomofthetowercontainsMcubes;andforallabovelevel,eachmustcontainsanumberofcubeswhichisexactly1lessthanorgreaterthanthenumberofcubesofthelevelrightbelowit.BelowisanexampleofatowerofH=6,M=2,N=13.Yourtaskistodeterminehowmanydifferenttowerscanbethere.Twotowersareconsidereddifferentifthereisatleastonenumberi(1