[4F1-OS-8a] AIと制約プログラミング(1/2)

[4F1-OS-8a-03] 解集合プログラミングを用いた独立集合遷移問題の解法に関する考察

〇山田 悠也¹、加藤 聖人²、小菅 脩司²、竹内 頼人¹、番原 睦則¹ (1. 名古屋大学大学院情報学研究科、2. 名古屋大学情報学部)

キーワード：独立集合遷移問題、解集合プログラミング、組合せ遷移

独立集合問題は，与えられた無向グラフ G と自然数 k に対して，G が要素数 k 以上の独立集合をもつかを判定し，もつ場合には独立集合を求める問題である．独立集合遷移問題とは，基となる独立集合問題とその二つの実行可能解が与えられたとき，一方から他方へ遷移制約を満たしつつ，実行可能解のみを経由して到達できるかを判定する問題である．独立集合遷移問題は一般にPSPACE 完全であることが知られている．

本発表では，独立集合遷移問題に対して，解集合プログラミング(ASP)を用いた解法について述べる．独立集合遷移問題を解くには，ステップ数を増やしながら複数の部分問題を繰り返し解く必要がある．しかし，各部分問題中の制約の大部分は共通であるため，ASP システムが同一の探索空間を何度も調べることになり，求解効率が低下するという問題点がある．この問題を解決するために，マルチショット ASP 解法を利用した独立集合遷移問題の ASP 符号化を提案する．提案手法の有効性を評価するために，組合せ遷移国際競技会 CoRe Challenge 2022 で使われる問題集を用いた実験結果を示す．