从访谈中:删除n×n矩阵中的行和列,以最大化剩余值的总和

Question

给定n×n实数矩阵.您可以擦除任何数字(从0到n)的行和任何数字(从0到n)的列,然后计算剩余条目的总和.想出一个算法,找出要擦除的行和列,以便最大化该总和.

Answer 1

问题是NP难.(所以你不应该期望用多项式时间算法来解决这个问题.但是,仍然可能有(非多项式时间)算法略强于蛮力.)NP-硬度证明背后的想法是如果我们能解决这个问题,那么我们就可以在一般图中解决集团问题.(最大集团问题是在图中找到最大的成对连接顶点集.)

具体来说,给定任何具有n个顶点的图形,让我们形成矩阵A,其条目a[i][j]如下:

• a[i][j] = 1for i == j(对角线条目)
• a[i][j] = 0如果图(和i?j)中存在边(i,j )
• a[i][j] = -n-1如果边(i,j)为不存在于所述曲线图.

现在假设我们解决了删除某些行和列(或等效地保留一些行和列)的问题,以便最大化矩阵中条目的总和.然后答案给出了图中的最大集团:

1. 声明:在任何最佳解决方案中,没有保留行i和列j,图中不存在边(i,j).证明:由于a[i][j] = -n-1所有正条目的总和最多n,因此选择(i,j)将导致负数.(请注意,删除所有行和列将提供更好的总和,为0.)

2. 声明:在(某些)最优解决方案中,保持的行和列集是相同的.这是因为从任何最佳解决方案开始,我们可以简单地删除未保留i列的所有行,i反之亦然.请注意,由于唯一的正条目是对角条目,我们不会减少总和(并且通过之前的声明,我们也不会增加它).

所有这些意味着如果图形具有最大的大小k,则我们的矩阵问题具有求和的解,k反之亦然.因此,如果我们能够在多项式时间内解决我们的初始问题,那么集团问题也将在多项式时间内得到解决.这证明了最初的问题是NP难.(实际上,很容易看出初始问题的决策版本 - 是否有一种方法可以删除一些行和列,以便总和至少为k- 在NP中,因此(决定版本)初始问题是实际上NP完全.)

Answer 2

蛮力方法就是这样的:

• 对于n行,有2 ⁿ个子集.
• 对于n列,有2 ⁿ个子集.
• 对于nxn矩阵,有2 ²ⁿ个子集.

0个元素是一个有效的子集,但很明显,如果你有0行或0列,则总数为0,所以实际上有2 ^个2n-2 + 1个子集,但这没有什么不同.

因此,您可以通过强力计算每个组合作为O(a ⁿ)算法.快速.:)

通过计算网格中的所有正数,可以更快地计算出最大可能值是多少.如果这些数字碰巧形成一个有效的子矩阵(意味着您可以通过删除行和/或列来创建该集合),那么就是您的答案.

其中隐含的是,如果没有数字是负数,则根据定义,完整矩阵是答案.

此外,知道最高可能的最大值可能允许您快速执行暴力评估,因为如果您得到任何等于该最大值的组合,那么这就是您的答案,您可以停止检查.

此外,如果所有数字都是非正数,则答案是最大值,因为根据定义,您可以将矩阵缩减为1 x 1矩阵,其中包含1个值.

这是一个想法:构造2 ⁿ -1 nxm矩阵,其中1 <= m <= n.一个接一个地处理它们.对于每个nxm矩阵,您可以计算:

1. 最高可能的最大总和(如上所述); 和
2. 是否没有数字是正面的,允许您快捷回答.

如果(1)低于当前计算的最大最大总和,则可以丢弃此nxm矩阵.如果(2)为真,那么您只需要与当前最高的最大总和进行简单比较.

这通常被称为修剪技术.

你还可以开始说nxn矩阵中的最高数字是起始最高的最大总和,因为很明显它可以是1 x 1矩阵.

我相信你可以把它调成一个(稍微更有效)递归的基于树的搜索算法,上面的测试有效地允许你消除(希望很多)不必要的搜索.