日本ソフトウェア科学会第 41 回大会 (2024 年度) 講演論文集

解集合プログラミングを用いた遷移コストと遷移長を考慮したパレート最適な組合せ遷移
高田 和紀

楊 東 番原 睦則

本稿では，遷移コストと遷移長の両方を考慮した多目的組合せ遷移最適化問題 (MO-CROP) を新たに提案し，解集合プログラミング (ASP) を用いた解法について述べる．MO-CROP とは，基となる組合せ問題，その 2 つの実行可能解，複数の重み付き遷移制約が与えられたとき，一方から他方へ，遷移コストと遷移長の両方を考慮したパレート最適な遷移系列を求める問題である．従来の組合せ遷移問題が，ただ一つの遷移制約を考慮するのに対し，MO-CROP では複数の重み付き遷移制約を考慮する点が大きく異なる．提案解法は，遷移長を制限した単目的組合
せ遷移最適化問題を，遷移長を増やしながら繰り返し解くことによって最適遷移系列を求める．提案アルゴリズムの特長は，遷移長の上限値を自動で適切に更新することによって，パレート最適な遷移系列の全列挙を保証できる点である．提案手法の有効性を評価するために，独立集合遷移に基づく MO-CROP を解く ASP 符号化を新たに考案
し，CoRe Challenge 2022 のベンチマーク問題集を用いた実験結果について述べる．

科学の分野を中心に急速に発展し理論的な基盤が整

1 はじめに備されている．特に計算複雑性理論の研究では，基組合せ遷移 (Combinatorial Reconﬁguration; [17]となる組合せ問題が NP 完全の場合，その組合せ遷[25] [31]) とは，組合せ問題の実行可能解が形成する解移問題の多くが PSPACE 完全になることが明らか

空間を対象とする研究分野である．解空間はグラフとになっている [17]．そのような例としては，命題論理

して定義され，頂点は実行可能解を表し，辺は遷移制の充足可能性判定 (SAT) 遷移 [11] [23]，独立集合遷

約 (隣接関係ともよばれる) を満たす 2 つの実行可能

移 [17] [20]，支配集合遷移 [2] [12] [13] [28], グラフ彩色

解の組を表す．基となる組合せ問題が実行可能解の存

遷移 [3] [4] [5]，クリーク遷移 [19]，ハミルトン閉路遷在性を判定するのに対し，組合せ遷移問題は解空間グ

移 [29]，集合被覆遷移 [17] などがあげられる．

ラフの構造や性質を分析することを主眼とする．

ごく最近では，国際組合せ遷移競技会 CoRe Chal-

組合せ遷移の到達可能性問題 [17] とは，基となるlenge 2022–2023 [26] が 2 年連続で開催され，組合組合せ問題とその 2 つの実行可能解が与えられた

せ遷移問題の解法アルゴリズムなど実践的な研究もとき，一方から他方へ，遷移制約を満たしつつ，実盛んになっている [6] [18] [30] [32] [33]．しかしながら，行可能解のみを経由して到達可能かどうかを判定す

組合せ遷移の従来研究の大多数は，ただ一つの遷移制る問題である．本稿ではこの問題を組合せ遷移問題

約のみを考慮した遷移系列の有無を対象としており，(Combinatorial Reconﬁguration Problem) とよぶ．

複数の重み付き遷移制約を考慮した研究はほとんど組合せ遷移問題の研究は，ここ 20 年で理論計算機
Pareto-optimal Combinatorial Reconﬁguration considering Cost and Length based on Answer Set
Programming
Kazuki Takada, Dong Yang, Mutsunori Banbara, 名
古 屋 大 学 大 学 院 情 報 学 研 究 科, Graduate School ofInformatics, Nagoya University.

なされていない．
本稿では，遷移コストと遷移長の両方を考慮した多目的組合せ遷移最適化問題 (Multi-Objective Com-

binatorial Reconﬁguration Optimization Problem;
MO-CROP) を新たに提案し，解集合プログラミングを用いた解法アプローチについて述べる．提案する

MO-CROP は，基となる組合せ問題，その 2 つの実

この符号化は，従来の TJ 型独立集合遷移問題の行可能解，複数の重み付き遷移制約が与えられたとASP 符号化 [33] と，本稿で新しく考案した TSき，一方から他方へ，遷移コストと遷移長の両方を考型独立集合遷移問題を解く ASP 符号化の自然な慮したパレート最適な遷移系列を求める問題である．

拡張となっている．

従来の組合せ遷移問題がただ一つの遷移制約を考慮

5. 提案アプローチの有効性を評価するために，するのに対し，MO-CROP では複数の重み付き遷移

CoRe Challenge 2022 のベンチマーク問題集 (計制約を考慮する点が大きく異なる．解集合プログラ

326 問) を用いて実験を行った．その結果，TJ–TS

ミング (Answer Set Programming; ASP [1] [10] [24])型独立集合遷移最適化問題 212 問 (全体の 65%)

は，論理プログラミングから派生した比較的新しいプについてパレート最適な遷移系列を全列挙する

ログラミングパラダイムである．MO-CROP に対しことができた．

て ASP を用いる利点としては，ASP 言語の高い表

提案アプローチは，組合せ遷移の実践的研究，およ

現力を生かして基の組合せ問題を簡潔に記述できる

び，ASP の組合せ遷移への応用研究に寄与するもの

点，遷移最適化問題への拡張も容易である点，マルチである．本稿の ASP 符号化は ASP システム clingo

ショット ASP 解法 [9] を利用することで，効率的なの言語で記述されている．ASP の言語構文について

遷移系列探索の実装が可能である点があげられる．

は第 3 節で簡単に述べるが，より詳しい説明につい本稿の主な貢献および結果は以下の通りである．

ては文献 [8] を参照いただきたい．

1. 複数の重み付き遷移制約をもつ多目的組合せ遷
移最適化問題 (MO-CROP) を提案する．この問

2 準備: 組合せ遷移問題

題は，ただ一つの遷移制約を考慮する従来の組合組合せ遷移問題とは，基となる組合せ問題とその 2

せ遷移問題の自然な拡張になっており，遷移コス

つの実行可能解 Xs と Xg ，および一つの遷移制約がトと遷移長のトレードオフを考慮した多様な最与えられたとき，遷移系列

適遷移系列を求める問題である．

Xs = X0 → X1 → X2 → · · · → Xℓ = Xg

(1)

2. MO-CROP に対する解法アルゴリズムを提案すが存在するかどうかを判定する問題である．Xs はス

