Multi-MaxSAT : ラグランジュ分解・調整法を用いたWeighted Max-SAT問題の解法(分散協調とエージェント)
スポンサーリンク
概要
- 論文の詳細を見る
Weighted Max-SAT問題とは, SAT問題における各節に重みを与え,満足できない節の重み和を最小にするような論理変数への真偽値の割当を求める最適化問題である. SAT問題に関する研究が近年劇的に進展したことを受けて, SAT問題の最適化版であるWeighted Max-SAT問題への関心も最近高まりつつある.本論文では,複数の部分問題(節集合)が互いに緩く結合することにより構成されるWeighted Max-SAT問題に対して特に有効な新しい解法としてMulti-MaxSATを提案する.評価実験によれば,部分問題間で共有される変数の数が比較的少ないとき, Multi-MaxSATは,最新の代表的な厳密解法や発見的解法よりも処理時間や発見できる解の質の面で優れている.
- 2009-01-01
著者
関連論文
- *-SAT:SATの拡張(最近のSAT技術の発展)
- Multi-MaxSAT : ラグランジュ分解・調整法を用いたWeighted Max-SAT問題の解法(分散協調とエージェント)
- 分散制約最適化問題へのソフトアーク整合の適用
- 描画用制約プログラミング言語 : CLDの設計
- 分散制約最適化問題に基づく提携構造形成問題
- 敵対者に対応する協調問題解決：限量記号付き分散制約充足問題
- 分散ラグランジュ緩和プロトコルにおける適応的な価格更新
- 一般化相互割当問題の上界値を求める分散ラグランジュ緩和プロトコル(マルチエージェントの理論,マルチエージェントの理論と応用)
- 一般化相互割当問題のための分散ラグランジュ緩和プロトコル(モデル/理論, ソフトウェアエージェントとその応用論文)
- An Easy-Hard-Easy Cost Profile in Distributed Constraint Satisfaction(Knowledge Processing)
- 情報収集のための分散タスク割り当て
- 情報収集のための分散タスク割り当て(「アクティブマイニング」及び一般 : 文部科学省科学研究費特定領域研究「情報洪水時代におけるアクティブマイニングの実現」公開シンポジウム)
- 情報収集のための分散タスク割り当て (知識ベースシステム研究会(第60回) 人工知能基礎論研究会(第52回) 小特集:「データマイニング」および一般) -- (文部科学省科学研究費特定領域研究 情報洪水時代におけるアクティブマイニングの実現)
- アクティブ情報統合のための動的分散制約充足プロトコル
- アクティブ情報統合のための動的分散制約充足プロトコル (テーマ:「アクティブマイニング」および一般)
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散制約充足におけるnogood学習の効果
- 複雑な局所問題に対応する分散制約充足アルゴリズム
- 分散不完全制約充足問題
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散breakout : 反復改善型分散制約充足アルゴリズム(並列処理)
- 環境設定ウォッチャーシステムの開発
- CSPの新しい展開 : 分散/動的/不完全CSP ( 制約充足問題の基礎と応用)
- ICMAS'95報告
- 分散制約充足におけるエージェントの非集中的組織化
- 山登り法を用いた分散制約充足における組織化
- 分散制約充足における組織化の負荷分散
- 山登り法を用いた分散制約充足における組織化
- 山登り法を用いた分散制約充足における組織化
- 情報収集のための分散タスク割り当て (知識ベースシステム研究会(第60回) 人工知能基礎論研究会(第52回) 小特集:「データマイニング」および一般) -- (文部科学省科学研究費特定領域研究 情報洪水時代におけるアクティブマイニングの実現)
- ポアソンSAT過程における節の脆弱度と期待寿命 (特集 「医療及び化学情報マイニング」および一般)
- 過制約な一般化相互割当問題に対する分散ラグランジュ緩和プロトコル
- OS-04 SAT技術の理論,実装,応用(オーガナイズドセッション報告,2012年度人工知能学会全国大会(第26回))
- 制約充足や最適化に関するエージェント研究の最近の動向(エージェント)
- Distributed Search Methods for Quantified Distributed Constraint Optimization Problem
- 制約充足や最適化に関するエージェント研究の最近の動向