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)。

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

这是一个包含 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 实现，但您可以在 Internet 上找到一些。 :) 至少你现在可以用纸和铅笔来做。 :)

如有不明之处欢迎随时提问!

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

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

附言:

B 表示 B 为真，!B 表示为假。

PS-2:

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