このエントリーをはてなブックマークに追加
ID 30094
フルテキストURL
著者
Funabiki, Nobuo Okayama University
Yokohira, Tokumi Okayama University
Nakanishi, Toru Okayama University
Tajima, Shigeto Osaka University
Higashino, Teruo Osaka University, Osaka
抄録

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

キーワード
SAT
heuristic algorithm
optimization
DIMACS
MIPS_SAT.
備考
Digital Object Identifier: 10.1109/ICSMC.2001.972986
Published with permission from the copyright holder. This is the institute's copy, as published in Systems, Man, and Cybernetics, 2001 IEEE International Conference on, 7-10 Oct. 2001, Vol. 4, Pages 2769-2774.
Publisher URL:http://dx.doi.org/10.1109/ICSMC.2001.972986
Copyright © 2001 IEEE. All rights reserved.
発行日
2001-10
出版物タイトル
Systems
4巻
開始ページ
2769
終了ページ
2774
資料タイプ
学術雑誌論文
言語
English
査読
有り
DOI
Submission Path
industrial_engineering/33