我正在阅读有关 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 的矩阵链乘法子问题图。
感谢您的时间和帮助
最佳答案
我不确定我是否理解你的问题,但你在寻找这样的东西吗?
我使用这个简单的 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
关于algorithm - 使用动态规划的矩阵乘法的子问题图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32583995/