| 講演名 | 2001/5/10 SAT充足解の偏りを利用した局所探索の高速化 岩間 一雄, 玉置 卓, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年、Schoningは3SATに対する最も良い上限、すなわち時間計算量が1.334^nである単純な局所探索アルゴリズムを示した。本稿では充足解にある種の偏りがあり、それについての情報が与えられたときに、アルゴリズムを高速化できることを示す。特に、充足解の0の個数と1の個数が偏っている場合、すなわちp_0nの0とp_1nの1を含む場合、例えばp_0=1/3ならば1.260^nでp_0=0.1ならば1.072^nで解を見つけることができる。そのような偏りは他の問題からSATに還元した例題によく見られる。本稿では具体例として、3次元マッチングから変換した例題に対してこの修正されたアルゴリズムが、総当たりよりも高速に動作することを示した。また、いくつかの実験も行なった。 |
| 抄録(英) | Recently Schoning has shown that a simple local-search algorithm for 3SAT achieves the currently best upper bound, i.e., an expected time of 1.334^n. In this paper, we show that this algorithm can be modified to run much faster if there is some kind of imbalance in satisfying assignments and we have a (partial) knowledge about that. Especially if a satisfying assignment has imbalanced 0's and 1's, i.e., p_1n 1's and (1- p_1)n 0's, then we can find a solution in time 1.260^n when p_1=1/3 and 1.072^n when P_1=0.1. Such an imbalance often exists in SAT instances reduced from other problems. As a concrete example, we investigate a reduction from 3DM and show our new approach is nontrivially faster than its direct algorithms. Preliminary experimental results are also given. |
| キーワード(和) | 充足可能性問題 / 局所探索 / 確率アルゴリズム |
| キーワード(英) | satisfiability / local search / randomization |
| 資料番号 | COMP2001-11 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/5/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | SAT充足解の偏りを利用した局所探索の高速化 |
| サブタイトル（和） | |
| タイトル（英） | Exploiting Partial Knowledge of Satisfying Assignments |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 充足可能性問題 / satisfiability |
| キーワード(2)（和/英） | 局所探索 / local search |
| キーワード(3)（和/英） | 確率アルゴリズム / randomization |
| 第 1 著者 氏名（和/英） | 岩間 一雄 / Kazuo Iwama |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 玉置 卓 / Suguru Tamaki |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2001/5/10 |
| 資料番号 | COMP2001-11 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 44 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |