W4256030467
馬野 洋平, 正彦 酒井, 直樹 西田 et al. · IEICE INFORMATION AND SYSTEMS SOCIETY JOURNAL · 2012
草刈 圭一朗 名古屋大学 本論文 [1] では,論理式の充足可能性判定問題 (SAT 問題)を解く SAT ソルバの高速化を行う ための一手法を提案しました.近年実用化され てきている高速な SAT ソルバのほとんどが,入 力を和積形論理式 (CNF) に限定し,その形式を 最大限に利用して高速化を図っています.これ に対して,本論文では基本対称関数と呼ばれる ブール関数に対応する節(基本対称節)も許す ように入力の形式を拡張することで,充足判定 の際の処理の一部が軽量化でき,SAT ソルバの 高速化が可能であることを示しました.ここで, リテラル(変数やその否定)の和である節が一 つ以上のリテラルが真であるときに成り立つの に対して,n-基本対称節はちょうど n 個のリテ ラルが真のときに成り立つというものです. 本論文の研究開始のきっかけは数独 [2] という パズルでした.このパズルは 9 × 9 のマスに 1 か ら 9 までの数字を,縦(9 マス) ・横(9 マス) ・ 3 × 3 ボックス(9 マス)等のそれぞれについて 数字が重複しないように入れるというものです. この制約を論理式に書き下して SAT 問題を解く ことによって数独の問題を解くのは,論理式の 生成もやさしく,また,miniSAT などの既存の SAT ソルバで短時間で解けます.しかし,私達 が作成していた数独の問題作成を対話的に行う システムでは,ユーザの操作に対して問題を最 悪 18 回解いて表示する必要があり,高速化の必 要性を感じていました. パズル問題などを SAT 問題に落し込んで解く 際のコーディングの常套手段なのですが,例えば * 現在,日立ソリューションズ
Cited by 0 works. doi:10.1587/ieiceissjournal.16.4_21 Open-access PDF