算法合集之匹配算法在搜索問題中的應(yīng)用(參考版)
2024-10-19 20:30本頁面
【正文】 謝謝大家 ! 。雖然在本文的例子中，部分搜索有著很多的過人之處，但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法。 因此，在搜索問題中靈活地應(yīng)用部分搜索的方法，往往可以創(chuàng)造出奇效。 部分搜索同樣可以和解方程、 貪心、 動(dòng)態(tài)規(guī)劃等高效算法結(jié)合。 它們在思想上有著明顯的相同點(diǎn)。 甚至對 n=200的隨機(jī)數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。 這樣大大節(jié)省了優(yōu)化二的時(shí)間。 注意判斷重復(fù)（如果一個(gè)已匹配點(diǎn)已經(jīng)被確定為可以使用，那么不需要對它再擴(kuò)展一次，因?yàn)楫?dāng)把這個(gè)已匹配點(diǎn)確定為可以使用的結(jié)點(diǎn)的時(shí)候，已經(jīng)從這個(gè)結(jié)點(diǎn)擴(kuò)展過，如果再擴(kuò)展必將產(chǎn)生無謂的重復(fù)） 如果已經(jīng)求出了 MaxL， 可以先求一組長度為MaxL的匹配 A， 這樣對于所有長度在 1MaxL范圍內(nèi)的劃分， A都是一組可行匹配。 所以 maxL=Max(maxT[i][S] | i可以使用 )； 具體實(shí)現(xiàn)方法： 計(jì)算所有從未匹配點(diǎn)出發(fā)的交錯(cuò)路所能到達(dá)的已匹配點(diǎn)，從每一個(gè)未匹配點(diǎn)出發(fā)，寬度優(yōu)先搜索，只要 O(n2)的時(shí)間。 具體實(shí)現(xiàn)方法： 考慮二分圖右邊的 n個(gè)結(jié)點(diǎn)（ n顆炸彈）， 如果結(jié)點(diǎn) i未匹配，則 i被認(rèn)為可以使用。 求 MaxT[i][S]可以用動(dòng)態(tài)規(guī)劃的方法解決。 MaxT[i][S]=炸彈 i， 從 S開始炸，可以炸到的最大編號。 這樣既節(jié)省了判斷的時(shí)間，又可以使每次劃分長度從長到短枚舉，使程序盡快逼近最優(yōu)解，從而同時(shí)增強(qiáng)剪枝條件一的效果。 進(jìn)一步優(yōu)化： 優(yōu)化二雖然排除了許多不必要的劃分，但是在判斷時(shí)浪費(fèi)了不少時(shí)間。 性能分析（ 2）： 通過上述兩個(gè)優(yōu)化，程序效率有了很大提高。 每次求匹配只要從原來的基礎(chǔ)上擴(kuò)展就可以了。 (2)每次匹配可以從以前的匹配開始擴(kuò)展，不需要重新開始。 可以用動(dòng)態(tài)規(guī)劃計(jì)算 Dist值，狀態(tài)轉(zhuǎn)移方程如下： Dist[m+1]=0, Dist[i]=min{Dist[j]+1|C[i][j1][k](0k=n)) (1=i=N) (ij=N+1) 求 Dist的時(shí)間復(fù)雜度為 O(
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1