| ID | 30094 |
| フルテキストURL | |
| 著者 |
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
|
| 資料タイプ |
学術雑誌論文
|
| 言語 |
英語
|
| 査読 |
有り
|
| DOI | |
| Submission Path | industrial_engineering/33
|
