有趣的算法问题

Question

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

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

000
001
...
111

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

因此，在输出上同时产生状态'0‘和'1’的输入向量的最小集合是{000,111}。

给出了一个设计，一些门的排列，给出了一个算法来寻找在最终输出上产生两个状态(即0和1)的输入向量的最小集合。

Answer 1

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

要得到其中一个输入，你可以选择一个任意的输入，看看它是0还是1。要找到另一个输出的输入，你需要一个SAT求解器。

维基百科推荐了一些可以使用的algorithms：

• DPLL algorithm
• Chaff algorithm
• GRASP
• WalkSAT
• etc...

如果你不想实现它，有一些工具可以随时使用SAT解算器：

• CVC3 (开源LGPL)
• Yices (非商业用途免费)

Answer 2

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