下面是我在编程竞赛遇到一个有趣的问题：

问题陈述：的 N 矩阵给出的尺寸，确定是否存在一个排序使得矩阵可以成倍增加。如果存在之一，打印出所得到的矩阵的大小（尺寸的产品）。

我的意见：这减少的NP完全汉弥尔顿路径问题，如果你认为每个矩阵作为一个顶点，绘制矩阵，可以成倍之间有向边。我解决了这个通过简单的暴力破解的问题，但是这显然是非常缓慢的。我想知道是否有任何聪明的优化为这个问题的特定实例。

为每个维度长度的节点。也就是说，如果有尺寸的矩阵（M，N），那么m和n将在图中顶点

有关尺寸（M，N）的每一个矩阵连接节点m和n有向边（可以有两个节点之间的多条边）。

现在找到一个欧拉线索将使乘法顺序。

请参阅 http://en.wikipedia.org/wiki/Euler_path 寻找欧拉路径。复杂性是pretty的接近线性（O（n日志^ 3N loglogn），其中n是边数矩阵=号）。

Here is an interesting problem that I encountered in a programming competition:

Problem statement: Given the dimensions of n matrices, determine if there exists an ordering such that the matrices can be multiplied. If there exists one, print out the size (product of the dimensions) of the resultant matrix.

My observations: This reduces to the NP-complete hamiltonian path problem if you consider each matrix as a vertex and draw a directed edge between matrices that can be multiplied. I solved this by simply brute-forcing the problem but this is clearly very slow. I was wondering if there are any clever optimizations for this particular instance of the problem.

Create a node for each dimension length. That is, if there is a matrix of dimension (m,n), then m and n will be vertices in the graph.

For every matrix of size (m,n) connect nodes m and n with a directed edge (there can be multiple edges between two nodes).

Now finding a eularian trail would give the multiplication order.

See http://en.wikipedia.org/wiki/Euler_path for finding Eularian trails. Complexity is pretty close to linear ( O(nlog^3n loglogn) where n is the number of edges = number of matrices) .