算法合集之探尋深度優(yōu)先搜索中的優(yōu)化技巧-文庫吧資料
2024-10-22 20:30本頁面
【正文】 劃 由于優(yōu)化了狀態(tài)的表示，它可用一個整數(shù)方便的描述，而且問題很明顯滿足最優(yōu)性和無后效性，所以很快就會想到用動態(tài)規(guī)劃來求狀態(tài)的最優(yōu)值： 設 fi表示整數(shù) i所對應的未覆蓋區(qū)域至少需要多少個小正方形拼成： ???????1}1{1}m i n {10iijfifji 個正方形只需添加到狀態(tài)要求解的剖分線： i=1時對應的剖分線： 狀態(tài)數(shù)太大了！ 顯然無法求出所有的狀態(tài)的 fi值，但是我們只需求出其中的若干個就足夠了。 for i ? 1 to n do a[i] ? a[i 1]。 for i ? 1 to n do s ? s + Tot[i, a[i] 1]。 如何將 a與一個整數(shù)互相對應呢？ 設 Toti,j表示：滿足 j≥ai≥ai+1≥…≥an≥0的序列 {ak(i≤k≤n}}的個數(shù)。 由組合數(shù)學知識可知 b的個數(shù)為：把 n個無標號的小球放入 n+1個有標號的盒子中的方案數(shù)，等于 C2nn， 當n=31時也不超過 1e18， 故可考慮用一個 p類型數(shù)對應一個多元組 b。 分析：一個狀態(tài)需要占用 n個字節(jié)，空間太多，而且比較兩個狀態(tài)是否相等的時間復雜度為 O(n)， 速度也是非常慢的。 但是，有兩個新問題需要解決： 問題 如何求某個節(jié)點到目標節(jié)點的最優(yōu)值呢？ 問題 應該求哪些節(jié)點到目標節(jié)點的最優(yōu)值呢？ 狀態(tài)的表示 首先，某個節(jié)點到目標節(jié)點的最優(yōu)值只與當前未覆蓋區(qū)域的形狀有關，所以只要以未覆蓋區(qū)域作為當前狀態(tài)。 若求出了大量的節(jié)點的 y值，就能使許多非葉子節(jié)點變?yōu)槿~子節(jié)點，總節(jié)點數(shù)就會大大減少。 (測試環(huán)境 (R)4 CPU ) 還有什么方法能夠使搜索效率再大幅提高呢 ？ 看下邊這棵搜索樹： 當搜到藍色結(jié)點時 ， 若已經(jīng)使用了 x個小正方形 , 而這個節(jié)點到目標結(jié)點的最小深度為 y (也就是說最少可以用 y個小正方形拼完此時的未覆蓋區(qū)域 )， 那么若往下搜 ， 最優(yōu)值顯然剛好為x+y。 對右圖所示的兩種情況：它們沿 “ 左上 —右下 ” 對角線是對稱的 ，可以只搜它們中的任
教學課件相關推薦
鄂ICP備17016276號-1