给定一个 N 维矩阵A，我想找到一个M<N维索引数组I，使得子矩阵A[I, I]在所有此类I向量中具有最大元素和。
例如对于 3 维
A =
1 2 3
4 5 6
7 8 9
和二维索引[1,3]
A[(1,3), (1,3)] =
1 3
7 9
所以基本上这是一个离散优化问题，有N个选择M个可能的解决方案。
有没有找到最佳解决方案的有效方法？
查找具有最大和的子矩阵的索引
计算科学
矩阵
离散优化
2021-12-01 02:44:06
1个回答
这是一个已知为 NP-hard的二元背包问题。目前还没有有效的算法，但有一些算法可以解决多达 400 个变量的问题（根据 1999 年发表的一篇论文）。