解可滿足性問題之新區域搜尋演算法

Abstract

可滿足性問題(satisfiability problem) 為計算複雜度NP 是否等於P 問題的核心問題， 並在人工智慧、硬體設計、VLSI 測試與驗證、 最佳化問題等領域有諸多應用。本研究中使用一 改良的區域搜尋演算法來解可滿足性問題。針對 目前為止所發展的演算法的弱點，以下列方法加 以克服：1. 提出新的適應度函數以加強對搜尋之 引導；2. 並於區域搜尋演算法中加入重設條件， 捨棄陷於區域最佳解附近的解以達到系統化的 搜尋。我們應用本論文所提出之演算法於 Gottlieb、Marchiori 與Rossi 於2002 年所匯整的 題組中，和其他演算法進行比較，獲得了不錯的 成果。