記憶化搜索的應用

一般來說，動態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動態(tài)規(guī)劃要低很多。

如何協(xié)調(diào)好動態(tài)規(guī)劃的高效率與高消費之間的矛盾呢？有一種折中的辦法就是記憶化算法。記憶化算法在求解的時候還是按著自頂向下的順序，每求解一個狀態(tài)，就將它的解保存下來，以后再次遇到這個狀態(tài)的時候，就不必重新求解了。這種方法綜合了搜索和動態(tài)規(guī)劃兩方面的優(yōu)點，因而還是很有使用價值的。

舉一個例子：如右圖所示是一個有向無環(huán)圖，求從頂點1到頂點6的最長路徑。（規(guī)定邊的方向從左到右）

我們將從起點（頂點1）開始到某個頂點的最長路徑作為狀態(tài)，用一維數(shù)組opt記錄。Opt[j]表示由起點到頂點j時的最長路徑。顯然，opt[1]=0，這是初始狀態(tài)，即動態(tài)規(guī)劃的邊界條件。于是，我們很容易地寫出狀態(tài)轉(zhuǎn)移方程式：opt[j]=max{opt[k]+a[k,j]}（k到j(luò)有一條長度為a[k,j]的邊）。雖然有了完整的狀態(tài)轉(zhuǎn)移方程式，但是還是不知道動態(tài)規(guī)劃的順序。所以，還需要先進行一下拓撲排序，按照排序的順序推下去，opt[6]就是問題的解。

可以看出，動態(tài)規(guī)劃相比搜索之所以高效，是因為它將所有的狀態(tài)都保存了下來。當遇到重復子問題時，它不像搜索那樣把這個狀態(tài)的最優(yōu)值再計算一遍，只要把那個狀態(tài)的最優(yōu)值調(diào)出來就可以了。例如，當計算opt[4]和opt[5]時，都用到了opt[3]的值。因為已經(jīng)將它保存下來了，所以就沒有必要再去搜索了。

但是動態(tài)規(guī)劃仍然是有缺點的。一個很突出的缺點就是要進行拓撲排序。這道題的拓撲關(guān)系是很簡單的，但有些題的拓撲關(guān)系是很復雜的。對于這些題目，如果也進行拓撲排序，工作量非常大。遇到這種情況，我們可以用記憶化搜索的方法，避免拓撲排序。

【例】滑雪

【問題描述】

小明喜歡滑雪，因為滑雪的確很刺激，可是為了獲得速度，滑的區(qū)域必須向下傾斜，當小明滑到坡底，不得不再次走上坡或等著直升機來載他，小明想知道在一個區(qū)域中最長的滑坡。滑坡的長度由滑過點的個數(shù)來計算，區(qū)域由一個二維數(shù)組給出，數(shù)組的每個數(shù)字代表點的高度。下面是一個例子：

1???? 2???? 3???? 4???? 5

16??? 17??? 18??? 19??? 6

15??? 24??? 25??? 20??? 7

14??? 23??? 22??? 21??? 8

13??? 12??? 11??? 10??? 9

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小，在上面的例子中，一條可行的滑坡為25-24-17-16-1（從25開始到1結(jié)束），當然25-24……2…1更長，事實上這是最長的一條。

【輸入格式】

輸入的第一行為表示區(qū)域的二維數(shù)組的行數(shù)R和列數(shù)C（1≤R、C≤100），下面是R行，每行有C個數(shù)代表高度。

【輸出格式】

輸出區(qū)域中最長的滑坡長度。

【輸入樣例】ski.in

5????? 5

1????? 2???? 3???? 4???? 5

16??? 17? ??18??? 19??? 6

15??? 24??? 25??? 20??? 7

14??? 23??? 22??? 21??? 8

13??? 12??? 11??? 10??? 9

【輸出樣例】ski.out

25

【算法分析】

由于一個人可以從某個點滑向上下左右相鄰四個點之一，如上圖所示。當且僅當高度減小，對于任意一個點[i,j]，當它的高度小于與之相鄰的四個點（[i-1,j], [i,j+1], [i+1,j], [i,j-1]）的高度時，這四個點可以滑向[i,j]，用f[i,j]表示到[i,j]為止的最大長度，則f[i,j]=max{f（i+a,j+b）}+1，其中坐標增量{(a,b)=[(1,0),(-1,0),(0,1),(0,-1)],0<i+a<=r，0<j+b<=c，High[i,j]<High[i+a,j+b]}。為了保證滿足條件的f[i+a,j+b]在f[i,j]前算出，需要對高度排一次序，然后從大到小規(guī)劃（高度）。最后再比較一下所有f(i,j){0<i≤r,0<j≤c}，找出其中最長的一條路線。我們還可以用記憶化搜索的方法，它的優(yōu)點是不需進行排序，按照行的順序，利用遞歸逐點求出區(qū)域中到達此點的最長路徑，每個點的最長路徑只求一次。

1 const 2 dx:array[1..4] of shortint=(0,-1,0,1); {x的坐標增量} 3 dy:array[1..4] of shortint=(-1,0,1,0); {y的坐標增量} 4 var 5 r,c,ans,anss:longint; 6 map,f:array[1..100,1..100] of longint; 7 procedure init; 8 var i,j:longint; 9 begin 10 readln(r,c); 11 for i:=1 to r do 12 for j:=1 to c do 13 read(map[i,j]); {讀入每個點的高度} 14 ans:=0; anss:=0; 15 fillchar(f,sizeof(f),0); 16 end; 17 function search(x,y:longint):longint; {函數(shù)的作用是求到[x,y]點的最長路徑} 18 var i,j,nx,ny,tmp,t:longint; 19 begin 20 if f[x,y]>0 then {此點長度已經(jīng)求出，不必進行進一步遞歸，保證每一個點的最大長度只求一次，這是記憶化搜索的特點} 21 begin 22 search:=f[x,y]; exit; 23 end; 24 t:=1; 25 for i:=1 to 4 do {從四個方向上搜索能達到[x,y]的點} 26 begin 27 nx:=x+dx[i]; ny:=y+dy[i]; {新坐標} 28 if (1<=nx)and(nx<=r) and (1<=ny)and(ny<=c) {邊界限制} 29 and (map[nx,ny]>map[x,y]) {高度比較} 30 then 31 begin 32 tmp:=search(nx,ny)+1; {遞歸進行記憶化搜索} 33 if tmp>t then t:=tmp; 34 end; 35 end; 36 f[x,y]:=t; 37 search:=t; 38 end; 39 procedure doit; 40 var i,j:longint; 41 begin 42 for i:=1 to r do {按照行的順序，利用遞歸逐點求出區(qū)域中到達此點的最長路徑} 43 for j:=1 to c do 44 begin 45 anss:=search(i,j); 46 //f[i,j]:=anss; 47 if anss>ans then ans:=anss; {尋找最大長度值} 48 end; 49 end; 50 procedure outit; 51 var i,j:longint; 52 begin 53 {for i:=1 to r do begin 54 for j:=1 to c do 55 write(f[i,j],' '); writeln; end;} 56 writeln(ans); 57 end; 58 begin 59 init; 60 doit; 61 outit; 62 end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/vacation/p/6071586.html

總結(jié)

以上是生活随笔為你收集整理的记忆化搜索的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。