使用行索引和列索引一次查找矩阵中值的最小和

Question

所以我想通过以下方式找到矩阵中的最小值。

       [[ 1000.   930.   940.   740.]
        [ 1000.  1000.   990.   670.]
   M1=  [ 1000.  1000.  1000.   680.]
        [ 1000.  1000.  1000.  1000.]]

2 个矩阵值之和的选择方式应使索引使用一次 0,1,2,3。但矩阵值的总和也应该最小化。

所以在这种情况下，解决方案是

M1[2][3]

和

M1[0][1]

。 不正确的是

M1[2][3]

和

M1[1][3]

，它们的总和较低，但不包含唯一索引号。

该解应该适用于 NxN 矩阵，N 是偶数。所以对于 8x8 矩阵，我想找到 4 个元素。这样索引号就出来了。 0,1,2,3,4,5,6,7 使用一次。所以有四个矩阵值。 另一个限制是矩阵仅包含上三角矩阵中感兴趣的值。因此，如果矩阵元素为 1000，则在求最小和时可以忽略这些元素。

我尝试过改变匈牙利算法，但没有成功。 有人知道有一种算法可以满足我的要求吗？也许是我可以滥用的 Python 包

或者有一个聪明的解决方案会有所帮助，我必须用最多大约 200X200 个元素来做这个矩阵。

Answer 1

我会说一个可能不是最快但可能有效的解决方案。

您可以这样构建图表：

• 该图将包含 (N×N+1) 个顶点，它们代表矩阵的索引和一个新的顶点，这将是源

• 源将连接到所有其他顶点，其距离等于每个顶点所代表的索引值。

• 然后您必须将每个顶点（源除外）连接到可能到达的所有其他顶点（例如，M1[1][2] 可以到达 M1[0][3]，但不能到达 M1[1 ][3]）。任意顶点到顶点 V 的距离将对应于矩阵中 V 的值。

构建此图后，您应该在其上行走 K 步（K 是您将考虑的可能矩阵索引的数量，例如，像您的示例一样，4x4 矩阵中的索引为 2）。

对于您采取的每一步，您都将您最后的位置存储在堆栈和 2 个哈希中（第一个存储已使用的所有行，第二个存储已使用的所有列），并标记您进入的顶点。

当你进入一个顶点时，你应该使用散列检查是否可以留在其中（理论上 O(1) 检查），如果可能，你将该值添加到当前总和中，否则你将转到之前的位置（存储在堆栈中）并删除进入当前顶点时添加的权重。

你还应该存储一个全局变量，并且总是走K步，检查当前总和是否小于全局总和，如果是，则更改它。

当你走完所有可能的路之后，全局总和就是你的答案。

希望这有帮助:)