数据结构-记忆化搜索讲解

算法：记忆化搜索算法 一：简述

记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。

而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。

二：应用实例

题目描述 对于一个递归函数w(a,b,c)

如果 a20就返回w(20,20,20) 如果 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
#include
#include    
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(a20){
        return w(20,20,20);
    }
    else if(f[a][b][c]!=0)return f[a][b][c];   //如果之前被计算过，那么直接返回存在数组中的结果 
                                                //没有计算过的，就进行的计算 
    else if(a 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);
         ...
    }