所以我想通过以下方式找到矩阵中的最小值。
[[ 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 个元素来做这个矩阵。
最佳答案
我会说一个可能不是最快但可能有效的解决方案。
您可以这样构建图表:
该图将包含 (N×N+1) 个顶点，代表矩阵的索引和一个新的顶点，它将作为源
源将连接到所有其他顶点，其距离等于每个顶点代表的索引值。
然后您必须将每个顶点(源除外)连接到可能到达的所有其他顶点(例如，M1[1][2] 可以到达 M1[0][3] 但不能到 M1[1][3])。从任何顶点到顶点 V 的距离将对应于矩阵中 V 的值。
构建此图后，您应该在其上走 K 步(K 是您将考虑的可能矩阵索引的数量，例如，像您的示例那样在 4x4 矩阵中为 2)。
对于你采取的每一步，你将你的最后位置存储在一个堆栈和 2 个哈希中(第一个存储所有已使用的行，第二个存储所有已使用的列)并标记你进入的顶点.
你总是进入一个顶点，你应该通过使用散列(理论上 O(1) 检查)来检查是否有可能留在其中，如果可能，你将该值添加到当前总和，否则你去到以前的位置(存储在堆栈中)并删除进入当前顶点时添加的权重。
您还应该存储一个全局变量，并且总是走 K 步，检查当前总和是否小于全局总和，如果是，则更改它。
在你走完所有可能的路之后，全局总和就是你的答案。
希望这有帮助:)
关于algorithm - 使用行索引和列索引一次查找矩阵中值的最小总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42584032/