算法合集之探尋深度優(yōu)先搜索中的優(yōu)化技巧-資料下載頁
2024-10-16 20:30本頁面
【正文】 ，不比當前最優(yōu)值更優(yōu)； 如果找到了，那么搜下去的最優(yōu)值顯然為 x+fi， 就可直接令當前最優(yōu)值 =min{當前最優(yōu)值， x+fi}； 這樣一來，避免了無謂的查找，效率大大提高。 實現(xiàn)方法 經(jīng)過以上的優(yōu)化過程，搜索的層次能夠減少了 c層，效率得到了大大的提高。 如果結合各種各樣剪枝條件，最大數(shù)據(jù) (n =31)也僅要4秒多。 搜索效率 n 運行時間 n 運行時間 =17 25 19 27 21 29 23 31 至此，已圓滿解決了本題。 回顧解決本題的步驟 簡單的動態(tài)規(guī)劃 Fi,j， 求較優(yōu)解； 根據(jù)本題“剖分的對稱性”等特點設計了一些簡單的剪枝； 通過合理的劃分剖分方案，得到新的搜索順序，找到了新的剪枝方法； 通過將每個狀態(tài)對應于一個整數(shù)，方便的借助高效的動態(tài)規(guī)劃算法來求某些狀態(tài)值，從而降低了搜索的層數(shù)。 經(jīng)過以上這 4步，搜索的效率逐步提高！特別是第 3步和第 4步效率提高得十分明顯。 搜索，因其時間效率的 “先天不足”，人們有針對性的研究出了很多優(yōu)化技巧。 一、搜索的對象和順序是優(yōu)化中非常重要的一個環(huán)節(jié)，好的順序往往是高效率的前提。但是，它也僅僅是一個前提，要保障高效率僅僅靠它是不夠的； 二、“剪枝”是最常見的優(yōu)化方法，幾乎可以說，只要用搜索解決問題，就必須考慮剪枝優(yōu)化。 但是，無論剪枝多么巧妙，都不能從本質(zhì)上降低搜索算法的時間復雜度。 總結 三、預求某些狀態(tài)的最優(yōu)值，降低搜索的層數(shù)。它能夠起到降低搜索復雜度的功效。 由于 FreePascal的開發(fā)使用，使得空間上的限制放松了上百倍，而題目對運行時間的限制歷來都是十分苛刻的，這使得我們想到用犧牲空間的代價來換取更多的時間。若把它利用到搜索中來，就產(chǎn)生以上這種優(yōu)化方法。 這一優(yōu)化中最重要的一步就是 狀態(tài)的表示 。 算法的優(yōu)化是永無止境的，搜索的優(yōu)化更是如此，需要我們 具體問題具體分析，充分發(fā)揮思維的靈活性。只有積累了足夠的經(jīng)驗，才能夠熟練的應用各種優(yōu)化技巧。 總結 n 13 23 29 F’n,n 12 14 15 最優(yōu)值 11 13 14
教學課件相關推薦
鄂ICP備17016276號-1