算法：記憶化搜索算法

一：簡述

記憶化搜索實際上是遞歸來實現的，但是遞歸的過程中有許多的結果是被反復計算的，這樣會大大降低算法的執行效率。

而記憶化搜索是在遞歸的過程中，將已經計算出來的結果保存起來，當之后的計算用到的時候直接取出結果，避免重復運算，因此極大的提高了算法的效率。

二：應用實例

題目描述
對于一個遞歸函數w(a,b,c)

如果 a<=0 or b<=0 or c<=0 就返回值1.
如果 a>20 or b>20 or c>20就返回w(20,20,20)
如果 a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
其它的情況就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
這是個簡單的遞歸函數，但實現起來可能會有些問題。當a,b,c均為15時，調用的次數將非常的多。你要想個辦法才行.

/* absi2011 : 比如 w(30,-1,0)既滿足條件1又滿足條件2

這種時候我們就按最上面的條件來算

所以答案為1

*/

輸入輸出格式
輸入格式：

會有若干行。

并以-1,-1,-1結束。

保證輸入的數在[-9223372036854775808,9223372036854775807]之間，并且是整數。

輸出格式：

輸出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

輸入輸出樣例

輸入樣例#1：
1 1 1
2 2 2
-1 -1 -1

輸出樣例#1：
w(1, 1, 1) = 2
w(2, 2, 2) = 4

這是一個非常經典的記憶化搜索的題目。
　　拿到這個題，首先可以想到的就是遞歸的方法，看上去用遞歸可以輕而易舉的解決。但是遞歸的開銷是不一般的大。下面先給大家

#include<iostream> #include<cstdio> #include <time.h> //用來記時 using namespace std; clock_t start, finish; double duration;typedef long long ll; ll f[30][30][30];int w(ll a, ll b, ll c){ //遞歸的函數 if(a<=0||b<=0||c<=0){return 1;}else if(a>20||b>20||c>20){return w(20,20,20);}else if(a<b&&b<c){return w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);}else{return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);} }int main(){ll a, b, c;while(1){cin >> a >> b >> c;start = clock(); //開始計時 if(a==-1&&b==-1&&c==-1) return 0;else{printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));finish = clock(); //結束記時 duration = (double)(finish - start) / CLOCKS_PER_SEC; //計算持續時間 printf( "%f seconds\n", duration );}}return 0; }

運行結果:

記憶化搜索解法

開辟一個數組 f[][][]，用來存儲計算出來的結果。

關于數組的大小：因為題目中給出了一個條件 “ 如果 a>20 or b>20 or c>20就返回w(20,20,20) ” 那么數組只要最小開到 f[21][21][21]就夠用了。

具體的步驟看代碼中的注解。

#include<iostream> #include<cstdio> #include <time.h> using namespace std; clock_t start, finish; double duration;typedef long long ll; ll f[30][30][30];int w(ll a, ll b, ll c){if(a<=0||b<=0||c<=0){return 1;}else if(a>20||b>20||c>20){return w(20,20,20);}else if(f[a][b][c]!=0)return f[a][b][c]; //如果之前被計算過，那么直接返回存在數組中的結果 //沒有計算過的，就進行的計算 else if(a<b&&b<c){ f[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);}else{f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);}return f[a][b][c]; //計算完畢之后返回計算出的結果 }int main(){ll a, b, c;while(1){cin >> a >> b >> c;start = clock(); //開始計時 if(a==-1&&b==-1&&c==-1) return 0;else{printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));finish = clock(); //結束記時 duration = (double)(finish - start) / CLOCKS_PER_SEC; //計算持續時間 printf( "%f seconds\n", duration );} }return 0; }

運行結果

大家和遞歸的運行時間對比一下就可以看出，當遞歸的次數多了之后，效率要高出很多。

大家和遞歸的運行時間對比一下就可以看出，當遞歸的次數多了之后，效率要高出很多。

三：總結過程

根據上面的題，可以總結一個記憶化搜索的過程。

f（problem p）{if(p has been solved){return the result }else{divide the p into some sub-problems (p1, p2, p3...)f(p1);f(p2);f(p3);...}

總結

以上是生活随笔為你收集整理的数据结构-记忆化搜索讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。