試題、程序及解題報(bào)告樓天城

第13頁(yè)共13頁(yè)第12頁(yè)共1頁(yè)P(yáng)AGE8淺談部分搜索+高效算法在搜索問題中的應(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)系。但是，并不是所有的題目都可以建立簡(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)系，但還給出物品位置之間的限制（例如：如果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后來我們發(fā)現(xiàn)，如果我們一旦確定了3和5的位置，其它4個(gè)物品的位置之間已經(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ù)。部分搜索的方法充分發(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表示沒有牛奶，1表示有牛奶。不幸的是，2*N條記錄的順序被打亂了，有些數(shù)字也模糊不清?，F(xiàn)在史密斯先生請(qǐng)你恢復(fù)原來盒子的牛奶情況。輸入：第一行：一個(gè)整數(shù)N，然后的2N行，每行有N個(gè)數(shù)字，0表示一定沒有牛奶，1表示一定有牛奶，2表示不能確定。樣例：input501210211202100112110121011210100011222221100110010output

9862741011010

1

0

0

1

010

1

1

1

030

1

0

0

15

1

1

1

0

1數(shù)據(jù)范圍：1<=N<=10初步分析：行列之間的限制關(guān)系非常復(fù)雜，很難找到多項(xiàng)式算法。（網(wǎng)絡(luò)流?。浚┛梢杂?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)性問題。調(diào)整搜索順序：如果每次搜索可能性最少的，效果還是不錯(cuò)的。但是最壞情況需要計(jì)算(20)!的運(yùn)算量，實(shí)在不能說是個(gè)好的可行算法。部分搜索＋匹配算法我們可以發(fā)現(xiàn)行與行之間和列與列之間不存在約束關(guān)系，所有的約束關(guān)系都在行列之間。我們可不可以只搜索行呢？答案是肯定的。如果我們已經(jīng)知道了每行的值，列與列之間已經(jīng)沒有約束關(guān)系。我們當(dāng)然可以用匹配來求出一組可行解。建圖方法：二分圖左邊N個(gè)點(diǎn)表示N個(gè)沒有被選擇的N條記錄，右邊N個(gè)點(diǎn)表示N列。如果將左邊第i個(gè)結(jié)點(diǎn)對(duì)應(yīng)編號(hào)的記錄放入第j列，在第j列的每一行都不會(huì)產(chǎn)生矛盾,就在左邊第i個(gè)結(jié)點(diǎn)和右邊第j結(jié)點(diǎn)之間添一條邊。二分圖匹配可以在O(N3)的時(shí)間內(nèi)解決，比盲目搜索的效果好很多。性能分析（2）：這樣N=10時(shí)的運(yùn)算量為P(20,10)*(20*10*10)=13408850145600000。效率與簡(jiǎn)單搜索相比已有很大的提高。因?yàn)橹灰业揭唤M解就可以結(jié)束程序，所以可以很快地通過所有測(cè)試數(shù)據(jù)?？偨Y(jié)：我們可以這樣比較兩個(gè)算法，如果普通的搜索是先搜索行再搜索列，那么在搜索完行以后，它是在用搜索來找匹配。搜索的復(fù)雜度為O(N!)，而匹配的復(fù)雜度為O(N3)。搜索的效率不言而喻.本搜索算法依然可以使用幾個(gè)常規(guī)優(yōu)化。特殊的搜索方法和常規(guī)的優(yōu)化還是不矛盾的。本算法還有很多獨(dú)特優(yōu)化，我們結(jié)合兩個(gè)例子講起。例一：TriangleConstruction(ZJUMonthlyContest)【問題描述】一個(gè)邊長(zhǎng)為N的等邊三角形可以被分為N*N個(gè)邊長(zhǎng)為1的小的等邊三角形，如圖：

