有趣的算法問題

我在這裏有一個有趣的算法問題。問題與電子設計的模擬有關。有趣的算法問題

說例如，我有一個包含一些門的結構。說一個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

回答