2002年
A minimal-state processing search algorithm for satisfiability problems
2001 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-5
- ,
- ,
- ,
- ,
- 開始ページ
- 2769
- 終了ページ
- 2774
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- IEEE
The satisfiability problem (SAT) is a typical NP-complete problem where a wide range of applications has been studied. Given a set of variables U and a set of clauses C, the goal of SAT is to find a truth assignment to variables in U such that every clause in C is satisfied if it exits, or to derive the infeasibility otherwise. This paper presents an approximation algorithm called a minimal,state processing search algorithm for SAT (MIPS_SAT). MIPS_SAT repeatedly transits minimal states in terms of the cost function for searching a solution through a construction stage and a refinement stage. The first stage greedily generates an initial state composed of as many satisfied clauses as possible. The second stage iteratively seeks a solution while keeping state minimality. The performance of MIPS_SAT is verified through solving DIMACS benchmark instances.
- リンク情報
- ID情報
-
- ISSN : 1062-922X
- Web of Science ID : WOS:000177404200487