有趣的算法问题

我在这里有一个有趣的算法问题。问题与电子设计的模拟有关。有趣的算法问题

说例如，我有一个包含一些门的结构。说一个3输入与门。有8个可能的输入即

在对这些8个输入，如果我只在两个输入(000)和(111)饲料，我得到两个可能的输出即0和1。

所以在输出上产生状态“0”和“1”的输入向量的最小集合是{000,111}。

这个问题给出了一个设计，一些门的排列，给出了一个算法来找到最小输入向量组，在最终输出上产生两个状态（即0和1）。

2010-08-04 sud03r

出于好奇：这是某种方式与VHDL有关吗？ – Scoregraphic 2010-08-04 14:05:50

对于给定的电路，根本不可能产生两种输出状态（即，x而不是x）。 – 2010-08-04 14:09:50

门是否总是3输入与门，或者它们可以是任何类型的门？ – mbeckish 2010-08-04 14:58:39

您的问题等同于解决boolean satisfiability problem。因此它是NP完全的。

要获得其中一个输入，您可以选择一个任意输入并查看它是否给出0或1.要找到给出另一个输出的输入，您需要一个SAT求解器。

维基百科提出了一些algorithms可用于：

如果你不想实现它，但是也有一些准备使用SAT求解器的工具：

2010-08-04 14:05:14

那么，如果我们尝试第一个输入向量，那么我们已经解决了一半的问题:-) – 2010-08-04 14:15:10

@Luter Blissett：+1好点！我最好在答案中提到这一点。 – 2010-08-04 14:23:50

这是用Quine McCluskey算法解决的。还有一些JavaScripts和工具可以解决你的问题。

2010-08-04 14:11:40 codymanix

– 2010-08-04 14:56:18

回答