快速算法反轉布爾和產品

我試圖實現一個非常非常快速的布爾表達式引擎。我用它來表示非常大的狀態空間中的狀態，所以我需要它來儘可能多地處理每秒的操作。這款發動機的基礎是產品的總和。儘管如此，我仍然遇到了優化NOT運算符的問題。例如，如果我有一個含有N個minterms的產品總和，其中每個minterm都有M個變量，那麼嘗試反轉就會產生M^N個minterms，然後使用espresso算法進行簡化。如果我在逆向操作期間間歇性地運行espresso算法，我可以加快一點並節省一些內存，但這還不夠。我懷疑自己是第一個遇到這個問題的人，並且我試圖做這項研究，但我似乎無法找到一個有效的方法來做到這一點。快速算法反轉布爾和產品

任何人都可以指向正確的方向嗎？

來源

2014-07-06 Ned Bingham

一般來說，你無法避免指數式的爆炸。 –

不，布爾表達式本質上是指數型的，但是您可以沿着這種方式減少布爾表達式以儘量減少指數式爆炸。據我所知，非經營者有很多模式，導致我相信使用濃縮咖啡就像使用從空間加速的2噸鎢棒敲擊指甲 –

不，你不能總是減少它。嘗試'（x1＆y1）|（x2＆y2）| ... |（xn＆yn）''。否定之後，這個長度爲2^n。 –

你可以把它在O(n+m)其中

answer = (x1 OR x2 OR .. xn) AND (y1 OR y2 OR .. ym)

但是你可以優化流程，以找出是否最終答案不會是1

answer = (x1 OR x2 OR .. xn) LOGICAL-AND (y1 OR y2 OR .. ym)

哪裏LOGICAL-AND將檢查當前值爲0，它將返回0O(n+1)

您可以將als Ø改變這一過程分爲設置操作

DEFINE X = { X1, X2, .. Xn } 
DEFINE Y = { Y1, Y2, .. Ym } 

ANSWER = X ∈ 1 AND Y ∈ 1

和優化這樣

IF X ∈ 1 
THEN RETURN Y ∈ 1 
ELSE RETURN 0

平均而言，你Time = i + j其中

i = position of left-most 1 in X 
j = position of left-most 1 in Y

最壞的情況下，將採取O(n+m)

000..001, 000..000 

000..001, 000..001

來源

2015-01-19 07:14:48

快速算法反轉布爾和產品

回答

相關問題