る．提案解法は，遷移長を制限した単目的 CROP

タート状態，Xg はゴール状態を表す．各状態 Xi はを，遷移長を増やしながら繰り返し解くことに基となる組合せ問題の実行可能解を表す．X → X ′よって最適遷移系列を求める．提案アルゴリズム

は遷移制約に従って状態 X から状態 X ′ へ 1 回遷移の特長は，遷移長の上限値を自動で適切に更新すすることを表す．ℓ は遷移系列の長さ，すなわち，遷ることによって，パレート最適な遷移系列の全列移長を表す．(1) のような遷移系列が存在するとき，

挙を保証できる点である．

問題は到達可能であるといい，存在しないとき，到達

3. ASP に基づく MO-CROP の汎用ソルバー re-

不能であるという．

congo opt の設計と実装を詳述する．recongo opt

組合せ遷移問題の例として独立集合遷移問題を考は，ASP システム clingo のマルチショット ASP

える．無向グラフ G = (V, E) が与えられたとき，サ

解法 [9] を用いて解法アルゴリズムを実装するこイズ k の独立集合 (Independent Set) V ′ ⊆ V とは，とにより，基礎化にかかるオーバーヘッドを抑え| V ′ |= k であり，任意の 2 頂点 v1 , v2 ∈ V ′ についてつつ，獲得した学習節を再利用した効率的な遷移(v1 , v2 ) ∈/ E となるような V の部分集合 V ′ である．

系列の探索が可能である．

独立集合問題 (Independent Set Problem) は，与え4. MO-CROP のケーススタディとして，トークられたグラフ G と自然数 k に対して，G がサイズ k

ンジャンピング (TJ) とトークンスライディングの独立集合をもつかどうかを判定する問題である．独(TS) の 2 つの遷移制約をもつ，TJ–TS 型独立立集合遷移問題 (Independent Set Reconﬁguration

集合遷移最適化問題を解く ASP 符号化を示す．

Problem) は，独立集合問題を基とする組合せ遷移問

スタート

ゴール

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

TJ

→

1

2

3

4

5

6

7

8

9

10

11

12

TJ

X0

→

X2

図1

TJ 型独立集合遷移問題の例

立集合を表す．
独立集合に含まれるすべての頂点にトークン (to-

2

3

4

5

6

7

8

9

10

11

12

TJ

X1

題である．すなわち，遷移系列 (1) の各状態 Xi は独

1

→

X3

プログラムと呼ぶ．
論理プログラムは，以下の形式のルールの集合である (0 ≤ m ≤ n)．

ken) が置かれると仮定すると，独立集合遷移問題は，

a0 :- a1 , . . . ,am , not am+1 , . . . ,not an .

トークンを移動する問題と考えることもできる．ス

各 ai はアトム，not はデフォルトの否定，カンマ(2)

タート状態の独立集合に含まれるすべての頂点にトー(“,”) は連言を表す．“:-” の左側をヘッド，右側をボクンが置かれている．トークンは遷移制約を満たす

ディとよぶ．ピリオド (“.”) はルールの終わりを表ように移動させることができる．ただし，トークンがす．ルール (2) の直観的な意味は，「a1 , . . . , am がす

置かれた頂点の集合は，つねに独立集合問題の制約

べて成り立ち，am+1 , . . . , an のそれぞれが成り立たを満たさなければならない．最終的に，トークンの置ないならば，a0 が成り立つ」である．ボディが空のかれた頂点の集合がゴール状態の独立集合と一致す

ルールはファクトとよばれ，“:-” を省略して a0 . とれば到達可能となる．独立集合遷移問題の遷移制約記述される．ヘッドが空のルールは一貫性制約とよばとしては，1 回の遷移でちょうど一つのトークンが移れる．

動するトークンジャンピング (Token Jumping; TJ):- a1 , . . . ,am , not am+1 , . . . ,not an .

と，1 回の遷移でちょうど一つのトークンが隣接頂点

空 の ヘッド は 矛 盾 を 表 す．例 え ば ，一 貫 性 制 約へ移動するトークンスライディング (Token Sliding;“:- a1 ,a2 .” は，「a1 と a2 が両方同時に成り立つ

TS) の 2 種類が広く研究されている．

と矛盾」，すなわち，「a1 と a2 が両方同時に成り立つ

TJ 型独立集合遷移問題の例を図 1 に示す．独立集ことはない」を意味する．

合のサイズは k = 3 とし，黄色の頂点はトークンが組合せ問題を記述する際に便利な拡張構文として，置かれていることを意味する．この例では，3 回の遷選択子と個数制約がある．選択子 “{a1 ; . . . ;an }.” を移でスタート状態 (X0 ) からゴール状態 (X3 ) へ到達

ファクトとして書くと，「アトム集合 {a1 , . . . , an } の任可能である．各状態 Xi は独立集合問題の制約を満た意の部分集合が成り立つ」を意味する．選択子の両端にしている．また各遷移では，ちょうど 1 個のトークン

選択可能な個数の上下限を付けることによって個数制約が他の頂点へ移動する遷移制約 TJ を満たしている．

を記述できる．例えば，“:- not lb {a1 ; . . . ;an } ub.”と書くと，「a1 , . . . , an のうち，lb 個以上 ub 個以下

3 準備: 解集合プログラミングが成り立つ」を意味する．選択子と個数制約の中括

解集合プログラミングは，論理プログラミングから弧内には，アトムの他にリテラル ℓ や条件付きリテ

派生した比較的新しいプログラミングパラダイムでラル ℓ0 :ℓ1 , . . . ,ℓn も記述可能である．リテラル ℓ はある．ASP の言語は，一般拡張選言プログラムに基アトム a またはその否定 not a である．条件付きリづいている [16]．本節では，そのサブクラスである標

テラル ℓ0 :ℓ1 , . . . ,ℓn は，ℓ1 , . . . , ℓn が成り立つとき，

準論理プログラム (normal logic program) について

ℓ0 が成り立つことを表す．他にも，組合せ最適化問説明する．本稿では，標準論理プログラムを単に論理

題を解くための最大化関数 #maximize や最小化関数

1 #program base.

k(3).

2 :- not in(X,0), start(X).
node(1).

node(2).

node(3). node(4).

node(5).

node(7).

node(8).

node(9). node(10). node(11). node(12).

3node(6).

4 #program step(t).
5 K { in(X,t): node(X) } K :- k(K).

edge(1,2).

edge(1,5).

edge(2,3).

edge(2,6).

edge(3,4).

6 :- in(X,t), in(Y,t), edge(X,Y).

