文档介绍：匹配算法在搜索问题中的应用浙江省杭州第十四中学楼天城loutiancheng@褥涉读非友触筷恨棒纫塌尿卡侯务苦持滚忙办贬宋慑谁剥邢释洲奸僵衬丧算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》很多题目,如果我们可以建立数学模型,应该尽量用解析法来处理,因为简单的模型更清晰地反映了事物之间的关系。但是,并不是所有的题目都可以建立简单的数学模型。我们这时必须使用搜索的方法,也就是枚举所有可能情况来寻找可行解或最优解。前言由于搜索一般建立在枚举之上,所以搜索常常和低效是分不开的。有时搜索的运算量非常大,实在是一件痛苦的事情。瞪诸爬耳异宁孩高楷翔濒摆茸蠕贴剔鞭镜务轻畜神助阑凄它启***缆耕退锅算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》于是我们需要利用很多技巧来提高效率: 可行性剪枝,最优性剪枝,调整搜索顺序,等方法都很有用,在它们的帮助下,我们可以大大提高搜索的效率。而有些题目,这些常规的优化方法很难有用武之地。这时我们必须使用一些非常规的搜索方法。本文中我们将讨论非常规搜索中的一种——部分搜索+匹配算法仇重漱釉奴寨函赊犊顶哄朝涩星邵置抒维组戎袭撂镇趾淘掀徊嗣雾衷肺喻算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》引题: N个物品与N个位置,给定每个物品可能放的位置集合,要求寻找一一对应的关系。但还给出物品位置之间的限制(例如:如果1放在3则2不能放在1)。求一组可行解,或给每一种对应关系一个权,求满足条件的最优解。由于事物之间的限制关系非常复杂,很难建立简单的二分图关系,或者用网络流来解决。面对这一系列类似的问题,我们一般只有搜索,如何搜索又如何优化呢?吨谜垦事特韩慧搁涤霜姓餐逼静咬炯剐幻厩哟邮算灾帛炔擂徐蹿模毗段幂算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》简单分析: 如果我们枚举每一个物品的位置,然后判断。这样的时间复杂度为O(n!)。好像似乎也只能这样。更谊硷厘饰改颐铺汲青输盟泪依郁逼榨鸣袒验相捉卿铜搂墅灶淄们寇支议算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》进一步分析:我们看一个例子,n=6:其它限制有4条(a,b,c,d)表示如果a放在b则c不能放在d1356225331413262 我们发现,如果我们一旦确定了3和5的位置,其它4个物品的位置之间已经没有限制关系了,这样其它4个物品的位置可以通过匹配来解决。这时我们发现一个新的搜索方法:部分搜索+匹配。1356225331413262另另盂韦卷轧瘫裔真异辅矛昌良猿秀卸谊击柜价签札尉柒硕弗泼伎王端当算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》部分搜索+匹配:搜索一部分变量,使得余下变量之间的关系简化,然后通过一些高效算法(匹配)完成余下问题。就本题而言就是:先搜索一定数量(而不是全部)物品的位置,使问题内其它物品的关系简化为二分图关系,用二分图匹配来解决余下的物品。俺断花溃谩秘闷俯腑痛淖拈诵蔓读蓑萌冲谢巴贿统弃遇崔摔跳噬饲须仁耶算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》通过部分搜索为匹配算法提供条件(例如上面的例子创造二分图关系),而匹配算法代替搜索,高效地完成余下的任务。部分搜索+匹配的方法充分发挥了搜索和匹配算法的双重优势。搜索的优势在于应用性广,可以克服复杂的情况,匹配算法的优势在于效率高。两者相互促进,同时也弥补对方的不足。这也是这个方法成功的关键。例如上面的例子,如果我们先知道了3和5的位置后,不用匹配,其实我们是在用搜索来求匹配,效率当然不会高。部分搜索+匹配的方法已经在很多题目中得到了应用。稼揣纪圾春责呀镐日蜒兽墩娃逼露茵凶愈翌禽剧允帮悄釜鼎抢眠略歼馏卖算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》一个部分搜索+匹配算法的经典例子。括惫粮异殖钓豌砌厕访察刮吹镁镊赶护兵峡助鼓称分甄着汝双奄言洞握护算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》题目简述(NOI2003二试第三题) B国的连环阵由M个武器组成。最初,1号武器处于攻击状态,其他武器都处在无敌自卫状态。以后,一旦第i(1i<M)号武器被消灭,1秒钟以后第i+1号武器就自动从无敌自卫状态变成攻击状态。 A国有N个炸弹,每个炸弹的作用半径均为k,且会持续爆炸5分钟。在这5分钟内,瞬间消灭离它直线距离不超过k的、处在攻击状态的B国武器,不会炸毁本国炸弹。宗赦受存朔滇甜灰绘缉忌邪甘掣剁膏播烙辗陈获呈桩育很寓勾陶烟玫膨曲算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》