algorithm - 有趣的算法题

Question

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

例如，我有一个包含一些门的结构。说一个三输入与门。有 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
• 等...

如果您不想实现它，可以使用现成的 SAT 求解器工具:

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