matlab实现动态规划算法

matlab实现动态规划算法

最近看缓存相关论文，里面提到动态规划算法来解决小规模组合优化最优解，便尝试复DP算法，论文给出了一个简单例子，先从实现该例子开始，话说动态规划算法可以写好多东西，作为一个外行，第一次接触动态规划，断断续续花了一周多时间实现该算法，不知道这个效率去公司是不是已经被炒鱿鱼了。动态规划入门简单例子肯定从背包问题说起。
背包问题，讲解的通俗易懂，看懂后可以大致了解动态规划步骤，看懂后这种思想便可以移植到其他问题上。

论文例子

论文title《Mobility-Aware Caching in D2D Networks》，发表在IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS。
两个用户需要缓存文件，文件总数3，用户缓存容量为2，怎样缓存取得最优值。

文章给出的DP算法。只要看懂上图的例子，并实现，下面的算法就很好实现了。

不同文章DP算法几乎类似。就是一个多阶段决策优化问题。

实现算法

从例子图可知：

stage1阶段，只能缓存文件1，到stage2阶段，就可以缓存文件2，在缓存文件1得到的最优值基础上，加上缓存文件2，可以从Uf表中得到，便可得到新的缓存后的最优值，对每一个state，有不同的组合，这个状态就是可以缓存的最大容量，必须要在容量内进行组合，并比较取得最优值，从stage3，多个stage2的状态到stage3状态（2 2），最后比较得到整个决策过程的最优值。
matlab实现需要准备初始的stage1，和Uf，不断递归，得到最后一个stage，找到最优值及缓存方案。
从图中看，state状态需要矩阵保存，缓存分配需要矩阵保存，那么采用元胞数组来保存每一个stage。Uf也采用元胞保存。

递归关系就是前一阶段某一状态的最优值加上Uf里的各种组合的值，最后取最优值并保存最优分配方案。

代码

核心部分

for f = 2:F
    for i = 1:size(state,1) 
        for j = 1:size(Uf,1)  
            a = findAB(state,[sum(cell2mat(stage{1,f-1}(i,2)),1)+cell2mat(Uf(j,1))]);
            if a == 0
                continue
            end
            b = cell2mat(stage{1,f-1}(i,3))+cell2mat(Uf(j,f+1));
            if cell2mat(stage{1,f}(a,3))<=b
               stage{1,f}(a,3)={b};
               stage{1,f}(a,2)= {[cell2mat(stage{1,f-1}(i,2));cell2mat(Uf(j,1))]};    
            end
        end
    end
end

运行后stage3的结果，最优值0.82，对应缓存矩阵[1 1；1 0；0 1]。