tsk*_*zzy 12 language-agnostic algorithm math matrix
这是我在编程竞赛中遇到的一个有趣的问题:
问题陈述:给定n矩阵的维数,确定是否存在可以乘以矩阵的排序.如果存在,则打印出所得矩阵的大小(尺寸的乘积).
我的观察:如果你将每个矩阵视为一个顶点并在可以乘法的矩阵之间绘制一个有向边,这会减少到NP完全哈密顿路径问题.我通过简单的强制解决问题解决了这个问题,但这显然非常缓慢.我想知道这个特定的问题实例是否有任何聪明的优化.
ElK*_*ina 14
为每个维度长度创建一个节点.也就是说,如果存在维度矩阵(m,n),那么m和n将是图中的顶点.
对于每个大小(m,n)的矩阵,将节点m和n与有向边连接(两个节点之间可以有多个边).
现在找到一个eularian路径将给出乘法顺序.
查看http://en.wikipedia.org/wiki/Euler_path查找Eularian小径.复杂度非常接近线性(O(nlog ^ 3n loglogn),其中n是边数=矩阵数).