一種EPCCL理論編譯算法

　　超擴展規(guī)則是對擴展規(guī)則的擴充，基于超擴展規(guī)則能夠求得任意兩個非互補且不相互蘊含的子句所能擴展出極大項集的交集、差集和并集，并將所得結(jié)果以EPCCL（each pair of clauses contains complementary literals）理論的形式保存．基于超擴展規(guī)則的性質(zhì)，提出一種EPCCL理論編譯算法：求交知識編譯算法IKCHER（intersection　approach to knowledge compilation based on hyper extension rule）．該算法適合難解類SAT問題的知識編譯，也是一種可并行的知識編譯算法．研究了如何實現(xiàn)多個EPCCL理論的求交操作。證明了EPCCL理論的求交過程是可并行執(zhí)行的，并設計了相應的并行求交算法PIAE（parellel intersection of any number of EPCCL）．通過對輸入EPCCL理論對應普通子句集的利用，設計了一種高效的并行求交算法imp-PIAE（improvement of PIAE）．基于上述算法，還設計了兩種并行知識編譯算法P-IKCHER（IKCHER with PIAE）和impP-IKCHER（IKCHER with imp-PIAE）。分別采用PIAE并行合并算法和imp-PUAE并行合并算法．最后，通過實驗驗證了，大部分情況下，IKCHER算法的編譯質(zhì)量是目前為止所有EPCCL理論編譯器中最優(yōu)的．P-IKCHER算法所使用的合并策略并沒有起到加速的效果，反而使得編譯效率和編譯質(zhì)量有所下降；impP-IKCHER算法提高了IKCHER算法的編譯效率，CPU四核環(huán)境下最高可提高2倍．