算法合集之《淺談部分搜索+高效算法在搜索問題中的應(yīng)用.pdf

《算法合集之《淺談部分搜索+高效算法在搜索問題中的應(yīng)用.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、IOI2004國家集訓(xùn)隊(duì)論文樓天城淺談部分搜索+高效算法在搜索問題中的應(yīng)用浙江省杭州第十四中學(xué)樓天城摘要：本文從有位置限制的匹配問題的搜索談起，通過對題目MilkBottleData的分析，提出了深度優(yōu)先搜索的一種非常規(guī)搜索——部分搜索+高效算法。然后通過部分搜索在TriangleConstruction和智破連環(huán)陣兩題中的應(yīng)用，探討了部分搜索方法通用的主要優(yōu)化方法，并從此方法本質(zhì)分析其高效的原因所在和應(yīng)用需要滿足的要求和限制。關(guān)鍵字：部分搜索、高效算法正文：很多題目，如果我們可以建立數(shù)學(xué)模型，應(yīng)該盡量用解析法來處理，因?yàn)楹唵蔚哪Ｐ透逦胤从沉耸挛镏g的關(guān)系。但是，并不是所有的

2、題目都可以建立簡單的數(shù)學(xué)模型。我們這時必須使用搜索的方法，也就是枚舉所有可能情況來尋找可行解或最優(yōu)解。由于搜索建立在枚舉之上，所以搜索常常和低效是分不開的。有時搜索的運(yùn)算量實(shí)在太大，實(shí)在是一件痛苦的事情。于是我們需要利用很多技巧來提高效率，可行性剪枝，最優(yōu)性剪枝和調(diào)整搜索順序等方法都很有用，在它們的幫助下，我們可以大大提高搜索的效率。而有些題目，這些常規(guī)的優(yōu)化方法很難有用武之地。這是我們必須使用一些非常規(guī)的搜索方法。本文中我們將討論非常規(guī)搜索中的一種——部分搜索+高效算法。引題：N個物品與N個位置，給定每個物品的可能放的位置集合，要求尋找一一對應(yīng)的關(guān)系，但還給出物品位置之間的限制

3、（例如：如果1放在3則2不能放在1），求一組可行解，或給每一種對應(yīng)關(guān)系一個權(quán)，求滿足條件的最優(yōu)解。由于事物之間的限制關(guān)系非常復(fù)雜，很難建立簡單的二分圖關(guān)系，或者用網(wǎng)絡(luò)流來解決。面對這一系列類似的問題，我們一般只有搜索，如何搜索又如何優(yōu)化呢？簡單分析：如果我們枚舉每一個物品的位置，然后判斷，這樣的時間復(fù)雜度為O(N!)。好像似乎也只能這樣。進(jìn)一步分析：我們看一個例子，N=6：其它限制有4條(a,b,c,d)表示如果a放在b則c不能放在d1356225331413262第1頁共12頁IOI2004國家集訓(xùn)隊(duì)論文樓天城后來我們發(fā)現(xiàn)，如果我們一旦確定了3和5的位置，其它4個物品的位置之間

4、已經(jīng)沒有限制關(guān)系了，這樣其它4個物品的位置可以通過匹配來解決。這時我們可以發(fā)現(xiàn)一個新的搜索模式：部分搜索。部分搜索：搜索一部分變量，使得余下的變量之間的關(guān)系簡化，然后通過一些高效算法（一般有匹配、解方程、貪心、動態(tài)規(guī)劃等）完成余下問題。就本題而言：先搜索一定數(shù)量（而不是全部）的物品的位置，使問題內(nèi)物品的關(guān)系簡化為二分圖關(guān)系，用二分圖匹配來解決余下的物品。本質(zhì)：其實(shí)，例如上面的例子，如果我們先知道了3和5的位置后，不用匹配，其實(shí)我們是在用搜索來求匹配，效率當(dāng)然不會高。通過部分搜索為其它高效算法提供條件（例如上面的例子創(chuàng)造二分圖關(guān)系），而其它高效算法代替搜索，高效地完成余下的任務(wù)。部

5、分搜索的方法充分發(fā)揮了搜索和其它高效算法的優(yōu)勢。搜索的優(yōu)勢在于應(yīng)用性廣，可以克服復(fù)雜的情況，其他高效算法的優(yōu)勢在于效率高。兩者相互促進(jìn)，同時也彌補(bǔ)對方的不足。這也是這個方法的成功的關(guān)鍵。部分搜索+其它高效算法已經(jīng)在很多題目中得到了應(yīng)用。我們通過幾個例子來探討這種搜索方法的應(yīng)用和優(yōu)化技巧。先看一個應(yīng)用的例子。MilkBottleData(ACM/ICPCAsiaRegionalShanghai1996)【問題描述】一個被分為N*N個網(wǎng)格的盒子，每一格有可能包含一瓶牛奶或者什么都沒有。史密斯先生對每行從左到右記下牛奶的情況，同樣對每列從上到下記下牛奶的情況。每一條記錄包含N的數(shù)字，0

6、表示沒有牛奶，1表示有牛奶。不幸的是，2*N條記錄的順序被打亂了，有些數(shù)字也模糊不清。現(xiàn)在史密斯先生請你恢復(fù)原來盒子的牛奶情況。輸入：第一行：一個整數(shù)N，然后的2N行，每行有N個數(shù)字，0表示一定沒有牛奶，1表示一定有牛奶，2表示不能確定。樣例：input501210211202100112110121011210100011222221100110010output98627第2頁共12頁IOI2004國家集訓(xùn)隊(duì)論文樓天城4101101010010101110301001511101數(shù)據(jù)范圍：1<=N<=10初步分析：行列之間的限制關(guān)系非常復(fù)雜，很難找到多項(xiàng)式算法。（網(wǎng)絡(luò)流！？）

7、可以用(2N)!的深度優(yōu)先搜索，依次枚舉每行和每列的記錄編號，然后判斷是否產(chǎn)生了矛盾。判斷方法：設(shè)：第i條記錄的第j個數(shù)字為A[i,j]。如果第a行選擇第x條記錄，第b列選擇第y條記錄，那么矛盾的條件就是：((A[x,b]<>2)and(A[y,a]<>2)and(A[x,b]<>A[y,a]))性能分析（1）：因?yàn)镹<=10，(20)!*10高達(dá)24329020081766400000。試一試幾個基本的優(yōu)化：可行性剪枝：除了提前判斷，也沒有什么別的優(yōu)化。最優(yōu)性剪枝：不是最優(yōu)性問