創建真值表

降低有序二元判定圖（ROBDD）是否有一個軟件包（最好的應用程序，而不是庫）從一個給定的事實表中創建精簡有序二叉決策圖（ROBDDs）（在某些文本格式）？創建真值表

來源

2013-03-25 tomash

隨着任何BDD庫，你可以做你想做的。當然，你必須自己寫一段代碼。

如果你正在尋找一個輕量級的工具，我經常使用這樣的小應用程序有一個快速預覽功能的BDD：

http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/

來源

2013-03-25 13:27:06 Lorenzo

提供的頁面並不完全是我想要的。我想提供一個真值表並計算它的ROBDD（即Reduced OBDD），它是給定函數的基於BDD的最小表示。該頁面不允許任何這樣的。 – tomash

好吧，它從作爲表達式給出的函數（實際上不是真值表）繪製出ROBDD。輸出是一個ROBDD，雖然標題只說BDD。或者你正在尋找最好的變量順序？ – Lorenzo

你也可以試試這個：http://formal.cs.utah.edu:8080/pbl/BDD.php

這是我迄今使用的BDDs的最佳工具。

來源

2013-06-10 14:48:39 remustata

的BDD是因爲在檢測到重複的子truthtables的嚴重依賴的存儲器約束的數據結構。你會發現大多數BDD包不完全是一個很好的適合大，一般真值表，非常稀少或高度重複表達而不是優化。

使用標準的BDD軟件包，您可以使用對變量進行操作的表達式。所以你必須迭代你的真值表，在表中構造一個類似於1的和的表達式。一路上，大多數圖書館將動態地重新排列變量以適應內存限制，導致另一個巨大的放緩。在大約24個變量之後，即使具有非常稀疏的真值表，這些庫也將開始在現代系統上發生顛簸。

如果您只是在給出一個真值表的最終BDD節點，並且它的變量排序已經隱式定義了，那麼使用一些Unix文本處理工具就可以省略外部庫和可怕運行時的很多複雜性。

上BDD的，Knuth的TAOCP v4.1b，良好的資源顯示BDD節點和他們的「珠」，子truthtables那些非方形字符串的等價性。我將解決一個更簡單的版本，ZDD具有類似的結構，稱爲「宙斯」：積極的部分子不完全爲零的真理。爲了推廣到BDD，用管道中的sed + grep替換正方形字符串來代替正數部分的非零字符串。

要打印truthtable（給定爲ASCII的單行文件「1'和」 0'，換行符在端）的所有zeads，設定的變量和文件名的數目之後運行下面的命令：

MAX=8; FILENAME="8_vars_truthtable.txt"; for ((ITER=0; ITER<=${MAX}; ITER++)) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done

這個擁有超過BDD包很多好處：

簡單，基本上沒有多餘的依賴關係。
外部排序意味着不像內存中的散列表那樣顛簸。
輕鬆parallelizeable &可擴展的，如果你瞭解行緩衝和磁盤緩存在for循環分叉的時候。
如果寫入中間文件，排序也會並行。

我經常使用它的真值表最多32個變量大，這是不可能現實地拿出使用BDD庫。它根本不會對內存系統徵稅，幾乎不會使用幾個MB。但是如果你擁有大量的RAM，像Linux這樣的像樣的操作系統將很樂意將它全部用於緩存磁盤，以使其更快。

來源

2015-02-11 13:42:45 user13972

回答

相關問題