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