算法 select 设置共享元素

Question

我有一组二维数组。我需要 select 每列的最佳集合。

最佳集合是这样的：所有此类最佳集合中唯一项的数量最少。

我正在使用 python，但我认为这应该与语言无关。

我目前的方法非常原始，会搜索所有可能的选项，这会导致搜索量过大 space。（10^15 的顺序）

我正在寻找一种不那么天真的方式来查看数据，并减少搜索 space。

在下面的代码中，我知道我可以改进性能，但我对改进算法更感兴趣。

for comb in itertools.product(*value_options):
    comb_length = len(set(itertools.chain(*comb)))
    if comb_length < best_count:
        best = comb
        best_count = comb_length

关于数据的更多信息，集合很小，目前它们是两个值但我希望能够支持更多，一组集合中可以有任意数量的集合

我添加了一些测试数据。为了使文件更符合逻辑，文件中的每一行都是上面提到的列之一，每组都在括号中。

小集 http://www.importsoul.net/static/testdata.csv

从这组数据我得出结果

 332000.000,348000.000
  95300.000,787000.000
  48700.000,332000.000
  31600.000,64900.000
  12700.000,64900.000
   5620.000,95300.000
  10000.000

我还有一组更大的输入数据，尚未完成运行。 http://www.importsoul.net/static/testdata-large.csv

为了更容易导入这里是测试数据 json

Answer 1

这个问题是NP完全的。您可以做得比现在更好，但是您可以扩展的范围是有限的。

首先，您可以使用 branch-and-bound 改进您的算法，以避免看到 "obviously" 比您已经看到的更糟糕的解决方案。这个想法是跟踪迄今为止看到的最佳解决方案所涵盖的独特元素的数量，并通过一次从一列中选择集合来构建部分解决方案。如果在任何时候，您选择的集合包含比您见过的最佳解决方案更多的独特元素，您可以立即撤消最近的选择并尝试不同的选项，而无需探索所有可能的方法来构建完整的解决方案来自次优的部分解决方案。

为了证明问题是 NP 完全问题，我们为您的问题提供了 boolean satisfiability 的多项式时间缩减。我们假设列可以有不同的长度；证明稍微有点笨拙，但仍然有可能，列被强制为等长。

假设我们有一个合取范式的布尔公式，例如：

(!A || B || C) && (!C || D || !E) && (A || !B || D)

我们想知道它是否可以满足。我们构建了您问题的相应实例。这个想法是使用 1 元素集的列来强制我们为每个变量选择一个真值，看看我们是否可以选择集使得没有变量必须同时为真和假。

对于公式中的每个析取子句，我们构建一个列，迫使我们选择析取的一个元素。例如，析取子句 (!A || B || C) 将变成列

{!A}
{B}
{C}

迫使我们选择析取给我们的选择之一。此外，我们添加以下形式的列：

{A}  | {B}  | {C}  | {D}  | {E}
{!A} | {!B} | {!C} | {!D} | {!E}

迫使我们为每个变量选择变量或其否定。我们的示例公式的完整 table 看起来像

{!A} | {!C} | {A}  | {A}  | {B}  | {C}  | {D}  | {E}
{B}  | {D}  | {!B} | {!A} | {!B} | {!C} | {!D} | {!E}
{C}  | {!E} | {D}

如果每列的最佳选择集包含的唯一元素的数量等于公式中变量的数量，则最佳选择的元素为公式提供了令人满意的分配。如果集合的最优选择覆盖的元素多于此，则公式不可满足。

算法 select 设置共享元素

Algorithm to select sets with shared elements

python

algorithm

optimization

set