edge(3,7).

edge(4,8).

edge(5,6).

edge(5,9).

edge(6,7).

7

edge(6,10).

edge(7,8).

edge(7,11). edge(8,12). edge(9,10).

8 token_removed(X,t) :- in(X,t-1), not in(X,t), t > 0.
9 :- not 1 { token_removed(X,t) } 1, t > 0.

edge(10,11). edge(11,12).

10
start(1).

start(6).

start(9).

11 #program check(t).

goal(3).

goal(8).

goal(11).

12 :- not in(X,t), goal(X), query(t).

リスト 1

独立集合遷移問題のインスタンス (図 1) のASP ファクト表現#minimize も用意されている．

リスト 2

TJ 型独立集合遷移問題を解く ASP 符号化(TJ 符号化)

トム node/1 は頂点を，edge/2 は辺をそれぞれ表す．

ASP システムは，与えられた論理プログラムか

アトム start/1 はスタート状態に含まれる頂点を，ら，安定モデル意味論 [10] に基づく解集合を計算す

goal/1 はゴール状態に含まれる頂点をそれぞれ表す．

るプログラムである．ASP システムの多くは，変数

例えば，start(1) は頂点 1 がスタート状態の独立集を含む論理プログラムを変数を含まない論理プログ合に含まれることを表している．

ラムに基礎化したのち，基礎ソルバーを用いて解集合

つぎに，文献 [33] で提案された TJ 型独立集合遷移を計算する．本稿で用いる ASP システム clingo も，問題を解く論理プログラム (ASP 符号化) をリスト 2

基礎化のためのグラウンダー gringo と基礎ソルバーに示す．この符号化は，base, step(t), check(t) のclasp をシームレスに結合したものである．

3 つのサブプログラムから構成されている．step(t)マルチショット ASP 解法は，ファクトやルールと check(t) のパラメータ t はステップ数 (状態 Xi

を動的に追加・変更・削除しながら一連の論理プロの i) を表す定数である．サブプログラム base はス

グラムを効率良く解くための方法である．clingo にタート状態に関する制約を表す．アトム in(X,t) は，は，マルチショット ASP 解法のため新しい言語構文

ステップ t において頂点 X にトークンが置かれているとして，#program 文と#external 文が導入されていことを意味する．2 行目のルールは，ステップ 0 とス

る．前者は #program p(t). の形式で，ASP プログ

タート状態でトークンの配置が一致することを一貫性

ラムをいくつかのパラメータ付きサブプログラムに制約を用いて強制している．サブプログラム step(t)分割するために使用される．p はサブプログラム名をは，独立集合問題の制約と遷移制約を表す．5–6 行目

表し，パラメータ t は定数である．この t は省略可能のルールは独立集合問題の制約を表す．5 行目のルーである．base はデフォルトのサブプログラムであり，ルは，各ステップ t において，独立集合のサイズが#program 文によって明示的に指定されないすべてのちょうど K 個であることを個数制約を用いて強制してファクトとルールを含む．後者は #external a. のいる．6 行目のルールは，各ステップ t において，隣形式で，外部アトム a の真偽値が (clingo の Python

接する頂点 X と Y が同時に独立集合に含まれること

API を使って) 後で変更できることを意味する．

はないことを一貫性制約を用いて強制している．8–9

論理プログラムの例として，第 2 節の図 1 に示

行目のルールは TJ 遷移制約を表す．8 行目のルー

した TJ 型独立集合遷移問題を考える．まず最初に，

ルでは，各ステップ t で，頂点 X からトークンが移

図 1 の問題インスタンスのファクト形式をリスト 1

動したことを表す補助アトム token_removed(X,t)に示す．アトム k/1 は独立集合のサイズを表す．アを導入する．9 行目のルールは，各ステップ t で，

は，ちょうど 1 個のトークンが隣接頂点へ移動する
1 #program base.
2 :- not in(X,0), start(X).

TS 遷移制約を満たしている．
考案した TS 型独立集合遷移問題を解く ASP 符号

3
4 #program step(t).

化をリスト 3 に示す．TJ 型独立集合遷移問題 (リス

5 K { in(X,t) : node(X) } K :- k(K).
6 :- in(X,t), in(Y,t), edge(X,Y).

ト 2) との違いは，10 行目のルールが追加されている

7

点のみである．このルールは，各ステップ t，各頂点

8 token_removed(X,t) :- in(X,t-1), not in(X,t), t>0.
9 :- not 1 { token_removed(X,t) } 1, t>0.
10 :- not 1 { in(Y,t) : edge(X,Y) ; in(Y,t) : edge(Y,X) } 1,
token_removed(X,t).
11

X について，X からトークンが移動するならば，移動
先はその隣接頂点であることを個数制約で強制している．これは，互いに隣接する 2 頂点には同時にトークンが置かれないという独立集合の性質を利用して

12 #program check(t).
13 :- not in(X,t), goal(X), query(t).

おり，既存の TJ 型独立集合遷移問題の ASP 符号化[33] の自然な拡張となっている．

リスト 3

TS 型独立集合遷移問題を解く ASP 符号化(TS 符号化)

5 遷移コストと遷移長を考慮した多目的組合
せ遷移最適化

token_removed(X,t) が真になる頂点がただ一つで多目的組合せ遷移最適化問題 (MO-CROP) とは，基あることを個数制約を用いて強制している．サブプロとなる組合せ問題とその 2 つの実行可能解 Xs と Xg ，

グラム check(t) はゴール状態に関する制約を表す．

および，複数の重み付き遷移制約が与えられたとき，

12 行目のルールは，ステップ t とゴール状態でトー遷移系列 Xs = X0 → X1 → X2 → · · · → Xℓ = Xg

クンの配置が一致するかどうかをチェックする．ここのうち，遷移コストと遷移長の両方を考慮したパレー

で，query(t) は#external 文によって宣言された外ト最適な遷移系列を求める問題である．従来の組合せ

部アトムである．この外部アトムの真理値を clingo

遷移問題と同様に，Xs はスタート状態，Xg はゴーの Python API を用いて動的に変更することにより，

ル状態，各状態 Xi は基となる組合せ問題の実行可能

12 行目のルールの活性・非活性を制御できる．

解を表す．X → X ′ は複数の重み付き遷移制約のい最後に，問題インスタンスのファクト表現 (リス

ずれか一つに従って状態 X から状態 X ′ へ 1 回遷移ト 1) と独立集合遷移問題を解く ASP 符号化 (リスすることを表す．遷移コストは各遷移で適用された遷

ト 2) を入力として，clingo 上に実装された組合せ遷

