WEKO3
アイテム
ADSAT：敵対者が存在するMaxSAT
https://ipsj.ixsq.nii.ac.jp/records/212819
https://ipsj.ixsq.nii.ac.jp/records/21281994f79c67-9110-4c97-aaea-747903350479
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ICS21204013.pdf (756.6 kB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-09-08 | |||||||||||
| タイトル | ||||||||||||
| タイトル | ADSAT：敵対者が存在するMaxSAT | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 九州大学大学院システム情報科学府 | ||||||||||||
| 著者所属 | ||||||||||||
| 九州大学大学院システム情報科学府 | ||||||||||||
| 著者所属 | ||||||||||||
| 九州大学大学院システム情報科学府 | ||||||||||||
| 著者名 |
菅原, 知也
× 菅原, 知也
× 越村, 三幸
× 横尾, 真
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 本論文では，ADSAT (Attacker Defender SAT) と呼ばれる，防御者と敵対者が存在する場合の MaxSAT について論じる．MaxSAT は，充足可能性問題 (SAT) を最適化問題に拡張したものであり，その目的は充足する節の数の最大化である．ADSAT において，防御者は充足する節の数の最大化を目的とし，敵対者はその最小化を目的とする．本研究の目的は，敵対者のあらゆる攻撃を想定した防御者の最適解を求めることである．このような頑健な解を求めることは理論上のみならず実用上も重要である．先行研究において，ADSAT を解くアルゴリズムとして IBR (Iterated Best Response) が提案されている．しかしながら，ADSAT は ΣP2 完全問題であるため，小さいサイズの問題でも実用的な時間で最適解を求めることが非常に困難である．そこで本論文では，ADSAT の近似解を求めるアルゴリズムとして，IBR を簡略化した BP-BR (Best Preference Best Response) と AE (Attack Enumeration) の 2 種を提案する．特に敵対者の攻撃を限定した場合，AE は効率的に近似解を求めることができる．また，計算機実験により 3 つのアルゴリズムの性能を比較し，評価を行う． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA11135936 | |||||||||||
| 書誌情報 |
研究報告知能システム（ICS） 巻 2021-ICS-204, 号 13, p. 1-5, 発行日 2021-09-08 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-885X | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