我們注意到相鄰的兩條邊必須是同一種顏色，現(xiàn)在給出這n*n個(gè)三角形的三條邊的顏色，請(qǐng)你判斷是否可以用這n*n個(gè)三角形構(gòu)成一個(gè)邊長(zhǎng)為n的等邊三角形。這里只考慮n=4的情況。分析：直接搜索運(yùn)算量達(dá)16!=20922789888000，實(shí)在太高了。其實(shí)，這個(gè)問題也就是一個(gè)16個(gè)物體的有位置限制的匹配問題。與引題的區(qū)別就是：位置之間的限制是確定的，我們必須充分利用這一特點(diǎn)。使用部分搜索＋匹配的算法，我們?nèi)绾嗡阉髂?？我們?dāng)然應(yīng)該選擇效率最高的方法。假設(shè)枚舉的三角形的數(shù)量為T，則運(yùn)算量為P(16,T)*256*(16-T)。T運(yùn)算量T運(yùn)算量0409697439214182400161440104463528509440028601601122317642547200031118208012892705701888000413418496013267811710566400051476034560145356234211328000614760345600155356234211328000713284311040016?81062744883200結(jié)論：運(yùn)算量隨T的增加而遞增。此類問題，一般情況下，枚舉的變量數(shù)量越少越好。優(yōu)化：選擇好的枚舉變量，使枚舉的變量數(shù)量盡可能少。對(duì)于此題，我們可以枚舉陰影部分的6塊，其它10塊都可以建立簡(jiǎn)單的二分圖關(guān)系。運(yùn)算量為P(16,6)*256*10加上常規(guī)的優(yōu)化效率有了很大的提高?？偨Y(jié)：搜索變量的選擇：一般以搜索變量的數(shù)目盡可能少為原則，因?yàn)楦咝惴ǖ男适嵌囗?xiàng)式級(jí)別的，但是搜索是NP的。選擇方法：有時(shí)可以通過分析，例如上述兩題；但有的題目需要程序來確定搜索的變量。例二：智破連環(huán)陣(NOI2003)（一個(gè)部分搜索法優(yōu)化的經(jīng)典例子。）【問題描述】B國(guó)在耗資百億元之后終于研制出了新式武器——連環(huán)陣(ZenithProtectedLinkedHybridZone)，并聲稱這是一種無敵的自發(fā)性智能武器。但A國(guó)經(jīng)偵察發(fā)現(xiàn)，連環(huán)陣其實(shí)是由M個(gè)獨(dú)立武器組成的。這M個(gè)武器編號(hào)為1，2，…，M。每件武器有兩種狀態(tài)：無敵自衛(wèi)狀態(tài)和攻擊狀態(tài)。最初，1號(hào)武器處于攻擊狀態(tài)，其他武器都處在無敵自衛(wèi)狀態(tài)。以后，一旦第I(1i<M）號(hào)武器被消滅，1秒鐘以后第i+1號(hào)武器就自動(dòng)從無敵自衛(wèi)狀態(tài)變成攻擊狀態(tài)。當(dāng)?shù)贛號(hào)武器被消滅以后，這個(gè)造價(jià)昂貴的連環(huán)陣就被徹底摧毀了。為了打敗B國(guó)，A國(guó)軍事部長(zhǎng)打算用最廉價(jià)的武器——炸彈來消滅連環(huán)陣。經(jīng)過長(zhǎng)時(shí)間的精密探測(cè)，A國(guó)的軍事家們掌握了連環(huán)陣中M個(gè)武器的平面坐標(biāo)，然后依此選擇了n個(gè)點(diǎn)，并在這些點(diǎn)上安放了特殊的定時(shí)炸彈。這n個(gè)炸彈編號(hào)為1，2，…，n。每個(gè)炸彈的作用半徑均為k，且會(huì)持續(xù)爆炸5分鐘。在這5分鐘內(nèi)，每枚炸彈都可以在瞬間消滅離它直線距離不超過k的、處在攻擊狀態(tài)的B國(guó)武器。和連環(huán)陣類似，最初a1號(hào)炸彈持續(xù)引爆5分鐘時(shí)間，然后a2號(hào)炸彈持續(xù)引爆5分鐘時(shí)間，接著a3號(hào)炸彈引爆……以此類推，直到連環(huán)陣被摧毀。在每個(gè)炸彈爆炸的時(shí)候，其它尚未引爆的炸彈都處于地下隱蔽處，不會(huì)被己方的炸彈摧毀。顯然，選好a1、a2、a3...十分重要。好的序列可以在僅使用較少炸彈的情況下就能將連環(huán)陣摧毀；壞的序列可能在使用完所有炸彈后仍無法將連環(huán)陣摧毀?，F(xiàn)在，請(qǐng)你決定一個(gè)序列a1、a2、a3…使得在第ax號(hào)炸彈引爆的時(shí)間內(nèi)連環(huán)陣被摧毀。這里的x應(yīng)當(dāng)盡量小?！据斎胛募枯斎胛募plhz.in第一行包含三個(gè)整數(shù)：M、n和k（1M,n100，1k1000），分別表示B國(guó)連環(huán)陣由M個(gè)武器組成，A國(guó)有n個(gè)炸彈可以使用，炸彈攻擊范圍為k。以下M行，每行由一對(duì)整數(shù)xi，yi（0xi，yi10000）組成，表示第i（1iM）號(hào)武器的平面坐標(biāo)。再接下來n行，每行由一對(duì)整數(shù)ui，vi(0ui，vi10000)組成，表示第i（1in）號(hào)炸彈的平面坐標(biāo)。輸入數(shù)據(jù)保證無誤和有解。測(cè)試數(shù)據(jù)中的xi、yi、ui、vi是隨機(jī)生成的?！据敵鑫募枯敵鑫募plhz.out的第一行包含一個(gè)整數(shù)x，表示實(shí)際使用的炸彈數(shù)。第二行包括x個(gè)整數(shù)，依次表示a1，a2，…，ax。初步分析：A國(guó)炸彈I可以炸到B國(guó)武器J的條件:(u[i]-x[j])2+(v[i]-y[j])2<=r2結(jié)論：很難找到求最優(yōu)解的多項(xiàng)式算法。面對(duì)此類問題，一般只有搜索策略。進(jìn)一步分析：每一顆炸彈必定炸掉B國(guó)武器中編號(hào)連續(xù)的一段。5分鐘只是表明每一顆炸彈可以炸掉任意多個(gè)編號(hào)連續(xù)的B國(guó)武器。部分搜索：此題使用部分搜索的算法需要一些轉(zhuǎn)化：如果已經(jīng)將B國(guó)武器根據(jù)編號(hào)分為x段，[Si,Ti](S1=1,Ti>=Si,Ti+1=Si+1)。然后判斷是否可以從A國(guó)的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實(shí)我們把搜索分為了兩部分，先通過搜索將B國(guó)武器根據(jù)編號(hào)分為x段，再通過搜索判斷是否可以從A國(guó)的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實(shí)第二部分可以用匹配來解決。C[S][T][I]表示A國(guó)炸彈I是否可以炸到B國(guó)武器S,S+1..T-1,T。C[S][S][I]=((u[I]-x[S])2+(v[I]-y[S])2<=R2)C[S][T][I]=C[S][T-1][I]&C[T][T][I](S<T)求C的時(shí)間復(fù)雜度為O(N3)。建圖：左邊x個(gè)點(diǎn)，表示B國(guó)武器根據(jù)編號(hào)分為的x段，右邊N個(gè)點(diǎn)，表示A國(guó)的N顆炸彈。左邊第i個(gè)點(diǎn)到右邊第j個(gè)點(diǎn)有邊的條件即：C[Si][Ti][j]。搜索的任務(wù)就是將B國(guó)武器根據(jù)編號(hào)劃分為若干段+二分圖匹配判斷。性能分析（1）：搜索的基本框架已經(jīng)建立，雖然數(shù)據(jù)是隨機(jī)生成的，但是M個(gè)B國(guó)武器的劃分方案還是非常多的，有時(shí)可能高達(dá)2m。時(shí)間上很難承受，如果使用卡時(shí)，正確性受到影響，效果不會(huì)很好。只有4個(gè)數(shù)據(jù)可以在時(shí)限內(nèi)出解，另外6個(gè)如果卡時(shí)，有1個(gè)也可以得到最優(yōu)解。優(yōu)化：優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。優(yōu)化一（最優(yōu)性）：如果A國(guó)炸彈可以重復(fù)使用，設(shè)：Dist[i]=炸掉B國(guó)武器i－m的最少使用炸彈數(shù)?？梢杂脛?dòng)態(tài)規(guī)劃計(jì)算Dist值，狀態(tài)轉(zhuǎn)移方程如下：Dist[m+1]=0。Dist[i]=Min(Dist[j]+1|Can[i][j-1][k](1<=k<=n))(1<=i<=n)(i<j<=n+1)求Dist的時(shí)間復(fù)雜度為O(N3)。從而產(chǎn)生了一個(gè)最優(yōu)性剪枝條件：if當(dāng)前已經(jīng)使用的炸彈數(shù)+Dist[當(dāng)前已經(jīng)炸掉的B國(guó)武器數(shù)+1]>=當(dāng)前找到的最優(yōu)解then剪枝；優(yōu)化二（可行性）：此搜索方法一般都可以用兩個(gè)效果很好的可行性優(yōu)化：(1)提前判斷是否可以匹配成功，避免多余的搜索。(2)每次匹配可以從以前的匹配開始擴(kuò)展，不需要重新開始。如果當(dāng)前的劃分方法已經(jīng)無法匹配成功，就沒有搜索下去的必要了，只要每搜索新的一段時(shí)立即通過匹配判斷即可。每次求匹配只要從原來的基礎(chǔ)上擴(kuò)展就可以了。通過上述兩個(gè)優(yōu)化，程序的效率有了很大的提高。性能分析（2）：雖然通過上述兩個(gè)優(yōu)化，程序的效率較原來的搜索有了很大的提高。10個(gè)測(cè)試數(shù)據(jù)中有8個(gè)可以在時(shí)限內(nèi)出解，另外2個(gè)如果卡時(shí)，有1個(gè)也可以得到最優(yōu)解。進(jìn)一步優(yōu)化：優(yōu)化二雖然排除了許多不必要的劃分，但是在判斷時(shí)浪費(fèi)了不少時(shí)間。因此，在枚舉劃分長(zhǎng)度時(shí)，可以通過以前的劃分和匹配情況（被匹配的邊），用O(n2)的時(shí)間復(fù)雜度的寬度優(yōu)先搜索計(jì)算出下一個(gè)劃分的最大長(zhǎng)度maxL，顯然下一個(gè)劃分的長(zhǎng)度在[1，maxL]都一定可以找到可行的匹配。這樣既節(jié)省了判斷的時(shí)間，又可以使每次劃分長(zhǎng)度從長(zhǎng)到短枚舉，使程序盡快逼近最優(yōu)解，同時(shí)增強(qiáng)了剪枝條件一的效果。這一部分的實(shí)現(xiàn)，首先需要求MaxT。MaxT[I][S]=炸彈i，從S開始炸，可以炸到的最大編號(hào)。如果，炸彈i炸不到S，則MaxT[I][S]=S-1。求MaxT[I][S]可以用動(dòng)態(tài)規(guī)劃的方法解決。狀態(tài)轉(zhuǎn)移方程為：MaxT[I][S]=炸彈i炸不到SS-1炸彈i炸得到SMaxT[i][S+1]MaxT[i][m+1]=m求MaxT的時(shí)間復(fù)雜度為O(N2)。具體實(shí)現(xiàn)方法，考慮二分圖右邊的n個(gè)結(jié)點(diǎn)（n顆炸彈），如果結(jié)點(diǎn)i沒有匹配，i被認(rèn)為可以使用。對(duì)于一個(gè)已經(jīng)匹配的結(jié)點(diǎn)i，如果從任何一個(gè)沒有匹配的結(jié)點(diǎn)出發(fā)存在一條到達(dá)i，而且i為外點(diǎn)的交錯(cuò)路，i也被認(rèn)為可以使用。計(jì)算所有從沒有匹配點(diǎn)出發(fā)的交錯(cuò)路（沒有匹配點(diǎn)i出發(fā)的交錯(cuò)路沒有被匹配點(diǎn)i一定為外點(diǎn)）所能到達(dá)的匹配的結(jié)點(diǎn)，只要從每一個(gè)沒有匹配的結(jié)點(diǎn)出發(fā)，寬度優(yōu)先搜索，只要O(N2)的時(shí)間。注意判斷重復(fù)（如果一個(gè)已經(jīng)匹配的結(jié)點(diǎn)已經(jīng)被確定為可以使用，那么不需要對(duì)它再擴(kuò)展一次，因?yàn)楫?dāng)把這個(gè)已經(jīng)匹配的結(jié)點(diǎn)確定為可以使用的結(jié)點(diǎn)的時(shí)候，已經(jīng)從這個(gè)結(jié)點(diǎn)擴(kuò)展過，如果再擴(kuò)展必將產(chǎn)生無謂的重復(fù)）所以MaxL=Max(MaxT[I][S]|i可以使用)；性能分析（3）：通過以上的優(yōu)化，所有數(shù)據(jù)都是瞬間出解，并且所有結(jié)果都是最優(yōu)解。甚至對(duì)n=200的隨機(jī)數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。精益求精：另外，還有兩個(gè)優(yōu)化，但是有時(shí)效果不好，但也值得一提。優(yōu)化三：分支定界。這樣可以增強(qiáng)剪枝條件一的效果，但是當(dāng)最優(yōu)解與Dist[1]相差比較遠(yuǎn)的時(shí)候，會(huì)浪費(fèi)一定的時(shí)間。優(yōu)化四：優(yōu)化一中Dist[i]的值有時(shí)并不是最優(yōu)的，通過測(cè)試，發(fā)現(xiàn)如果Dist[i]的值與最優(yōu)值相差1，特別是當(dāng)i小的時(shí)候，程序的速度都會(huì)有明顯的影響。所以，可以通過同樣的搜索來計(jì)算Dist[i]，（本題的答案就是Dist[1]）。這樣做可以增強(qiáng)剪枝條件一的效果，但是同時(shí)對(duì)每個(gè)i都要搜索也浪費(fèi)了一定的時(shí)間。程序結(jié)果比較：12345678910最簡(jiǎn)單的搜索0.000.000.50TimeOver0.65TimeOverTimeOverTimeOverTimeOverTimeOver優(yōu)化的搜索0.010.010.10TimeOver0.500.80TimeOver0.550.300.80進(jìn)一步優(yōu)化的搜索0.010.010.020.030.000.020.020.010.020.02此搜索方法一般都可以用兩個(gè)效果很好的可行性優(yōu)化：(1)提前判斷是否可以成功，避免多余的搜索。(2)每次判斷盡量多利用以前的判斷結(jié)果。總結(jié)：本文中的幾個(gè)例子都可以應(yīng)用部分搜索的方法高效解決，它們?cè)谒枷肷嫌兄黠@的相同點(diǎn)。一般的思維過程如下：一般的優(yōu)化包括：（1）選擇好的枚舉變量，使枚舉的變量數(shù)量盡可能少。（2）盡可能充分利用以前的結(jié)果，提前判斷，避免多余的搜索。部分搜索同樣可以和解方程、貪心、動(dòng)態(tài)規(guī)劃等高效算法結(jié)合。部分搜索＋高效算法體現(xiàn)了搜索與其他方法的有機(jī)結(jié)合，充分發(fā)揮兩者的長(zhǎng)處，相互彌補(bǔ)對(duì)方的不足，這就是其高效的主要原因所在。因此，在搜索問題中靈活地應(yīng)用部分搜索的方法，往往可以創(chuàng)造出奇效。值得注意的是，部分搜索來解決搜索問題作為一種非常規(guī)的搜索方法。雖然在本文的例子中，部分搜索有著很多的過人之處，但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法。大多數(shù)的搜索問題還是適合用常規(guī)的搜索方法的，所以只有充分把握部分搜索的特點(diǎn)，使之與常規(guī)的搜索融會(huì)貫通，才能真正得到高效的搜索算法。參考文獻(xiàn)：ACM/ICPCAsiaRegionalShanghai1996(MilkBottleData)ZJUMonthlyContest(TriangleConstruction)NOI2003(智破連環(huán)陣)感謝：ZhejiangUniversityOnlineJudge提供(MilkBottleData)和(TriangleConstruction)的題目描述。附錄：智破連環(huán)陣參考程序：#include<stdio.h>#include<stdlib.h>#include<string.h>constintmaxm=100+2;constintmaxn=100+2;intn,m,dist[maxm],MaxT[maxm][maxn];boolreachable[maxm][maxn],*can[maxm][maxm];/*m=B國(guó)武器數(shù)。n=A國(guó)炸彈數(shù)。dist[i]=如果A國(guó)炸彈可以重復(fù)使用，炸掉B國(guó)武器I~m的最少使用炸彈數(shù)。MaxT[s][i]=炸彈I，從S開始炸，可以炸到的最大編號(hào)，如果炸彈I炸不到S，則MaxT[I][S]=S-1。reachable[i][j]=A國(guó)炸彈i是否可以炸到B國(guó)炸彈j。can[s][t][i]=表示A國(guó)炸彈I是否可以炸到B國(guó)武器S,S+1..T-1,T。*/intanswer,bestv[maxn];/*answer=最少需要的A國(guó)炸彈數(shù)。bestv=記錄取最優(yōu)解A國(guó)炸彈的使用序列。*/inta[maxm],b[maxn];boolvis[maxn],*g[maxm];/*a[i],b[i]用于匹配，分別記錄左（右）第i個(gè)點(diǎn)的匹配邊的另一個(gè)點(diǎn)的編號(hào)，如果沒有匹配則為0。vis[i]用于匹配和寬度優(yōu)先搜索時(shí)判重。g[i][j]=左邊第i個(gè)點(diǎn)到右邊第j個(gè)點(diǎn)是否有邊。*/voidinit(){ //讀入數(shù)據(jù)并計(jì)算reachable。 intx1[maxm],y1[maxm],x2[maxn],y2[maxn],i,j,R; scanf("%d%d%d",&m,&n,&R); for(i=1;i<=m;i++) scanf("%d%d",&x1[i],&y1[i]); for(i=1;i<=n;i++) scanf("%d%d",&x2[i],&y2[i]); for(i=1;i<=m;i++) for(j=1;j<=n;j++) reachable[i][j]=((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j])<=R*R);}voidpreprocess(){ //初始化，計(jì)算can,MaxT。 ints,t,i; for(i=1;i<=m;i++) g[i]=newbool[maxn]; for(s=1;s<=m;s++) for(t=s;t<=m;t++) can[s][t]=newbool[maxn]; for(s=1;s<=m;s++) { for(i=1;i<=n;i++) can[s][s][i]=reachable[s][i]; for(t=s+1;t<=m;t++) for(i=1;i<=n;i++) can[s][t][i]=can[s][t-1][i]&&reachable[t][i]; for(i=1;i<=n;i++) { MaxT[s][i]=s-1; for(t=s;t<=m;t++) if(can[s][t][i]) MaxT[s][i]=t; } } //計(jì)算dist dist[m+1]=0; for(s=m;s>=1;s--) { t=s-1; for(i=1;i<=n;i++) if(MaxT[s][i]>t) t=MaxT[s][i]; dist[s]=1+dist[t+1]; }}boolfind(intv){ //匈牙利算法找可增廣路。 for(inti=1;i<=n;i++) if(g[v][i]&&!vis[i]) { vis[i]=true; if(b[i]==0||find(b[i])) { a[v]=i; b[i]=v; returntrue; } } returnfalse;}voidsearch(intused,ints){ //狀態(tài)：已經(jīng)使用了used個(gè)A國(guó)炸彈，編號(hào)在s之前的B國(guó)武器都已經(jīng)炸毀。 if(used+dist[s]>=answer)//優(yōu)化一：最優(yōu)性剪枝 return; if(s==m+1) { //如果B國(guó)武器已經(jīng)全部炸毀，