移制約の重みの総和を表す．遷移長は遷移系列の長さ移問題ソルバー recongo を実行することで，図 1 のℓ を表す．

遷移系列を求めることができる．

提案解法は，与えられた MO-CROP に対して，制限された長さでの最小コスト遷移系列を求める問題

4 TS 型独立集合遷移問題の ASP 符号化

を論理式として表現し，その論理式を ASP システム

本節では，TS 型独立集合遷移問題を解く ASP 符

等の汎用ソルバーを使って解くことにより，パレート

号化について述べる．独立集合遷移問題の TS 遷移

最適な遷移系列を全列挙する方法である．ソルバーが制約は，TJ 遷移制約の特殊形である．TJ 遷移制約

最適解を求めた場合，制限された長さでの最小コスト

では 1 回の遷移でちょうど一つのトークンが移動す遷移系列が得られることを意味する．逆に充足不能とるのに対し，TS 遷移制約ではその移動先が (移動元

判定した場合，制限された長さでは到達可能な遷移系の) 隣接頂点に限定される．TS 型独立集合遷移問題

列が存在しないことを意味する．この場合，遷移系列の例を図 2 に示す．この例では，6 回の遷移でスターの長さを増加させた論理式を構成し，再びソルバーにト状態からゴール状態へ到達可能である．また各状態よる実行を繰り返す．提案解法は，パレート最適な遷は独立集合問題の制約を満たしている．また各遷移で移系列を探すだけで，到達不能の証明はできない不完

スタート
1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

TS

→

1

2

3

4

5

6

7

8

9

10

11

12

TS

X0

→

1

2

3

4

5

6

7

8

9

10

11

12

TS

X1
ゴール

→

X2

1

2

3

4

5

6

7

8

9

10

11

12

X3
↓ TS

1

2

3

4

5

6

7

8

9

10

11

12

TS

←

1

2

3

4

5

6

7

8

9

10

11

12

TS

X6

X5

図2

TS 型独立集合遷移問題の例←

X4

全な手続きである．検査すべき遷移系列の長さに 上

この ψℓ の最適解が求まると，制限された遷移長 ℓ限が存在する場合 (例えば，基の組合せ問題の直径がにおける最小コスト遷移系列が求まる．遷移コストと既知の場合) には，完全な手続きとなる．

遷移長を考慮したパレート最適な遷移系列を列挙する定式化. MO-CROP が与えられたとき，基となには，遷移長 ℓ を 0 から 1 ずつ増やしながら，ψℓ をる 組 合 せ 問 題 の 変 数 集 合 を x = {x1 , x2 , ..., xn }繰り返し解き，得られた最小コスト遷移系列のパレー

で 表 す．ま た ，各 状 態 Xt (t ≥ 0) の 変 数 集 合 を

ト最適性をチェックすればよい．しかしながら，現段= {xt1 , xt2 , ..., xtn } と表記する．スタート状態を表

階では遷移長の上限がわからないため，パレート最適す論理式を S(x)，基となる組合せ問題の制約を表すな遷移系列の全列挙を保証することはできない．つま論理式を C(x)，ゴール状態を表す論理式を G(x) とり，パレートフロントを知ることはできない．この問

x

t

′

する．与えられた m 個の遷移制約を Tj (x, x )，その題を解消するには，得られた遷移コストをもとに，遷重みを wj > 0 で表す (1 ≤ j ≤ m)．このとき，遷移長 ℓ の上限値 I max を適切に更新する必要がある．

移制約を表す論理式 T (x, x′ ) と遷移コスト O(x, x′ )パレートフロントの保証. 遷移長 ℓ の上限値 I max をは，以下のように表される．
()
T (x, x′ ) = exact one T1 (x, x′ ), . . . , Tm (x, x′ )m∑wj Tj (x, x′ )O(x, x′ ) =更新するための基本的アイデアは，パレート最適な遷

j=1

