论文国家队楼天城

《论文国家队楼天城》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈部分搜索+高效算法在搜索问题中的应用浙江省杭州第十四中学楼天城摘要：木文从有位置限制的匹配问题的搜索谈起，通过对题口MilkBottleData的分析，提岀了深度优先搜索的一种非常规搜索——部分搜索+高效算法。然后通过部分搜索在TriangleConstruction和智破连环阵两题中的应用，探讨了部分搜索方法通用的主耍优化方法，并从此方法本质分析其高效的原因所在和应用需耍满足的要求和限制。关键字：部分搜索、高效算法正文：很多题冃，如果我们可以建立数学模型，应该尽量用解析法来处理，因为简单的模型更清晰地反映了事物之间的关系。但是，并不是所有的题目都可以建立简单的数学模型。我们这

2、时必须使用搜索的方法，也就是枚举所有可能情况來寻找可行解或最优解。出于搜索建立在枚举之上，所以搜索常常和低效是分不开的。有时搜索的运算量实在太人，实在是一件痛苦的事情。于是我们需要利用很多技巧来提高效率，可行性剪枝，最优性剪枝和调整搜索顺序等方法都很有用，在它们的帮助下，我们可以大大提高搜索的效率。而有些题目，这些常规的优化方法很难有用武Z地。这是我们必须使用一些非常规的搜索方法。本文中我们将讨论非常规搜索中的一种——部分搜索+高效算法。引题：N个物品与N个位置，给定每个物品的可能放的位置集合，要求寻找一一对应的关系，但还给出物品位置Z间的限制(例如：如果1放在3则2不能放在1),

3、求一组可行解，或给每一种对应关系一个权，求满足条件的最优解。由于事物Z间的限制关系非常复杂，很难建立简单的二分图关系，或者用网络流來解决。面对这一系列类似的问题，我们一般只有搜索，如何搜索又如何优化呢？简单分析：如果我们枚举每一个物品的位置，然后判断，这样的时间复朵度为0(N!)o好像似乎也只能这样。进一步分析：我们看一个例了，N=6：其它限制有4条(a,b,c,d)表示如果a放在b则c不能放在d1356225331413262第1页共12页后来我们发现，如果我们一旦确定了3和5的位置，其它4个物品的位置之间已经没有限制关系了，这样其它4个物品的位置可以通过匹配来解决。这时我们可以

4、发现一个新的搜索模式：部分搜索。部分搜索：搜索一部分变量，使得余下的变量之间的关系简化，然后通过一些高效算法（般有匹配、解方程、贪心、动态规划等）完成余下问题。就本题而言：先搜索一定数量（而不是全部）的物品的位置，使问题内物品的关系简化为二分图关系，用二分图匹配來解决余下的物品。本质：其实，例如上面的例子，如果我们先知道了3和5的位置后，不用匹配，其实我们是在用搜索来求匹配，效率当然不会高。通过部分搜索为其它高效算法提供条件（例如上面的例子创造二分图关系），而其它高效算法代替搜索，高效地完成余下的任务。部分搜索的方法充分发挥了搜索和其它高效算法的优势。搜索的优势在于应用性广，可以克

5、服复杂的情况，其他高效算法的优势在于效率高。两者相互促进，同时也弥补对方的不足。这也是这个方法的成功的关键。部分搜索+其它高效算法已经在很多题H中得到了应用。我们通过几个例子来探讨这种搜索方法的应用和优化技巧。先看一个应用的例子。MilkBottleData（ACM/ICPCAsiaRegionalShanghai1996）【问题描述】一个被分为N*N个网格的盒子，每一格有可能包含一瓶牛奶或者什么都没有。史密斯先生对每行从左到右记下牛奶的情况，同样对侮列从上到下记下牛奶的情况。侮一条记录包含N的数字，0表示没有牛奶，1表示有牛奶。不幸的是，2*N条记录的顺序被打乱了，有些数字也模糊

6、不清。现在史密斯先生请你恢复原来盒子的牛奶情况。输入：第一行：一个整数N,然后的2N行，每行有N个数字，0表示一定没有牛奶，1表示一定有牛奶，2表示不能确定。样例：input501210211202100112110121011210100011222221100110010output98627第2页共12页4101101010010101110301001511101数据范围：l<=N<=10初步分析：行列Z间的限制关系非常复杂，很难找到多项式算法。(网络流！？)可以用(2N)!的深度优先搜索，依次枚举每行和每列的记录编号，然后判断是否产生了矛盾。判断方法：设：第i条记录的第j

7、个数字为A[i,j]。如果第a行选择第x条记录，第b列选择第y条记录，那么矛盾的条件就是:((A[x,b]02)and(A[y,a]02)and(A[x,b]OA[y,a]))性能分析(1)：因为N<=10,(20)!*10高达24329020081766400000c试一试几个基本的优化：可行性剪枝：除了捉前判断，也没有什么别的优化。最优性剪枝：不是最优性问题。调整搜索顺序：如果每次搜索可能性最少的，效果还是不错的。但是最坏情况需要计算(20)!的运算量，实在不能说