python - 寻找最小公分母

Question

我遇到以下问题。我有一个 L 二进制条目数组。(如果感兴趣的话，L 通常在 2 到 8 之间。)所有可能的组合确实存在。因此，在一个实现中存在 2^L 数组。现在每个组合都会随机分配一个适应度值。适应度值也可以是 1 或 0。现在，例如，以下数组可能具有适合度值0:

1000
1010
1100
1001
1011

那么，所有具有 10__ 的数组都为零，并且所有具有 1_00 的数组都是正确的。这实际上是我的问题。我需要一种算法来找到这些相似之处并对它们进行排名。例如，10__ 的等级为 2，1_00 的等级为 3。大多数情况下，可以定义所有适应度为零的数组，或者具有少量的低等级，或者具有许多高等级。所以我的输出必须是有序的，并且我需要知道每个等级有多少个。我可以想象这是一个已知问题并且已经有解决方案了？我希望你能帮忙:)

Answer 1

假设这个适应度值可能取决于二进制条目中每个位的值，并且您正在搜索可以总结真值表的规则(我不确定我是否非常理解你的问题这一点)，你可以使用类似 Karnaugh map 的东西

这些 map 的工作原理如下:

列出您的因子(此处为第 1 位、第 2 位的值...)并将它们分成两个列表(一个用于行，一个用于列)。

使用 Gray Code 对每个列表进行排序.

将每个列表的值集分别用于表中的列和行。

您知道有一个表代表二进制条目的所有可能的值。

然后，列出表中每个条目的适合度值(1 或 0)。

然后，您必须在表中创建 True 值(或 false)组，这将允许您找到该组的规则(通过查找共同特征)。您通常按正方形或角对它们进行分组(参见第一个维基百科链接)。

这是一个具有 3 位条目的(简单)示例:

假设您有以下真值表:

ABC|R
-----
000|0
001|0
010|1
011|1
100|1
101|0
110|1
111|1

您可以建立以下卡诺表:

        AB
  |     00 |     01 |     11 |     10   <-- AB
--------------------------------------
0 |      0 | (1)  1 | (1)  1 | (2)  1
--------------------------------------
1 |      0 | (1)  1 | (1)  1 |      0

^
|
C

• 你可以将4个分组在中间，这4个B都为True，但是A和C可能为True或False，所以你可以这样总结:

  (1) B -> R

• 右上角还有一个:

  (2) A 和 !B 和 !C -> R

所以在这种情况下你的规则是:

B or (A and !B and !C) -> R

正如我在评论中提到的，我不确定您真正想要实现什么。但是，如果您试图找到一些简单的规则来总结您的真值表，也许列出此步骤找到的规则就足够了？

我没有提供 python 实现，但你可以在互联网上找到一些。 :) 至少你现在可以用纸和铅笔来做。 :)

如果有什么不清楚的地方，请随时询问!

这是您可以在互联网上找到的众多教程之一:

http://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html

PS:

B 表示 B 为 true，!B 表示 B 为 false。

PS-2:

您还可以使用 bool 代数来减少规则。