算法合集之《匹配算法在搜索问题中的应用 》.ppt

匹配算法在搜索问题中的应用浙江省杭州第十四中学楼天城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(1i<M)号武器被消灭,1秒钟以后第i+1号武器就自动从无敌自卫状态变成攻击状态。 A国有N个炸弹,每个炸弹的作用半径均为k,且会持续爆炸5分钟。在这5分钟内,瞬间消灭离它直线距离不超过k的、处在攻击状态的B国武器,不会炸毁本国炸弹。庐积猎叮褥荣怎剔蒜驾亦署览哭恕凄震镜言澡美第寒饺这瀑协狸蒙偏沸节算法合集之《匹配算法在搜索问题中的应用》算法合集之《匹配算法在搜索问题中的应用》