《算法合集之《浅谈部分搜索+高效算法在搜索问题中的应用 》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈部分搜索+高效算法在搜索问题中的应用 》（12页珍藏版）》请在金锄头文库上搜索。
1、IOI2004 国家集训队论文 楼天城 第 1 页 共 12 页 浅谈部分搜索浅谈部分搜索+高效算法在搜索问题中的应用高效算法在搜索问题中的应用 浙江省杭州第十四中学 楼天城 摘要：摘要： 本文从有位置限制的匹配问题的搜索谈起，通过对题目 Milk Bottle Data 的 分析，提出了深度优先搜索的一种非常规搜索部分搜索+高效算法。然后通 过部分搜索在 Triangle Construction 和智破连环阵两题中的应用，探讨了部分搜 索方法通用的主要优化方法， 并从此方法本质分析其高效的原因所在和应用需要 满足的要求和限制。 关键字：关键字： 部分搜索、高效算法 正文：正文： 很多题目，
2、如果我们可以建立数学模型，应该尽量用解析法来处理，因为简 单的模型更清晰地反映了事物之间的关系。 但是，并不是所有的题目都可以建立简单的数学模型。我们这时必须使用搜 索的方法，也就是枚举所有可能情况来寻找可行解或最优解。 由于搜索建立在枚举之上，所以搜索常常和低效是分不开的。有时搜索的运 算量实在太大，实在是一件痛苦的事情。 于是我们需要利用很多技巧来提高效率，可行性剪枝，最优性剪枝和调整搜 索顺序等方法都很有用，在它们的帮助下，我们可以大大提高搜索的效率。 而有些题目，这些常规的优化方法很难有用武之地。这是我们必须使用一些 非常规的搜索方法。本文中我们将讨论非常规搜索中的一种部分搜索+高效
3、算法。 引题：引题： N 个物品与 N 个位置，给定每个物品的可能放的位置集合，要求寻找一一 对应的关系，但还给出物品位置之间的限制（例如：如果 1 放在 3 则 2 不能放在 1） ，求一组可行解，或给每一种对应关系一个权，求满足条件的最优解。 由于事物之间的限制关系非常复杂，很难建立简单的二分图关系，或者用网 络流来解决。 面对这一系列类似的问题，我们一般只有搜索，如何搜索又如何优化呢？ 简单分析： 如果我们枚举每一个物品的位置，然后判断，这样的时间复杂度为 O(N!)。 好像似乎也只能这样。 进一步分析： 我们看一个例子，N=6： 其它限制有 4 条(a,b,c,d)表示如果 a 放在
4、b 则 c 不能放在 d 1 3 5 6 2 2 5 3 3 1 4 1 3 2 6 2 IOI2004 国家集训队论文 楼天城 第 2 页 共 12 页 后来我们发现，如果我们一旦确定了 3 和 5 的位置，其它 4 个物品的位置之 间已经没有限制关系了，这样其它 4 个物品的位置可以通过匹配来解决。 这时我们可以发现一个新的搜索模式：部分搜索。 部分搜索：搜索一部分变量，使得余下的变量之间的关系简化，然后通过部分搜索：搜索一部分变量，使得余下的变量之间的关系简化，然后通过 一些高效算法（一般有匹配、解方程、贪心、动态规划等）完成余下问题。一些高效算法（一般有匹配、解方程、贪心、动态规划等）
5、完成余下问题。 就本题而言：先搜索一定数量（而不是全部）的物品的位置，使问题内物品 的关系简化为二分图关系，用二分图匹配来解决余下的物品。 本质：本质： 其实，例如上面的例子，如果我们先知道了 3 和 5 的位置后，不用匹配，其 实我们是在用搜索来求匹配，效率当然不会高。 通过部分搜索为其它高效算法提供条件（例如上面的例子创造二分图关通过部分搜索为其它高效算法提供条件（例如上面的例子创造二分图关 系） ，而其它高效算法代替搜索，高效地完成余下的任务。系） ，而其它高效算法代替搜索，高效地完成余下的任务。 部分搜索的方法充分发挥了搜索和其它高效算法的优势。搜索的优势在于部分搜索的方法充分发挥了搜
6、索和其它高效算法的优势。搜索的优势在于 应用性广，可以克服复杂的情况，其他高效算法的优势在于效率高。两者相互应用性广，可以克服复杂的情况，其他高效算法的优势在于效率高。两者相互 促进，同时也弥补对方的不足。这也是这个方法的成功的关键。促进，同时也弥补对方的不足。这也是这个方法的成功的关键。 部分搜索+其它高效算法已经在很多题目中得到了应用。我们通过几个例子 来探讨这种搜索方法的应用和优化技巧。 先看一个应用的例子。 Milk Bottle Data (ACM/ICPC Asia Regional Shanghai 1996) 【问题描述】【问题描述】 一个被分为N*N个网格的盒子， 每一格有可
7、能包含一瓶牛奶或者什么都没有。 史密斯先生对每行从左到右记下牛奶的情况， 同样对每列从上到下记下牛奶的情 况。每一条记录包含N的数字，0表示没有牛奶，1表示有牛奶。不幸的是，2*N 条记录的顺序被打乱了，有些数字也模糊不清。 现在史密斯先生请你恢复原来盒子的牛奶情况。 输入： 第一行：一个整数N，然后的2N行，每行有N个数字，0表示一定没有牛奶，1 表示一定有牛奶，2表示不能确定。 样例： input 5 01210 21120 21001 12110 12101 12101 00011 22222 11001 10010 output 9 8 6 2 7 IOI2004 国家集训队论文 楼天
8、城 第 3 页 共 12 页 4 1 0 1 1 0 10 1 0 0 1 0 1 0 1 1 1 0 3 0 1 0 0 1 5 1 1 1 0 1 数据范围：12) and (Ay,aAy,a) 性能分析（性能分析（1） ：） ： 因为 N=Si,Ti+1=Si+1)。然后判断是否可以从A国的N颗炸弹中选出x 颗，分别可以炸掉其中的一段。 其实我们把搜索分为了两部分，先通过搜索将B国武器根据编号分为x段，再IOI2004 国家集训队论文 楼天城 第 6 页 共 12 页 通过搜索判断是否可以从A国的N颗炸弹中选出x颗，分别可以炸掉其中的一段。 其实第二部分可以用匹配来解决。 CSTI 表示
9、A国炸弹I是否可以炸到B国武器S,S+1.T-1,T。 CSSI=(uI-xS)2+(vI-yS)2=当前找到 的最优解 then 剪枝； 优化二（可行性） ： 此搜索方法一般都可以用两个效果很好的可行性优化：此搜索方法一般都可以用两个效果很好的可行性优化： (1)提前判断是否可以匹配成功，避免多余的搜索。提前判断是否可以匹配成功，避免多余的搜索。 (2)每次匹配可以从以前的匹配开始扩展，不需要重新开始。每次匹配可以从以前的匹配开始扩展，不需要重新开始。 如果当前的划分方法已经无法匹配成功，就没有搜索下去的必要了，只要每 搜索新的一段时立即通过匹配判断即可。 每次求匹配只要从原来的基础上扩展就
10、可以了。 通过上述两个优化，程序的效率有了很大的提高。 性能分析（性能分析（2） ：） ： 虽然通过上述两个优化，程序的效率较原来的搜索有了很大的提高。10个测 试数据中有8个可以在时限内出解，另外2个如果卡时，有1个也可以得到最优解。 进一步优化：进一步优化： 优化二虽然排除了许多不必要的划分，但是在判断时浪费了不少时间。 因此，在枚举划分长度时，可以通过以前的划分和匹配情况（被匹配的边） ， 用O(n2)的时间复杂度的宽度优先搜索计算出下一个划分的最大长度maxL，显然下一个划分的长度在1，maxL都一定可以找到可行的匹配。这样既节省了判断 的时间，又可以使每次划分长度从长到短枚举，使程序
11、尽快逼近最优解，同时增IOI2004 国家集训队论文 楼天城 第 7 页 共 12 页 强了剪枝条件一的效果。 这一部分的实现，首先需要求MaxT。 MaxTIS=炸弹i，从S开始炸，可以炸到的最大编号。 如果，炸弹i炸不到S，则MaxTIS=S-1。 求 MaxTIS可以用动态规划的方法解决。状态转移方程为： MaxTIS= 炸弹 i 炸不到 S S-1 炸弹 i 炸得到 S MaxTiS+1 MaxTim+1=m 求MaxT的时间复杂度为O(N2)。 具体实现方法， 考虑二分图右边的n个结点 （n颗炸弹） ， 如果结点i没有匹配， i被认为可以使用。对于一个已经匹配的结点i，如果从任何一个
12、没有匹配的结点 出发存在一条到达i，而且i为外点的交错路，i也被认为可以使用。 计算所有从没有匹配点出发的交错路（没有匹配点i出发的交错路没有被匹 配点i一定为外点）所能到达的匹配的结点，只要从每一个没有匹配的结点出发， 宽度优先搜索，只要O(N2)的时间。注意判断重复（如果一个已经匹配的结点已经被确定为可以使用，那么不需要对它再扩展一次，因为当把这个已经匹配的结 点确定为可以使用的结点的时候，已经从这个结点扩展过，如果再扩展必将产生 无谓的重复） 所以MaxL=Max(MaxTIS | i可以使用)； 性能分析（性能分析（3） ：） ： 通过以上的优化，所有数据都是瞬间出解，并且所有结果都是
13、最优解。 甚至对 n=200 的随机数据，也可以在瞬间出解，可见程序的效率有了很大的 提高。 精益求精：精益求精： 另外，还有两个优化，但是有时效果不好，但也值得一提。 优化三：分支定界。这样可以增强剪枝条件一的效果，但是当最优解与 Dist1相差比较远的时候，会浪费一定的时间。 优化四：优化一中 Disti的值有时并不是最优的，通过测试，发现如果 Disti的值与最优值相差 1，特别是当 i 小的时候，程序的速度都会有明显的 影响。所以，可以通过同样的搜索来计算 Disti， （本题的答案就是 Dist1） 。 这样做可以增强剪枝条件一的效果， 但是同时对每个 i 都要搜索也浪费了一定的 时
14、间。 程序结果比较：程序结果比较： 1 2 3 4 5 6 7 8 9 10 最简单的 搜索 0.00 0.00 0.50 Time Over 0.65 Time Over Time Over Time Over Time Over Time Over 优化的搜 索 0.01 0.01 0.10 Time Over 0.50 0.80 Time Over 0.55 0.30 0.80 进一步优 化的搜索 0.01 0.01 0.02 0.03 0.00 0.02 0.02 0.01 0.02 0.02 此搜索方法一般都可以用两个效果很好的可行性优化：此搜索方法一般都可以用两个效果很好的可行性优
15、化： (1)提前判断是否可以成功，避免多余的搜索。提前判断是否可以成功，避免多余的搜索。 (2)每次判断尽量多利用以前的判断结果。每次判断尽量多利用以前的判断结果。 IOI2004 国家集训队论文 楼天城 第 8 页 共 12 页 总结：总结： 本文中的几个例子都可以应用部分搜索的方法高效解决， 它们在思想上有着 明显的相同点。一般的思维过程如下： 一般的优化包括： （1） 选择好的枚举变量， 使枚举的变量数量尽可能少。 （2） 尽可能充分利用以前的结果，提前判断，避免多余的搜索。 部分搜索同样可以和解方程、贪心、动态规划等高效算法结合。 部分搜索高效算法体现了搜索与其他方法的有机结合， 充分
16、发挥两者的长 处，相互弥补对方的不足，这就是其高效的主要原因所在。因此，在搜索问题中 灵活地应用部分搜索的方法，往往可以创造出奇效。 值得注意的是，部分搜索来解决搜索问题作为一种非常规的搜索方法。虽然 在本文的例子中，部分搜索有着很多的过人之处，但是并不能认为常规方法一定 不如非常规方法。大多数的搜索问题还是适合用常规的搜索方法的，所以只有充 分把握部分搜索的特点，使之与常规的搜索融会贯通，才能真正得到高效的搜索 算法。 参考文献：参考文献： ACM/ICPC Asia Regional Shanghai 1996 (Milk Bottle Data) ZJU Monthly Contest(Triangle Constru
