算法合集之探尋深度優(yōu)先搜索中的優(yōu)化技巧(編輯修改稿)
2024-11-12 20:30 本頁面
【文章內容簡介】 。 (測試環(huán)境 (R)4 CPU ) 還有什么方法能夠使搜索效率再大幅提高呢 ？ 看下邊這棵搜索樹： 當搜到藍色結點時 ， 若已經使用了 x個小正方形 , 而這個節(jié)點到目標結點的最小深度為 y (也就是說最少可以用 y個小正方形拼完此時的未覆蓋區(qū)域 )， 那么若往下搜 ， 最優(yōu)值顯然剛好為x+y。 最小深度為 Y 那么，若已知 y的值，藍色節(jié)點就變?yōu)榱怂阉鳂渲械娜~子節(jié)點，因為搜到它就可直接回溯了。 若求出了大量的節(jié)點的 y值，就能使許多非葉子節(jié)點變?yōu)槿~子節(jié)點，總節(jié)點數(shù)就會大大減少。 這就為進一步增加搜索效率找到了契機。 但是，有兩個新問題需要解決： 問題 如何求某個節(jié)點到目標節(jié)點的最優(yōu)值呢？ 問題 應該求哪些節(jié)點到目標節(jié)點的最優(yōu)值呢？ 狀態(tài)的表示 首先，某個節(jié)點到目標節(jié)點的最優(yōu)值只與當前未覆蓋區(qū)域的形狀有關，所以只要以未覆蓋區(qū)域作為當前狀態(tài)。 那么如何描述一個未覆蓋區(qū)域呢？ 可用逆序 n元組 (a1,a2,…,an)， ai≥ai+1 , n≥a1表示，其中 ai表示第 i+n1行未被覆蓋的小格子數(shù)目 。 分析：一個狀態(tài)需要占用 n個字節(jié)，空間太多，而且比較兩個狀態(tài)是否相等的時間復雜度為 O(n)， 速度也是非常慢的。 有沒有更好的方法呢？ 優(yōu)化狀態(tài)的表示 不妨令 bi=aiai +1(0≤i≤n， 這里 a0=n， an+1=0)， 則有 bi≥0， ∑bi=n。 由組合數(shù)學知識可知 b的個數(shù)為：把 n個無標號的小球放入 n+1個有標號的盒子中的方案數(shù)，等于 C2nn， 當n=31時也不超過 1e18， 故可考慮用一個 p類型數(shù)對應一個多元組 b。 而 b與 a也是一一對應的，所以可用一個 p類型整數(shù)直接描述一個狀態(tài)。 如何將 a與一個整數(shù)互相對應呢？ 設 Toti,j表示：滿足 j≥ai≥ai+1≥…≥an≥0的序列 {ak(i≤k≤n}}的個數(shù)。 狀態(tài)的對應的實現(xiàn) 將 n元組 a轉化為整數(shù) s s ? 0。 for i ? 1 to n do s ? s + Tot[i, a[i] 1]。 將整數(shù) s
教學課件相關推薦
鄂ICP備17016276號-1