版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、匹配算法在搜索問題中的巧用,浙江省杭州第十四中學(xué) 樓天城loutiancheng@sina.com,很多的題目,如果我們可以建立數(shù)學(xué)模型,應(yīng)該盡量用解析法來處理,因?yàn)楹唵蔚哪P透逦胤从沉耸挛镏g的關(guān)系。 但是,并不是所有的題目都可以建立簡單的數(shù)學(xué)模型。我們這時必須使用搜索的方法,也就是枚舉所有可能情況來尋找可行解或最優(yōu)解。,前言,由于搜索一般建立在枚舉之上,所以搜索常常和低效是分不開的。 有時搜索的運(yùn)算量實(shí)在太大,實(shí)
2、在是一件痛苦的事情。,于是我們需要利用很多技巧來提高效率: 可行性剪枝, 最優(yōu)性剪枝, 調(diào)整搜索順序, 等方法都很有用,在它們的幫助下,我們可以大大提高搜索的效率。,而有些題目,這些常規(guī)的優(yōu)化方法很難有用武之地。這是我們必須使用一些非常規(guī)的搜索方法。 本文中我們將討論非常規(guī)搜索中的一種 ——部分搜索+匹配算法,引題: N個物品與N個位置,給定每個物品的可能放的
3、位置集合,要求尋找一一對應(yīng)的關(guān)系?! 〉€給出物品位置之間的限制(例如:如果1放在3則2不能放在1)?! ∏笠唤M可行解,或給每一種對應(yīng)關(guān)系一個權(quán),求滿足條件的最優(yōu)解。,由于事物之間的限制關(guān)系非常復(fù)雜,很難建立簡單的二分圖關(guān)系,或者用網(wǎng)絡(luò)流來解決?! ∶鎸@一系列類似的問題,我們一般只有搜索,如何搜索又如何優(yōu)化呢?,簡單分析: 如果我們枚舉每一個物品的位置,然后判斷。這樣的時間復(fù)雜度為O(N!)。好像似乎也只能這樣。,進(jìn)一步分析
4、:我們看一個例子,N=6:其它限制有4條(a,b,c,d)表示如果a放在b則c不能放在d1 3 5 62 2 5 33 1 4 13 2 6 2 我們發(fā)現(xiàn),如果我們一旦確定了3和5的位置,其它4個物品的位置之間已經(jīng)沒有限制關(guān)系了,這樣其它4個物品的位置可以通過匹配來解決。,這時我們發(fā)現(xiàn)一個新的搜索方法:部分搜索+匹配。,1 3 5 62 2 5 33 1 4 13 2 6 2,部分搜索+匹配: 搜索
5、一部分變量,使得余下的變量之間的關(guān)系簡化,然后通過一些高效算法(匹配)完成余下問題。,就本題而言就是:先搜索一定數(shù)量(而不是全部)的物品的位置,使問題內(nèi)其它物品的關(guān)系簡化為二分圖關(guān)系,用二分圖匹配來解決余下的物品。,通過部分搜索為匹配算法提供條件(例如上面的例子創(chuàng)造二分圖關(guān)系),而匹配算法代替搜索,高效地完成余下的任務(wù)?! 〔糠炙阉?匹配的方法充分發(fā)揮了搜索和匹配算法的雙重優(yōu)勢。搜索的優(yōu)勢在于應(yīng)用性廣,可以克服復(fù)雜的情況,匹配算法的優(yōu)
6、勢在于效率高。兩者相互促進(jìn),同時也彌補(bǔ)對方的不足。這也是這個方法的成功的關(guān)鍵。,例如上面的例子,如果我們先知道了3和5的位置后,不用匹配,其實(shí)我們是在用搜索來求匹配,效率當(dāng)然不會高。,部分搜索+匹配的方法已經(jīng)在很多題目中得到了應(yīng)用。,一個部分搜索+匹配算法的經(jīng)典例子。,智破連環(huán)陣,題目簡述(NOI2003二試第三題) B國的連環(huán)陣由M個武器組成。最初,1號武器處于攻擊狀態(tài),其他武器都處在無敵自衛(wèi)狀態(tài)。以后,一旦第i(1 ? i<
7、;M)號武器被消滅,1秒鐘以后第i+1號武器就自動從無敵自衛(wèi)狀態(tài)變成攻擊狀態(tài)。 A國有N個炸彈,每個炸彈的作用半徑均為k,且會持續(xù)爆炸5分鐘。在這5分鐘內(nèi),瞬間消滅離它直線距離不超過k的、處在攻擊狀態(tài)的B國武器,不會炸毀本國炸彈。,任務(wù): 決定一個序列a1、a2、a3…使得在第ax號炸彈引爆的時間內(nèi)連環(huán)陣被摧毀。這里的x應(yīng)當(dāng)盡量小。輸入: N,M及武器和炸彈的坐標(biāo)。測試數(shù)據(jù)中的坐標(biāo)是隨機(jī)生成的。,初步分析: A
8、國炸彈I可以炸到B國武器J的條件: (u[I]-x[J])2+(v[I]-y[J])2<=R2,結(jié)論:很難找到求最優(yōu)解的多項式算法。面對此類問題,一般只有搜索策略。,進(jìn)一步分析: 每一顆炸彈必定炸掉B國武器中編號連續(xù)的一段?! ?分鐘只是表明每一顆炸彈可以炸掉任意多個編號連續(xù)的B國武器。,普通的搜索方法: 每次尋找一個編號最小的沒有被炸掉的B國武器,選擇一顆沒有使用過并能炸到此武器的A國炸彈,然后使
9、用這顆炸彈炸掉B國武器連續(xù)的一段,繼續(xù)深度優(yōu)先搜索下一顆炸彈的編號,如果發(fā)現(xiàn)B國武器已經(jīng)全部炸毀就可以回溯。 搜索的時間復(fù)雜度為O(n!)。即使加上優(yōu)化,程序效率也不是很高。,部分搜索: 此題使用部分搜索的算法需要一些轉(zhuǎn)化:如果已經(jīng)將B國武器根據(jù)編號分為x段,其中第I段為[Si,Ti] (S1=1,Ti>=Si,Ti+1=Si+1)?! ∪缓蟮娜蝿?wù)就是判斷是否可以從A國的N顆炸彈中選出x顆,分別可以炸掉其中的一段。,其
10、實(shí)我們把搜索分為了兩部分, (1)將B國武器根據(jù)編號分為x段。?。ǎ玻┡袛嗍欠窨梢詮腁國的N顆炸彈中選出x顆,分別可以炸掉其中的一段。,其實(shí)第二部分可以用匹配來解決。,建圖:C[S][T][I] 表示A國炸彈I是否可以炸到B國武器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] (
11、S<T)求C的時間復(fù)雜度為O(N3)。,建圖:左邊x個點(diǎn),表示B國武器根據(jù)編號分為的x段,右邊N個點(diǎn),表示A國的N顆炸彈。左邊第i個點(diǎn)到右邊第j個點(diǎn)有邊的條件即:C[Si][Ti][j]?! ∠旅嫒蝿?wù)就是將B國武器根據(jù)編號劃分為若干段+二分圖匹配判斷。,樣例1:4 3 60 6 6 6 6 0 0 01 5 0 3 1 1,性能分析(1): 搜索的基本框架已經(jīng)建立,雖然數(shù)據(jù)是隨機(jī)生成的,但是m個B國武器的劃
12、分方案還是非常多的,有時可能高達(dá)2m。時間上很難承受,如果使用卡時,正確性受到影響,效果不會很好?! ≈挥?個數(shù)據(jù)可以在時限內(nèi)出解,另外6個如果卡時,有2個也可以得到最優(yōu)解。,優(yōu)化: 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。,優(yōu)化一(最優(yōu)性):如果A國炸彈可以重復(fù)使用,設(shè):Dist[I]=炸掉B國武器I-m的最少使用炸彈數(shù)?!】梢杂脛討B(tài)規(guī)劃計算Dist值,狀態(tài)轉(zhuǎn)移方程如下:Dist[m+1]=0。Dist[I]=Min
13、(Dist[J]+1 | Can[I][J-1][K](1<=K<=n)) (1<=I<=N) (I<J<=N+1)求Dist的時間復(fù)雜度為O(N3)。,從而產(chǎn)生了一個最優(yōu)性剪枝條件:if (當(dāng)前已經(jīng)使用的炸彈數(shù)+Dist[當(dāng)前已經(jīng)炸掉的B國武器數(shù)+1]>=當(dāng)前找到的最優(yōu)解)then 剪枝;,優(yōu)化二(可行性): 部分搜索+匹配的方法一般都可以用兩個效果很好的可行性優(yōu)化:(1)提前判
14、斷是否可以匹配成功,避免多余的搜索。(2)每次匹配可以從以前的匹配開始擴(kuò)展,不需要重新開始。,如果當(dāng)前的劃分方法已經(jīng)無法匹配成功,就沒有搜索下去的必要了,只要每搜索新的一段時立即通過匹配判斷即可?! ∶看吻笃ヅ渲灰獜脑瓉淼幕A(chǔ)上擴(kuò)展就可以了。沒有必要從頭開始。,性能分析(2): 通過上述兩個優(yōu)化,程序的效率有了很大的提高?! ?10個測試數(shù)據(jù)中有8個可以在時限內(nèi)出解,另外2個如果卡時,也可以得到最優(yōu)解。,,進(jìn)一步優(yōu)化:
15、 優(yōu)化二雖然排除了許多不必要的劃分,但是在判斷時浪費(fèi)了不少時間?! ∫虼?,在枚舉劃分長度時,可以通過以前的劃分和匹配情況(被匹配的邊),用O(n2)的時間復(fù)雜度的寬度優(yōu)先搜索計算出下一個劃分的最大長度maxL,顯然下一個劃分的長度在[1,maxL]都一定可以找到可行的匹配。 這樣既節(jié)省了判斷的時間,又可以使每次劃分長度從長到短枚舉,使程序盡快逼近最優(yōu)解,從而同時增強(qiáng)剪枝條件一的效果。,這一部分的實(shí)現(xiàn),首先需要求MaxT。Max
16、T[I][S]=炸彈I,從S開始炸,可以炸到的最大編號。 如果,炸彈I炸不到S,則MaxT[I][S]=S-1。求MaxT[I][S]可以用動態(tài)規(guī)劃的方法解決。狀態(tài)轉(zhuǎn)移方程為:MaxT[I][S]= 炸彈I炸不到S S-1 炸彈I炸得到S MaxT[I][S+1]MaxT[I][m+1]=m求MaxT的時間復(fù)雜度為O(N2)。,具體實(shí)現(xiàn)方法: 考慮二分圖右邊
17、的n個結(jié)點(diǎn)(n顆炸彈), 如果結(jié)點(diǎn)I沒有被匹配,I被認(rèn)為可以使用?! ∪绻Y(jié)點(diǎn)I已經(jīng)被匹配,如果從任何一個沒有匹配的結(jié)點(diǎn)出發(fā)存在一條到達(dá)I,而且I為外點(diǎn)的交錯路,I也被認(rèn)為可以使用?! ∷訫axL=Max(MaxT[I][S] | I可以使用);,具體實(shí)現(xiàn)方法: 計算所有從沒有匹配點(diǎn)出發(fā)的交錯路(沒有匹配點(diǎn)I出發(fā)的交錯路沒有被匹配點(diǎn)I一定為外點(diǎn))所能到達(dá)的匹配的結(jié)點(diǎn),只要從每一個沒有匹配的結(jié)點(diǎn)出發(fā),寬度優(yōu)先搜索,只要O(
18、N2)的時間。 注意判斷重復(fù)(如果一個已經(jīng)匹配的結(jié)點(diǎn)已經(jīng)被確定為可以使用,那么不需要對它再擴(kuò)展一次,因?yàn)楫?dāng)把這個已經(jīng)匹配的結(jié)點(diǎn)確定為可以使用的結(jié)點(diǎn)的時候,已經(jīng)從這個結(jié)點(diǎn)擴(kuò)展過,如果再擴(kuò)展必將產(chǎn)生無謂的重復(fù)),如果已經(jīng)求出了MaxL,可以先求一組長度為MaxL的匹配A,這樣對于所有長度在1-MaxL范圍內(nèi)的劃分,A都是一組可行匹配。擴(kuò)展一次增廣路的復(fù)雜度為O(n2)。 這樣大大節(jié)省了優(yōu)化二的時間。,性能分析(3): 通過以上的
19、優(yōu)化,所有數(shù)據(jù)都是瞬間出解,并且所有結(jié)果都是最優(yōu)解。 甚至對n=200的隨機(jī)數(shù)據(jù),也可以在瞬間出解,可見程序的效率有了很大的提高。,總結(jié):本文中的兩個例子都可以應(yīng)用部分搜索+匹配的方法高效解決。 它們在思想上有著明顯的相同點(diǎn)。一般的思維過程如下:,,一般的優(yōu)化包括:(1)提前通過匹配判斷,避免多余的搜索(2)判斷時盡可能充分利用以前的結(jié)果,減少匹配的重復(fù)運(yùn)算。,部分搜索同樣可以和解方程、
20、 貪心、 動態(tài)規(guī)劃等高效算法結(jié)合。,部分搜索+匹配算法體現(xiàn)了搜索與其他方法的有機(jī)結(jié)合,充分發(fā)揮兩者的長處,相互彌補(bǔ)對方的不足,這就是其高效的主要原因所在?! ∫虼?,在搜索問題中靈活地應(yīng)用部分搜索的方法,往往可以創(chuàng)造出奇效?! ≈档米⒁獾氖?,部分搜索來解決搜索問題作為一種非常規(guī)的搜索方法。雖然在本文的例子中,部分搜索有著很多的過人
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 優(yōu)化問題中的廣義模式搜索算法.pdf
- 和聲搜索算法在函數(shù)優(yōu)化問題中的應(yīng)用研究.pdf
- 改進(jìn)變鄰域搜索算法在動態(tài)車輛路徑問題中的研究.pdf
- 改進(jìn)的和聲搜索算法及其在選址-庫存-路徑問題中的應(yīng)用.pdf
- 混合禁忌搜索算法在配送車輛調(diào)度問題中的研究和應(yīng)用.pdf
- 捕食搜索及其在組合優(yōu)化問題中的應(yīng)用.pdf
- 局部搜索技術(shù)在析取時序問題中的應(yīng)用.pdf
- 改進(jìn)的Lin-Kernighan局部搜索算法和雜交算法在旅行商問題中的應(yīng)用.pdf
- 幾何相容性在圖像匹配問題中的應(yīng)用.pdf
- 多目標(biāo)和聲搜索算法在半Flow Shop調(diào)度問題中的應(yīng)用研究.pdf
- 加工車間調(diào)度問題中禁忌搜索算法的研究與改進(jìn).pdf
- 分治算法在樹的路徑問題中的應(yīng)用
- 遺傳算法在分配問題中的應(yīng)用.pdf
- 非線性優(yōu)化的直接搜索算法及其在分形粗糙面散射問題中的應(yīng)用.pdf
- 改進(jìn)和聲搜索算法在車輛路徑問題中的應(yīng)用研究.pdf
- 遺傳算法在TSP問題中的應(yīng)用.pdf
- FPT-算法在CBVC問題中的運(yùn)用.pdf
- 改進(jìn)的螞蟻算法在TSP問題中的研究.pdf
- 仿生算法及其在專家分配問題中的應(yīng)用.pdf
- PageRank算法在非網(wǎng)頁檢索問題中的應(yīng)用.pdf
評論
0/150
提交評論