matlab动态规划优化

Question

我有一个动态规划解决方案的问题，我试图在matlab中实现，并试图看看是否有一个更好的(运行时)实现比我能想到的。

问题(所有值都是实数):输入:设X是一个t × d矩阵，W是一个k × d矩阵，a是一个k × k矩阵。输出:Y T-by-1数组s.t对于X中的第i行Y(i)是W中使我们的目标最大化的行数。

A(i,j)给出了如果之前选择的行是i，那么选择第j行的代价。

为了计算输出的权重，我们对X中的每一行i求和W中Y(i)行的点积，并加上a中的相关成本。

我们的目标是使上述权重最大化。

动态解决方案:

• 实例化一个k × t矩阵

• 用W的每一行点积X的第一行的结果填充矩阵的第一列

• 对于每一个相同的列(用i表示)，用X的第i行与W的每一行的点积来填充，并加上A(j,i)的代价，其中j是前一列中值最大的单元格的行索引

• 从最后一列回溯，每次选择值最高的单元格的行索引

Matlab实现(带有变量实例化):

T = 8;
d = 10;
k = 20;
X = rand(T,d);
W = rand(k,d);
A = rand(k);
Y = zeros(T,1);
weight_table = zeros(k,T);
weight_table(:,1) = W*X(1,:)';
for t = 2 : T
    [~, prev_ind] = max(weight_table(:,t-1));
    weight_table(:,t) = W*X(t,:)' + A(:,prev_ind);
end
[~, Y] = max(weight_table);

Answer 1

由于迭代之间存在数据依赖性，我建议保持循环，但预先计算一些东西，如W的乘积和X的每一行的转置。这是在这里完成的(显示仅weight_table计算部分作为代码的其余部分保持在原来的帖子相同)-

weight_table = zeros(k,T);
weight_table(:,1) = W*X(1,:)';
WXt = W*X.'; %//' Pre-calculate
for t = 2 : T
    [~, prev_ind] = max(weight_table(:,t-1));
    weight_table(:,t) = WXt(:,t) + A(:,prev_ind); %// Use pre-calculated values and thus avoid that multiplication across each iteration
end

对于更大的输入，如- T = 800; d = 1000; k = 2000;，我在我的系统上使用它获得8-10x性能改进。