T (x, x′ ) は m 個の遷移制約のうち，ちょうど一つが適用されることを表す．スタート状態から ℓ 回遷移した∧後の状態 Xℓ の変数集合 xℓ は，S(x0 )∧ ℓt=0 C(xt )∧∧ℓt−1, xt ) を満たす．そして，ゴール状態と一
t=1 T (x
致する最小コスト遷移系列を求めるためには，G(xℓ )
)
(∑
ℓ
t−1
, xt ) を付け加と目的関数 minimize
t=1 O(xえた論理式 ψℓ を構成すればよい．

ψℓ = S(x0 ) ∧

ℓ
∧

ℓ
∧

C(xt ) ∧T (xt−1 , xt )
t=0
( t=1
)
ℓ
∑
ℓ
t−1
t
∧ G(x ) ∧ minimizeO(x , x )t=1

移系列が見つかるたびに I max の値を更新し，遷移長 ℓを 0 から I max まで変化させて探索を行うことで，パレート最適な遷移系列の全列挙を保証する点である．遷移制約の最小の重みを wmin = min{wj : 1 ≤ j ≤ m}とすると，遷移長 ℓ における遷移系列の遷移コストの下限は ℓwmin となる．いま，直近で求まった
パレート最適な遷移系列の遷移コストを W とすると，ℓwmin > W となるような ℓ では，W を下回る
遷移コストは得られず，パレート最適な遷移系列は存在しない．したがって，ℓwmin ≤ W ，すなわちℓ ≤ W/wmin を満たす ℓ まで探索すればよい．以上
より，I max = ⌊W/wmin ⌋ と更新することでパレート最適な遷移系列の全列挙を保証できる．
アルゴリズム. 提案解法は，MO-CROP が与えら

recongo opt
MO-CROP
インスタンス-- ASP ファクト - ASP システム - パレート最適な
遷移系列

変換器

6
論理プログラム

図3?

提案
アルゴリズム提案アプローチの構成

れたとき，ψℓ を論理プログラムとして表現し，その論最後に，i > I max となるとき，41 行目で model∗ を理プログラムを ASP システムで実行することにより，出力する．

パレート最適な遷移系列を全列挙する．より正確には，ソルバーの実装．提案アルゴリズムを高速 ASP シ

ψℓ の ℓ を 0 から 1 ずつ増加させながら繰り返し実行

ステム clingo に実装したソルバー recongo opt を開発

し，ℓ が上限値 I

maxを超えたとき，パレート最適な遷した．recongo opt は，与えられた MO-CROP イン

移系列がすべて得られる．しかしながら，毎回 ψℓ をスタンス (ASP ファクト形式) と MO-CROP を解く

再構築するのは明らかに非効率である．この問題を解ASP 符号化を入力とし，高速 ASP システム clingo

決するために，マルチショット ASP 解法 [9] を用いるの Python API を用いて実装した提案アルゴリズム

ことで，インクリメンタルに ψℓ を構成する．具体的を用いて解を求める (図 3 参照)．

ℓには，ψℓ は，ψℓ−1 に C(x )，T (xO(ℓ) = minimize O(x

ℓ−1

ℓ−1

ℓ

ℓ

, x )，G(x )，ℓ, x ) を追加し，G(xℓ−1 )6 独立集合の多目的遷移最適化

を不活性化することで，インクリメンタルに構成でき多目的独立集合遷移最適化問題とは，独立集合問る．これにより，提案アルゴリズムは，学習節の再利

題に基づく多目的組合せ遷移最適化問題である．多用や基礎化のオーバーヘッド軽減による効率的な最目的独立集合遷移最適化問題の例を図 4 に示す．遷

適遷移系列の探索が可能である．なお，ASP システ∑
ム clingo において，minimize ℓt=1 O(xt−1 , xt ) と∧ℓ
t−1, xt ) は同値である．
t=1 minimize O(x移制約としては TJ と TS の両方を考慮し，重みをそ
レート最適な遷移系列のうち，(遷移コスト, 遷移長)

提案アルゴリズムの擬似コードをアルゴリズム 1= (13,5) の最適遷移系列を示している．すなわち，5に示す．変数 i は各状態 Xi のステップ番号 i を表す．

回の遷移でスタート状態からゴール状態へ到達し (1∗

変数 model はパレート最適な遷移系列を格納する配∗れぞれ 5 と 2 とする．この例は，全部で 4 つあるパ

回目が TJ で 2–5 回目が TS)，その遷移コストは 13列を表し，cost は直近に求まったパレート最適な遷である．各状態は独立集合問題の制約を満たしてい移系列の遷移コストを表す．変数 ret, model, cost にる．また各遷移では，TJ か TS のいずれかに従っては，ASP システムの実行結果，解集合，その遷移コちょうど 1 個のトークンが移動している．他の 3 つストが保存される．8 行目で追加される#external 文のパレート最適な遷移系列は，(遷移コスト, 遷移長)tは，ゴール状態を表す G(x ) の活性・不活性を切り替= (12,6), (14,4), (15,3) である．そのうち，(15,3) はえるために使われる．各ステップ i において，10–25

TJ のみの遷移系列 (図 1) に対応し，(12,6) は TS の行目で ψi をインクリメンタルに構成する．その後，

みの遷移系列 (図 2) に対応する．このように，多目

26 行目で ASP システムを用いて遷移長 ℓ = i にお的独立集合遷移最適化問題では，従来の独立集合遷移

ける最小コスト遷移系列を求め，27 行目でステップ問題と比較して，(13,5) や (14,4) のような遷移コスi の値を 1 増やす．31–38 行目では，得られた遷移系

トと遷移長のトレードオフを考慮した多様な最適遷列の遷移コストが直近で求まったパレート最適な遷移移系列を得ることができる．

系列の遷移コストより小さくなるとき，その遷移系

多目的独立集合遷移最適化問題を解く TJ–TS 符号

列を model∗ に格納し，cost∗ と I max の更新を行う．

化をリスト 4 に示す．従来の独立集合遷移問題を解く

Algorithm 1 提案アルゴリズムの疑似コード
Input P : problem instance of ASP fact format
Input S(x0 ), C(xt ), T (xt−1 , xt ), G(xt ), O(t): logic program
Parameter I max : the maximum number of steps [none]
1: ctl ← create an object of ASP solver
2: i ← 0
3: ret ← none
4: model ← none
5: model∗ ← an empty list
6: cost ← cost∗ ← none
7: wmin ← none
8: add a statement “#external query(t).” to G(xt )9: while (I max = none or i ≤ I max ) do
10:parts ← an empty list
11:
parts.append(C(xi ))12:parts.append(G(xi ))13:parts.append(O(i))
14:
if i > 0 then15:parts.append(T (xi−1 , xi ))16:
ctl.release external(query(i − 1)) {deactivating G(xi−1 )}
17:
else
18:
parts.append(P )19:parts.append(S(x0 ))20:
end if21:
ctl.ground(parts)
22:
if i = 0 then23:
wmin ← get minimum weight(O(i))
24:
end if25:
ctl.assign external(query(i), true) {activating G(xi )}26:(ret, model) = ctl.solve()
27:
i←i+1
28:
if ret ̸= SAT then29:
continue30:
end if31:
cost ← model.cost[0]32:
if cost∗ = none or cost < cost∗ then33:
cost∗ ← cost
34:
model∗ .append(model)
35:
if I max = none or I max > ⌊cost/wmin ⌋ then36:
I max ← ⌊cost/wmin ⌋37:
end if38:
end if
39: end while
40: ctl.close()
41: return model∗

TJ 符号化 (リスト 2) と TS 符号化 (リスト 3) とのいる．10 行目のルールは TJ 遷移制約を表し，TJ 符

違いは，複数の重み付き遷移制約 (8–12 行目) と遷移

号化 (リスト 2) の 9 行目に対応している．11–12 行

コストを最小化するための目的関数 (14 行目) である．

目のルールは TS 遷移制約を表し，TS 符号化 (リス

8 行目のルールは，各ステップ t に対して，遷移制約

ト 3) の 9–10 行目に対応している．tj(t) と ts(t)TJ と遷移制約 TS が適用されたことを意味する補助はどちらか必ず真になるので，10 行目と 11 行目は 2

アトム tj(t) と ts(t) をそれぞれ導入し，個数制約

つまとめて，:- not 1 token_removed(X,t) 1. とを用いていずれか一つが適用されることを強制して書いてもよい．14 行目のルールは，#minimize 文を

スタート
1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

TJ

→

1

2

3

4

5

6

7

8

9

10

11

12

TS

X0

→

1

2

3

4

5

6

7

8

9

10

11

12

TS

X1

→

X2
ゴール

X3
↓ TS

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

TS

←

X5
図4

X4

多目的独立集合遷移最適化問題の例

中に出現する tj_weight と ts_weight は，それぞれ合せ遷移競技会 CoRe Challenge 2022 で使用された
独立集合遷移の問題インスタンス (全 369 問) †1 を用

TJ と TS の重みを表す定数である．

いた．ただし，競技会において，TJ 型独立集合遷移

用いて，遷移コストを最小化している．この文の括弧での到達不能性が証明されたインスタンス 43 問は除1 #program base.

外した．その理由は，TJ 遷移制約において到達不能

2 :- not in(X,0), start(X).

であるとき，TS 遷移制約においても到達不能である

3

ため，TJ と TS を考慮した独立集合遷移最適化にお4 #program step(t).
5 K { in(X,t): node(X) } K :- k(K).
6 :- in(X,t), in(Y,t), edge(X,Y).
7

いても到達不能となるためである．
多目的独立集合遷移最適化問題を解く ASP 符号化

8 1 { tj(t) ; ts(t) } 1 :- t>0.

には，TJ–TS 符号化 (リスト 4) を用い，TJ と TS

9 token_removed(X,t) :- in(X,t-1), not in(X,t), t>0.

の重み (tj_weight と ts_weight) は，それぞれ 5 と

10 :- tj(t), not 1 { token_removed(X,t) } 1.

2 とした．多目的独立集合遷移最適化問題を解くソ

11 :- ts(t), not 1 { token_removed(X,t) } 1.
12 :- ts(t), not 1 { in(Y,t) : edge(X,Y) ; in(Y,t) : edge(Y,X) } 1,
token_removed(X,t).
13
14 #minimize { tj_weight,t : tj(t) ; ts_weight,t : ts(t) }.

ルバーには，提案アルゴリズム (アルゴリズム 1) を実装した ASP に基づく組合せ遷移最適化ソルバー

recongo opt を使用した．recongo opt ソルバーのバッ

15

クエンドには，ASP システム clingo バージョン 5.5.2

16 #program check(t).

を使用した．1 問あたりの制限時間は 30 分とした．

17 :- not in(X,t), goal(X), query(t).

実験環境は Mac mini, 3.2GHz 6 コア Intel Core i7,
リスト 4

多目的独立集合遷移最適化問題の ASP 符号化(TJ–TS 符号化)

64GB メモリである．
解けた問題数を表 1 に示す．左から問題ファミリ
名，問題ファミリに含まれる問題数，パレート最適な遷移系列が全列挙できた問題数 (#PF Found)，パレート最適な遷移系列が一つも得られなかった問題

7 実行実験

数 (#Unsolved) を表す．#PF Found はパレートフ

提案解法の有効性を評価するために実験を行った．

ロントを得られた問題数を意味する．

ベンチマークには多目的独立集合遷移最適化問題 (第6 節) を使用した．ベンチマーク問題集には，国際組提案手法は 326 問中 212 問 (全体の約 65%) に対†1 https://github.com/core-challenge/2022benchmark

表1

解けた問題数問題ファミリ 問題数 #PF Found #Unsolved

8 関連研究

202

187

15

組合せ遷移. 組合せ遷移の実践的研究は，ここ数

grid

7

2

5

年で活発に行われている．2022–2023 年に 2 年連続

handcraft5

50

で開催された国際組合せ遷移競技会 CoRe Challenge

power

17

0

17

2022–2023 [26] では，独立集合遷移問題を解くソル

queen

48

15

27

バーの性能が競われた．この CoRe Challenge 競技

sp

30

3

27

会を契機として，組合せ遷移問題の汎用ソルバーがいsquare17

017

くつか開発されている．recongo [33] は ASP に基づ

Total

326

212

108

く汎用ソルバーであり，CoRe Challenge 競技会におcolor04

いて，逐次ソルバーの複数部門で優勝するなど優れた
して，パレートフロントを得ることができた．問題

性能を示している．他にも，並列ソルバーの複数部門

ファミリごとに見ると，最短遷移長が短い問題の多で優勝したプランニングに基づくソルバー PARIS [6]い color04 に属する問題を 202 問中 187 問解き，よや，ゼロサプレス型二分決定グラフ (ZDD) に基づくい性能を示している．その一方で，最短経路長が数ソルバー ddreconf [18] などがある．しかし，これら百を超える問題を多く含む power, sp, square では，のソルバーでは多目的組合せ遷移最適化問題を解くこ

ほとんどの問題を解けなかった．クイーングラフ上のとはできない．本稿で開発した recongo opt ソルバー

問題から構成される queen(計 48 問) では，パレート

は，第 5 節の提案アルゴリズムをもとに，recongo を

フロントを得られた問題が 15 問，パレート最適な遷

多目的組合せ遷移最適化問題に拡張したものである．

移系列が一つも得られなかった問題が 27 問で，残り他のソルバーも多目的組合せ遷移最適化に拡張する

6 問については，パレート最適な遷移系列を部分的にことは可能であると思われるが，そのためのアルゴリ

列挙することができた．

ズムの改良・拡張は自明ではない．

パレート最適な遷移系列を全列挙するのに要した個々の組合せ遷移問題の解法についても研究が進んCPU 時間を表 2 に示す．CPU 時間が 10 秒未満のイでいる．組合せ遷移に対して ASP が初めて使われた

ンスタンスは省略している．最も時間を要したのは，のは，TJ 型独立集合遷移問題の ASP 符号化に関す頂点数が 400 で辺の数が 12540 のクイーングラフに基る研究である [32] [33]．文献 [15] はハミルトン閉路遷

づくインスタンス queen020x020_04_0961 で，CPU移問題を解く ASP 符号化を提案している．この研究

時間は約 1,630 秒であった．パレートフロントが得ら

では，遷移制約として，1 回の遷移でハミルトン閉路れた問題のうち，パレート最適な遷移系列が最も多かっ

上のちょうど k 本の辺が変化する k-opt [29] が使用た問題は queen16_16_02 と queen060x060_03_1394

されている．ASP を用いた支配集合遷移問題の解法

で，その数は 4 であった．

は，文献 [21] で研究されている．この研究では，遷今回の実験で使用した多目的独立集合遷移最適化

移制約として，TJ や TS の他に，1 回の遷移でちょ問題は TJ と TS のトレードオフを考慮した多様なうど 1 個のトークンが追加あるいは削除される TAR解が得られるという長所がある．その一方で，遷移制を用いた到達可能性判定問題の ASP 符号化を提案し約の数が 2 つと少なく，さらに TS が TJ の特殊形ている．本稿の結果から，これらの代表的な組合せ遷であるため，パレートフロントを構成する最適遷移系

移問題を多目的組合せ遷移最適化へ拡張することは列の数が少ない結果となった．より多くの遷移制約を興味深い．特に，ハミルトン閉路遷移問題の k-opt 遷

含む多目的独立集合遷移最適化問題を用いた性能評

移制約は，巡回セールスマン問題に対する近似解法で価は今後の重要な研究課題である．

よく使われるヒューリスティックスであり，k-opt を使ったハミルトン閉路の多目的遷移最適化は今後の研表2

インスタンス

パレートフロントを求めるのに要した CPU 時間

CPU 時間 (秒)インスタンスCPU 時間 (秒)hc-power-12_01

88.451queen020x020_04_0961

queen040x040_03_7037

417.181queen050x050_03_0562

47.341queen050x050_04_9047

142.805queen060x060_01_8336

136.225

queen060x060_02_6710

150.821queen060x060_03_1394

235.842queen060x060_04_3799

277.343

3-FullIns_5_02

26.9934-FullIns_5_01

31.0454-FullIns_5_02

30.962

DSJC1000.5_01

18.403

DSJC500.9_02

14.184

DSJR500.1_02

30.773le450_25a_02

66.956le450_25b_02

47.521

mug100_25_02

522.049

mug88_1_02

70.956

qg.order30_02

21.79

qg.order60_01

616.283queen13_13_01

15.809school1_02

11.875sp003_01

121.477

wap01a_01

95.606wap02a_01

117.579

wap03a_01

199.054wap04a_01

491.538

wap05a_01

11.537wap06a_01

13.262

wap07a_01

25.297wap08a_01

38.899

究課題の一つである．

1630.182

長を 1 からインクリメンタルに増やしながら繰り返

自動プランニング [27] は，スター

すことで，最短プラン長における最小コストプランをト状態からゴール状態への状態遷移系列に関する研求める．また，文献 [7] は，アクションコストを加味究という点から，組合せ遷移と関連が深い研究分野

した宣言的プランニング言語を新たに提案し，それをである．例えば，最小コストプランニングは，状態をASP に変換した後にプランを探索する手法を提案し表す命題の集合，スタート状態，ゴール条件，コストている．この手法は，最短プラン長における最小コス付きアクションの集合が与えられたとき，スタート

トプランの他に，最小コストにおける最短プランを求状態からゴール条件を満たす状態に遷移するまでのめることができる．いずれの手法もパレート最適なプアクション系列のうち，最小コストのものを求める

ランを一つ見つけることはできるが，パレートフロン問題である．最小コストプランニングは，2008 年かトを求めることはできない．本稿の提案解法は，遷移ら国際プランニング競技会 (International Planning

長の上限値を自動で適切に更新することによって，パCompetition; IPC) の題材として使用され，実践的

レート最適な遷移系列の全列挙を保証できる点が特なプランナーの開発が活発に行われている．

長であり，プランニング分野への応用も期待できる．

プランニング.

最小コストプランニングは，アクション系列のコストを最小化することが目的であるため，プラン長

9 おわりに(すなわち，遷移長) は基本的に考慮しない．プラン

本稿では，遷移コストと遷移長を考慮したパレート

長とコストを考慮したプランニングの研究としては最適な組合せ遷移を提案し，解集合プログラミングを

文献 [22] がある．この研究では，制限されたプラン用いた解法アプローチについて述べた．

長での最小コストプランを求める問題を SAT に翻訳

今後の課題としては，多目的組合せ遷移最適化問題

し，CDCL ベースの分枝限定法を用いたアルゴリズにおける解空間グラフの構造や性質に関する理論研究

ムによって解く手法を提案している．つまり，プランが挙げられる．本稿の提案手法の応用研究としては，

グラフ彩色遷移，L(h, k) ラベリング遷移，ハミルト
ン閉路遷移の多目的組合せ遷移最適化への拡張を考えている．頂点間の距離を考慮した d-Jump 遷移制
約 [14] に基づく多目的独立集合遷移最適化の研究も重要な研究課題の一つである．

参 考 文 献[ 1 ] Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge
University Press, 2003.
[ 2 ] Bonamy, M., Dorbec, P., and Ouvrard, P.:
Dominating sets reconﬁguration under token sliding, Discrete Applied Mathematics, Vol. 301(2021),
pp. 6–18.
[ 3 ] Bonsma, P. S. and Cereceda, L.: Finding Paths
between graph colourings: PSPACE-completenessand superpolynomial distances, Theoretical Computer Science, Vol. 410, No. 50(2009), pp. 5215–
5226.
[ 4 ] Brewster, R. C., McGuinness, S., Moore, B. R.,
and Noel, J. A.: A dichotomy theorem for circular colouring reconﬁguration, Theoretical Computer
Science, Vol. 639(2016), pp. 1–13.
[ 5 ] Cereceda, L., van den Heuvel, J., and Johnson,
M.: Finding paths between 3-colorings, Journal ofGraph Theory, Vol. 67, No. 1(2011), pp. 69–82.
[ 6 ] Christen, R., Eriksson, S., Katz, M., Muise, C.,
Petrov, A., Pommerening, F., Seipp, J., Sievers, S.,
and Speck, D.: PARIS: Planning Algorithms for
Reconﬁguring Independent Sets, Proceedings of the
26th European Conference on Artiﬁcial Intelligence(ECAI 2023), Gal, K., Nowé, A., Nalepa, G. J.,
Fairstein, R., and Radulescu, R.(eds.), Frontiers in
Artiﬁcial Intelligence and Applications, Vol. 372,
IOS Press, 2023, pp. 453–460.
[ 7 ] Eiter, T., Faber, W., Leone, N., Pfeifer, G., andPolleres, A.: Answer Set Planning Under Action
Costs, Journal of Artiﬁcial Intelligence Research,
Vol. 19(2003), pp. 25–71.
[ 8 ] Gebser, M., Kaminski, R., Kaufmann, B., andSchaub, T.: Answer Set Solving in Practice, Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning, Morgan and Claypool Publishers,
2012.
[ 9 ] Gebser, M., Kaminski, R., Kaufmann, B., andSchaub, T.: Multi-shot ASP solving with clingo,
Theory and Practice of Logic Programming, Vol. 19,
No. 1(2019), pp. 27–82.
[10] Gelfond, M. and Lifschitz, V.: The Stable Model
Semantics for Logic Programming, Proceedings ofthe Fifth International Conference and Symposiumon Logic Programming, MIT Press, 1988, pp. 1070–
1080.
[11] Gopalan, P., Kolaitis, P. G., Maneva, E. N., andPapadimitriou, C. H.: The Connectivity of Boolean

Satisﬁability: Computational and Structural Dichotomies, SIAM Journal on Computing, Vol. 38,
No. 6(2009), pp. 2330–2355.
[12] Haas, R. and Seyﬀarth, K.: The k-Dominating
Graph, Graphs and Combinatorics, Vol. 30,
No. 3(2014), pp. 609–617.
[13] Haddadan, A., Ito, T., Mouawad, A. E.,
Nishimura, N., Ono, H., Suzuki, A., and Tebbal,
Y.: The complexity of dominating set reconﬁguration, Theoretical Computer Science, Vol. 651(2016),
pp. 37–49.
[14] Hatano, H., Kitamura, N., Izumi, T., Ito,T., and Masuzawa, T.: Independent Set Reconﬁguration Under Bounded-Hop Token, CoRR,
Vol. abs/2407.11768(2024).
[15] Hirate, T., Banbara, M., Inoue, K., Lu, X.,
Nabeshima, H., Schaub, T., Soh, T., and Tamura,N.: Hamiltonian Cycle Reconﬁguration with Answer Set Programming, Proceedings of the 18th Edition of the European Conference on Logics in Artiﬁcial Intelligence (JELIA 2023), Gaggl, S. A., Martinez, M. V., and Ortiz, M.(eds.), LNCS, Vol. 14281,
Springer, 2023, pp. 262–277.
[16] 井上克巳, 坂間千秋: 論理プログラミングから解集合
プログラミングへ, コンピュータソフトウェア, Vol. 25,
No. 3(2008), pp. 20–32.
[17] Ito, T., Demaine, E. D., Harvey, N. J. A., Papadimitriou, C. H., Sideri, M., Uehara, R., and Uno,Y.: On the complexity of reconﬁguration problems,
Theoretical Computer Science, Vol. 412, No. 1214(2011), pp. 1054–1065.
[18] Ito, T., Kawahara, J., Nakahata, Y., Soh, T.,
Suzuki, A., Teruyama, J., and Toda, T.: ZDDBased Algorithmic Framework for Solving Shortest Reconﬁguration Problems, Proceedings of the20th International Conference on the Integrationof Constraint Programming, Artiﬁcial Intelligence,and Operations Research (CPAIOR 2023), Ciré,
A. A.(ed.), LNCS, Vol. 13884, Springer, 2023,
pp. 167–183.
[19] Ito, T., Ono, H., and Otachi, Y.: Reconﬁguration of Cliques in a Graph, Proceedings of the 12th
Annual Conference on Theory and Applications ofModels of Computation (TAMC 2015), Jain, R.,
Jain, S., and Stephan, F.(eds.), LNCS, Vol. 9076,
Springer, 2015, pp. 212–223.
[20] Kaminski, M., Medvedev, P., and Milanic,
M.: Complexity of independent set reconﬁgurability problems, Theoretical Computer Science,Vol. 439(2012), pp. 9–15.
[21] Kato, M., Schaub, T., Soh, T., Tamura, N., andBanbara, M.: Dominating Set Reconﬁguration with
Answer Set Programming, ICLP 2024, to appear.
[22] Lu, Q., Huang, R., Chen, Y., Xu, Y., Zhang,W., and Chen, G.: A SAT-based approach tocost-sensitive temporally expressive planning, ACM
Transactions on Intelligent Systems and Technology, Vol. 5, No. 1(2013), pp. 18:1–18:35.

[23] Mouawad, A. E., Nishimura, N., Pathak, V., andRaman, V.: Shortest Reconﬁguration Paths in the
Solution Space of Boolean Formulas, SIAM Journal on Discrete Mathematics, Vol. 31, No. 3(2017),
pp. 2185–2200.
[24] Niemelä, I.:
Logic Programs with Stable
Model Semantics as a Constraint Programming
Paradigm, Ann. Mathematics and Artiﬁcial Intelligence, Vol. 25, No. 3–4(1999), pp. 241–273.
[25] Nishimura, N.: Introduction to Reconﬁguration,
Algorithms, Vol. 11, No. 4(2018), pp. 52.
[26] Soh, T., Tanjo, T., Okamoto, Y., and Ito, T.:
CoRe Challenge 2022/2023: Empirical Evaluations
for Independent Set Reconﬁguration Problems (Extended Abstract), Proceedings of the SeventeenthInternational Symposium on Combinatorial Search(SOCS 2024), Felner, A. and Li, J.(eds.), AAAI
Press, 2024, pp. 285–286.
[27] Son, T. C., Pontelli, E., Balduccini, M., andSchaub, T.: Answer Set Planning: A Survey, Theory and Practice of Logic Programming, Vol. 23,
No. 1(2023), pp. 226–298.
[28] Suzuki, A., Mouawad, A. E., and Nishimura,N.: Reconﬁguration of dominating sets, Journal of
Combinatorial Optimization, Vol. 32, No. 4(2016),
pp. 1182–1195.
[29] Takaoka, A.: Complexity of Hamiltonian Cycle
Reconﬁguration, Algorithms, Vol. 11, No. 9(2018),
pp. 140.

[30] Toda, T., TakehiroIto, Kawahara, J., Soh, T.,
Suzuki, A., and Teruyama, J.: Solving Reconﬁguration Problems of First-Order Expressible Propertiesof Graph Vertices with Boolean Satisﬁability, Proceedings of the IEEE 35th International Conferenceon Tools with Artiﬁcial Intelligence (ICTAI 2023),
2023, pp. 294–302.
[31] van den Heuvel, J.: The complexity of change,
Surveys in Combinatorics 2013, Blackburn, S. R.,
Gerke, S., and Wildon, M.(eds.), London Mathematical Society Lecture Note Series, Vol. 409, Cambridge University Press, 2013, pp. 127–160.
[32] Yamada, Y., Banbara, M., Inoue, K., andSchaub, T.: Recongo: Bounded Combinatorial Reconﬁguration with Answer Set Programming, Proceedings of the 18th Edition of the European Conference on Logics in Artiﬁcial Intelligence (JELIA
2023), Gaggl, S. A., Martinez, M. V., and Ortiz, M.(eds.), LNCS, Vol. 14281, Springer, 2023,
pp. 278–286.
[33] Yamada, Y., Banbara, M., Inoue, K., Schaub,T., and Uehara, R.: Combinatorial Reconﬁguration with Answer Set Programming: Algorithms,
Encodings, and Empirical Analysis, Proceedings ofthe 18th International Conference and Workshops
on Algorithms and Computation (WALCOM 2024),
Uehara, R., Yamanaka, K., and Yen, H.(eds.),
Lecture Notes in Computer Science, Vol. 14549,
Springer, 2024, pp. 242–256.