algorithm - 矩阵重排的贪心解法

Question

我正在研究一些我认为是 NP 难题的问题。所以，我不是在寻找最佳解决方案，而是在寻找更好的启发式方法。给出一个整数输入矩阵(下例中的矩阵 A)作为输入，我必须生成一个整数输出矩阵(下例中的矩阵 B)，其行数小于输入矩阵，并且应满足以下两个条件:

1) 输出矩阵的每一列都应包含整数，其顺序应与它们在输入矩阵中出现的顺序相同。 (在下面的示例中，矩阵 A 和矩阵 B 的第一列具有相同顺序的相同整数 1,3。)

2)相同的整数不能出现在同一行(在下面的例子中，矩阵B的第一行包含彼此不同的整数1,3和2。)

请注意，输入矩阵始终遵循第二个条件。

解决这个问题的贪心算法是什么样的？

例子:

在此示例中，输出矩阵“矩阵 B”包含输入矩阵“矩阵 A”中出现的所有整数，但输出矩阵有 5 行，输入矩阵有 6 行。因此，输出“矩阵 B” ' 是输入'矩阵 A' 的有效解。

Answer 1

我会一次生成一行输出。在确定要放入行中的内容时，我会考虑每个输入列的下一个数字，从尚未放置的数字最多的输入列开始，并按照尚未放置的数字的降序考虑列。如果列可以在轮到它时在当前输出行中放置一个数字，它应该这样做。

您可以将其扩展到分支定界解决方案以找到确切的最佳答案。在每个阶段递归尝试所有可能的行，除非您发现当前行不可能改进目前为止的最佳答案。您知道，如果您有一列包含 k 个条目尚未放置，那么在最好的情况下，您至少需要再添加 k 行。

在实践中，我预计这会过于昂贵而不实用，因此您将需要忽略一些您不能排除的可能行，因此不能保证找到最佳答案。您可以尝试使用启发式搜索，例如有限差异搜索。

另一个非精确加速是将从部分解决方案得出的最佳可能答案所需的行数估计乘以某个因子 F > 1。这将允许您在分支和之前排除一些解决方案边界。您找到的答案的代价不会超过最佳答案的 F 倍，因为您只会丢弃无法将当前答案改进超过 F 倍的可能性。