算法合集之匹配算法在搜索問題中的應(yīng)用-資料下載頁
2024-10-16 20:30本頁面
【正文】 點(diǎn)，從每一個(gè)未匹配點(diǎn)出發(fā)，寬度優(yōu)先搜索，只要 O(n2)的時(shí)間。 可以證明，從未匹配點(diǎn)出發(fā)的交錯(cuò)路上的已匹配點(diǎn)一定為外點(diǎn)。 注意判斷重復(fù)（如果一個(gè)已匹配點(diǎn)已經(jīng)被確定為可以使用，那么不需要對(duì)它再擴(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， 這樣對(duì)于所有長度在 1MaxL范圍內(nèi)的劃分， A都是一組可行匹配。擴(kuò)展一次增廣路的復(fù)雜度為 O(n2)。 這樣大大節(jié)省了優(yōu)化二的時(shí)間。 性能分析（ 3）： 通過以上的優(yōu)化，所有數(shù)據(jù)都是瞬間出解，并且所有結(jié)果都是最優(yōu)解。 甚至對(duì) n=200的隨機(jī)數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。 最簡單的搜索 優(yōu)化的搜索 進(jìn)一步優(yōu)化的搜索 1 2 3 4 TimeOver TimeOver 5 6 TimeOver 7 TimeOver TimeOver 8 TimeOver 9 TimeOver 10 TimeOver 總結(jié)：本文中的兩個(gè)例子都可以應(yīng)用部分搜索＋匹配的方法高效解決。 它們?cè)谒枷肷嫌兄黠@的相同點(diǎn)。一般的思維過程如下： 一般的優(yōu)化包括： (1)提前通過匹配判斷，避免多余的搜索 (2)判斷時(shí)盡可能充分利用以前的結(jié)果，減少匹配的重復(fù)運(yùn)算。 部分搜索同樣可以和解方程、 貪心、 動(dòng)態(tài)規(guī)劃等高效算法結(jié)合。 部分搜索＋匹配算法體現(xiàn)了搜索與其他方法的有機(jī)結(jié)合，充分發(fā)揮兩者的長處，相互彌補(bǔ)對(duì)方的不足，這就是其高效的主要原因所在。 因此，在搜索問題中靈活地應(yīng)用部分搜索的方法，往往可以創(chuàng)造出奇效。 總結(jié) 值得注意的是，部分搜索來解決搜索問題作為一種非常規(guī)的搜索方法。雖然在本文的例子中，部分搜索有著很多的過人之處，但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法。大多數(shù)的搜索問題還是適合用常規(guī)的搜索方法的，所以只有充分把握部分搜索的特點(diǎn)，使之與常規(guī)的搜索融會(huì)貫通，才能真正得到高效的搜索算法。 謝謝大家 !
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1