1、匹配算法在搜索问题中的巧用 浙江省杭州第十四中学 楼天城很多的题目，如果我们可以建立数学模型，应该尽量用解析法来处理，因为简单的模型更清晰地反映了事物之间的关系。但是，并不是所有的题目都可以建立简单的数学模型。我们这时必须使用搜索的方法，也就是枚举所有可能情况来寻找可行解或最优解。前言由于搜索一般建立在枚举之上，所以搜索常常和低效是分不开的。有时搜索的运算量实在太大，实在是一件痛苦的事情。于是我们需要利用很多技巧来提高效率：可行性剪枝，最优性剪枝，调整搜索顺序，等方法都很有用，在它们的帮助下，我们可以大大提高搜索的效率。而有些题目，这些常规的优化方法很难有用武之地。这是我们必须使用一些非常规的
2、搜索方法。本文中我们将讨论非常规搜索中的一种 部分搜索 +匹配算法引题：N个物品与 N个位置，给定每个物品的可能放的位置集合，要求寻找一一对应的关系。但还给出物品位置之间的限制（例如：如果 1放在 3则 2不能放在 1）。求一组可行解，或给每一种对应关系一个权，求满足条件的最优解。由于事物之间的限制关系非常复杂，很难建立简单的二分图关系，或者用网络流来解决。面对这一系列类似的问题，我们一般只有搜索，如何搜索又如何优化呢？简单分析：如果我们枚举每一个物品的位置，然后判断。这样的时间复杂度为 O(N!)。 好像似乎也只能这样。进一步分析：我们看一个例子， N=6：其它限制有 4条 (a,b,c,d
3、)表示如果 a放在 b则 c不能放在 d1 3 5 62 2 5 33 1 4 13 2 6 2我们发现，如果我们一旦确定了 3和 5的位置，其它 4个物品的位置之间已经没有限制关系了，这样其它 4个物品的位置可以通过匹配来解决。这时我们发现一个新的搜索方法： 部分搜索 +匹配 。 1 3 5 62 2 5 33 1 4 13 2 6 2部分搜索 +匹配：搜索一部分变量，使得余下的变量之间的关系简化，然后通过一些高效算法（匹配）完成余下问题。就本题而言就是：先搜索一定数量（而不是全部）的物品的位置，使问题内其它物品的关系简化为二分图关系，用二分图匹配来解决余下的物品。通过部分搜索为匹配算法提供
4、条件（例如上面的例子创造二分图关系），而匹配算法代替搜索，高效地完成余下的任务。部分搜索 +匹配 的方法充分发挥了搜索和匹配算法的双重优势。搜索的优势在于应用性广，可以克服复杂的情况，匹配算法的优势在于效率高。两者相互促进，同时也弥补对方的不足。这也是这个方法的成功的关键。例如上面的例子，如果我们先知道了 3和 5的位置后，不用匹配，其实我们是在用搜索来求匹配，效率当然不会高。部分搜索 +匹配的方法已经在很多题目中得到了应用。一个部分搜索 +匹配算法的经典例子。题目简述 (NOI2003二试第三题 )B国的连环阵由 M个武器组成。最初， 1号武器处于攻击状态，其他武器都处在无敌自卫状态。以后，一旦第 i（ 1 iM） 号武器被消灭， 1秒钟以后第 i+1号武器就自动从无敌自卫状态变成攻击状态。 A国有 N个炸弹，每个炸弹的作用半径均为 k，且会持续爆炸 5分钟。在这 5分钟内，瞬间消灭离它直线距离不超过 k的、处在攻击状态的 B国武器，不会炸毁本国炸弹。
