algorithm - 在matlab中优化动态规划

Question

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

问题(所有值都是实数):输入:设 X 为 T-by-d 矩阵，W 为 k-by-d 矩阵，A 为 k-by-k 矩阵。output: Y T-by-1 array s.t for row i in X Y(i) 是 W 中使我们的目标最大化的行数。

如果我们选择的前一行是 i，A(i,j) 会告诉我们选择第 j 行的成本。

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

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

动态解决方案:

• 实例化一个 k-by-T 矩阵

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

• 对于每个相同的列(表示为 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 的性能提升。