algorithm - 使用动态规划的矩阵乘法子问题图

Question

我正在阅读 cormen 中的动态规划。

相关背景可以在下面的链接中找到

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap16.htm

通常，子问题图提供了一种替代方法来执行动态规划的运行时分析。每个顶点对应一个子问题，子问题的选择是从该子问题入射的边。回想一下，在棒切割中，子问题图有 n 个顶点，每个顶点最多有 n 条边，产生一个O(n^2) 运行时间。对于矩阵链乘法，如果我们要绘制子问题图，它将有 O(n^2) 个顶点，每个顶点的度数最多为 n - 1，总共有 O(n^3) 个顶点和边.

我正在寻找简单示例 n = 4 的矩阵链乘法子问题图。

感谢您的时间和帮助

Answer 1

我不确定我是否理解你的问题，但你正在寻找这样的东西吗？

我使用这个简单的 Python 脚本创建了它:

n = 4
print 'digraph {'
for i in range(n):
    for j in range(i, n):
        print 'p{}{} [label="M[{},{}]"];'.format(i,j,i+1,j+1)

for i in range(n):
    for j in range(n):
        for k in range(i, j):
            print 'p{}{} -> p{}{}'.format(i,j,i,k)
            print 'p{}{} -> p{}{}'.format(i,j,k+1,j)
print '}'

像这样运行(需要安装 graphviz 和 imagemagick):

python test.py | dot -Tpng | display