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

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

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

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

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

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

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

6、表示沒有牛奶，1表示有牛奶。不幸的是，2*N條記錄的順序被打亂了，有些數(shù)字也模糊不清?，F(xiàn)在史密斯先生請(qǐng)你恢復(fù)原來盒子的牛奶情況。輸入：第一行：一個(gè)整數(shù)N，然后的2N行，每行有N個(gè)數(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)先搜索，依次枚舉每行和每列的記錄編號(hào)，然后判斷是否產(chǎn)生了矛盾。判斷方法：設(shè)：第i條記錄的第j個(gè)數(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。試一試幾個(gè)基本的優(yōu)化：可行性剪枝：除了提前判斷，也沒有什么別的優(yōu)化。最優(yōu)性剪枝：不是最優(yōu)性問