算法合集之探尋深度優(yōu)先搜索中的優(yōu)化技巧-閱讀頁
2024-10-31 20:30本頁面
【正文】 因?yàn)樗训剿涂芍苯踊厮萘恕? 這就為進(jìn)一步增加搜索效率找到了契機(jī)。 那么如何描述一個未覆蓋區(qū)域呢？ 可用逆序 n元組 (a1,a2,…,an)， ai≥ai+1 , n≥a1表示，其中 ai表示第 i+n1行未被覆蓋的小格子數(shù)目 。 有沒有更好的方法呢？ 優(yōu)化狀態(tài)的表示 不妨令 bi=aiai +1(0≤i≤n， 這里 a0=n， an+1=0)， 則有 bi≥0， ∑bi=n。 而 b與 a也是一一對應(yīng)的，所以可用一個 p類型整數(shù)直接描述一個狀態(tài)。 狀態(tài)的對應(yīng)的實(shí)現(xiàn) 將 n元組 a轉(zhuǎn)化為整數(shù) s s ? 0。 將整數(shù) s轉(zhuǎn)化為 n元祖 a： a[0] ? n。 while s Tot[i, a[i] 1] do a[i] ? a[i] 1 s ? s Tot[i, a[i] 1]。當(dāng)然應(yīng)該盡量多求一些，因?yàn)榍蟪龅臓顟B(tài)越多搜索的效率就會越高。由于每條邊長度都為 1，可以從點(diǎn) 1開始廣搜，不斷擴(kuò)展直到產(chǎn)生出足夠多的狀態(tài)。 搜索時，每搜到一個節(jié)點(diǎn)，就查找當(dāng)前的狀態(tài) i是否在表中，如果找到了相應(yīng)的 fi值就可改進(jìn)當(dāng)前最優(yōu)值然后直接回溯。 實(shí)現(xiàn)方法 優(yōu)化：只計(jì)算 fi小于 ≤c(自定的常數(shù) )的狀態(tài)。 實(shí)現(xiàn)方法 經(jīng)過以上的優(yōu)化過程，搜索的層次能夠減少了 c層，效率得到了大大的提高。 搜索效率 n 運(yùn)行時間 n 運(yùn)行時間 =17 25 19 27 21 29 23 31 至此，已圓滿解決了本題。 經(jīng)過以上這 4步，搜索的效率逐步提高！特別是第 3步和第 4步效率提高得十分明顯。 一、搜索的對象和順序是優(yōu)化中非常重要的一個環(huán)節(jié)，好的順序往往是高效率的前提。 但是，無論剪枝多么巧妙，都不能從本質(zhì)上降低搜索算法的時間復(fù)雜度。它能夠起到降低搜索復(fù)雜度的功效。若把它利用到搜索中來，就產(chǎn)生以上這種優(yōu)化方法。 算法的優(yōu)化是永無止境的，搜索的優(yōu)化更是如此，需要我們 具體問題具體分析，充分發(fā)揮思維的靈活性。 總結(jié) n 13 23 29 F’n,n 12 14 15 最優(yōu)值 11 13 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1