|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
コンピュテーション研究専門委員会
組合せ遷移
組合せ遷移とは，「状態空間上での遷（うつ）り変わり」を数理モデル化し，アルゴリズム理論の観点から解析する研究である．組合せ遷移の研究の枠組み(1)が2008年に提唱されて以来，その研究は世界的に広がり，今ではアルゴリズム理論の新しい研究潮流となっている．特に，R.M. Karpの21問題（1972年）をはじめとした理論計算機科学の最も基礎的な問題を中心に，組合せ遷移の理論研究が進められている(2), (3)．また，研究が進むにつれ，組合せ遷移の概念が理論から産業まで多種多様な分野に現れることも分かってきた．近年では，数学の諸分野に現れる研究を組合せ遷移の視点から捉えたり，組合せ遷移の問題を解く汎用ソルバーの開発や産業応用に向けた工学的アプローチの研究に取り組んだりと，アルゴリズム理論の範ちゅうに収まりきらない研究事例も多数発表されている(4)．
ここでは，配電制御システムを例に，組合せ遷移の概念を導入する．配電網は冗長性を持つように設計されており，変電所から負荷区間への電気の送り方（供給経路）は複数ある．その中から供給経路を一つに決める際には，配電ロスの最小化等，様々な最適化指標が用いられる．例えば，配電網の標準解析モデルには，約1058通りという膨大な供給経路の選択肢が存在する．このような膨大な選択肢がある中から，最適な供給経路を算出するだけでも非常に難しい問題である．
しかし，たとえ最適な供給経路が算出できても，常時稼動型システム特有の課題も生じる．既にシステムは稼動して電力供給を行っており，たとえ最適な状態へ切り替えるためとはいえ，その切替途中で停電を起こすわけにはいかないのである．現在の供給経路から最適なものへと一気に切り替えられればいいのだが，電気的な制約から切替操作にも規則がある．したがって，現在の供給経路から最適な状態へと切り替える操作手順を計算する必要がある（図1）．これは，約1058通りの供給経路からなる状態空間において，現在の供給経路から最適なものへと辿り着くための経路（切替手順）を求めることに相当する．このように「状態空間上での遷り変わり」を対象とするアルゴリズム研究が「組合せ遷移」である．
組合せ遷移の研究では，対象とする状態空間をまず定める．組合せ遷移の文脈では，状態空間を「解空間グラフ」と呼ぶこともある．解空間グラフは，頂点の集合と二つの頂点を結ぶ辺の集合から定義されるグラフである．対象となる各状態が解空間グラフの頂点に対応し，一度の変更操作で遷り合える2頂点（状態）が辺で結ばれる．前述の配電制御システムの例であれば，供給経路一つ一つが解空間グラフの頂点に対応し，一度の切替操作で遷り合える供給経路が解空間グラフの辺で結ばれる．このような解空間グラフにおいて，到達可能性や連結性を問うのが，組合せ遷移の研究である．
配電網では，各開閉器を「開」または「閉」とする選択肢があり，それを全ての開閉器において定めることで，全体の供給経路が一つ決まる．したがって，供給経路の候補数は，開閉器の個数に対して，指数的に大きくなる．この例のように，解空間グラフの頂点（状態）数は，入力サイズに対して指数的に大きくなり得る．これは，解空間グラフを明示的に構築していては，組合せ遷移の問題を解く高速なアルゴリズムは開発できそうにないことを示している．
アルゴリズム理論分野では，より根本的な理論研究として，理論計算機科学の最も基礎的な問題を対象とした組合せ遷移の研究が進められている．例えば，命題論理式の充足可能性（SAT），グラフの独立集合，彩色，マッチング等が挙げられる．これらの組合せ遷移問題に対して，計算困難性と容易性の両面から研究が進められている．
ここでは，グラフの独立集合を具体例に挙げる．グラフ
において，互いに隣接しない頂点の部分集合
は，グラフ
の独立集合と呼ばれる．例えば，図2（a）から（f）には，同じグラフの6種類の独立集合が示されている．ここで，独立集合に含まれる頂点は，緑色の丸で描かれている．便宜上，独立集合に含まれる頂点の上に，緑色のトークン（コイン）が配置されているとみなそう．トークンジャンピング問題(5)では，グラフ
の二つの独立集合
と
が与えられたとき，毎回1枚だけトークンを移動することで，初期配置
から目標配置
へと独立集合を遷移させられるか判定したい．ただし，遷移の途中でも，独立集合であることは保持しなければならない．実際，図2はそのような独立集合の遷移系列を示している．
組合せ遷移の研究の枠組みが提唱されてからしばらくは，主に計算困難性の解析が中心であった．有名なP≠NP予想は，NP完全な問題に対しては高速な（多項式時間の）アルゴリズムの開発ができないという予想である．これに対して，組合せ遷移問題の多くは，PSPACE完全であることが証明されている(1),(2)．例えば，前述のトークンジャンピング問題もPSPACE完全である(5)．ここでは計算量クラスPSPACEの定義などは省略するが，PSPACEは計算量クラスNPを包含する．そのため，PSPACE≠NPの仮定の下では，PSPACE完全問題は，NP完全問題よりもアルゴリズム開発が難しいと言える．
最近では，計算困難性に関する研究が大きく深化し，組合せ遷移問題は近似的に解くことでさえPSPACE困難であるという研究(6)も発表された．
計算容易性の観点，すなわち，組合せ遷移問題を効率良く解くためのアルゴリズム手法の開発は，2013年頃から急速に発展してきた．組合せ遷移問題の多くは，PSPACE完全であった．実際，NP完全問題に対する既存のアルゴリズム手法は，組合せ遷移問題には適用できないことが多い．
そのような状況でも，組合せ遷移問題に対する様々なアルゴリズム手法が新しく開発されている．特に，固定パラメータ容易性の手法を用いたアルゴリズムは，盛んに研究が進められている．この手法では，パラメータに依存する範囲であれば，解空間グラフを（部分的に）構築できることが利点である．更には，個々の組合せ遷移問題に対するアルゴリズムの研究開発だけでなく，様々な組合せ遷移問題に適用可能なメタ定理(7),(8)も発表される等，研究は進んでいる．
組合せ最適化の分野では，SATソルバーや整数計画ソルバーの開発が長年進められ，アルゴリズムの非専門家であっても，様々な実用規模の問題を解くことができている．すなわち，これら汎用ソルバーを通して，利用者が意識せずとも，アルゴリズムの最先端技術が研究や産業の現場で利活用されている．ここでは，組合せ遷移の展開事例として，汎用ソルバーの開発と配電制御へのアプローチを紹介する．
組合せ遷移問題を解くソルバーは，組合せ遷移の国際プログラミング競技会Combinatorial Reconfiguration Challenge（CoRe Challenge）を契機として，複数の異なる手法に基づき研究開発が始まった．CoRe Challengeは2022年と2023年に2年連続で開催され(9)，いずれもトークンジャンピング問題が対象となった．プログラミング競技会では，AIプランニング，解集合プログラミング，有界モデル検査，ゼロサプレス型二分決定グラフ（ZDD : Zero-suppressed binary Decision Diagram）といった様々な手法を活用したソルバーが提案されている．
CoRe Challengeでは，競技会で用いたベンチマークデータ693問，投稿されたプログラム，競技会の結果を全てWeb公開している．これにより，今後新たなソルバーを開発した際には，開発者自身で性能評価を行える．その意味で，組合せ遷移ソルバーの各種手法を性能比較する土台が整えられたと言える．実際，前述のソルバー開発者らも，競技会後に詳細な性能解析に取り組み，複数の論文が発表されている．（論文情報は，文献（9）を参照されたい．）
もともと組合せ遷移の概念は，配電制御システムにおける供給経路の切替手順を発端として生まれた．そのため，組合せ遷移のアルゴリズム手法を配電制御に現れる諸課題の解析に活用した事例は，既に幾つか知られている．
一例として，停電復旧の最短手順を求めるアルゴリズム(10)が挙げられる．このアルゴリズムは，停電が発生していない健全な需要区間も制御対象とすることで，より大規模な停電の復旧にも対応できる．もちろん，健全な需要区間に新たな停電を発生させてはならないため，組合せ遷移ならではの視点によるアルゴリズム開発と言える．このアルゴリズムは，前述のZDDを用いた組合せ遷移ソルバーを基に開発されている．このアルゴリズムを実社会で活用するには，まだ多くのハードルがあるが，社会的説明責任を伴う停電復旧のプロセスに数理的エビデンスを与えることに今後つながると期待される．
(１) T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, “On the complexity of reconfiguration problems,” Theoretical Computer Science, vol.412, pp.1054-1065, 2011.
(２) N. Nishimura, “Introduction to reconfiguration,” Algorithms, vol.11, paper id 52, 2018.
(３) D.A. Hoang, Combinatorial Reconfiguration.
https://reconf.wikidot.com/ （2024年10月23日閲覧）
(４) 学術変革領域研究（B）「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」．
https://core.dais.is.tohoku.ac.jp/ （2024年10月23日閲覧）
(５) M. Kamiński, P. Medvedev, and M. Milanič, “Complexity of independent set reconfigurability problems,” Theoretical Computer Science, vol.439, pp.9-15, 2012.
(６) S. Hirahara and N. Ohsaka, “Probabilistically checkable reconfiguration proofs and inapproximability of reconfiguration problems,” Proc. the 56th Annual ACM Symposium on Theory of Computing （STOC 2024）, pp.1435-1445, 2024.
(７) A.E. Mouawad, N. Nishimura, V. Raman, and M. Wrochna, “Reconfiguration over tree decompositions,” Proc. the 9th International Symposium on Parameterized and Exact Computation （IPEC 2014）, Lecture Notes in Computer Science, vol.8894, pp.246-257, 2014.
(８) T. Gima, T. Ito, Y. Kobayashi, and Y. Otachi, “Algorithmic meta-theorems for combinatorial reconfiguration revisited,” Algorithmica, vol.86, pp.3395-3424, 2024.
(９) T. Soh, T. Tanjo, Y. Okamoto, and T. Ito, “CoRe Challenge 2022/2023 : Empirical evaluations for independent set reconfiguration problems （extended abstract）,” Proc. the 17th International Symposium on Combinatorial Search （SoCS 2024）, vol.17, pp.285-286, 2024.
(10) 川原 純，山岡宙太，伊藤健洋，鈴木 顕，飯岡大輔，杉村修平，後藤誠弥，田邊隆之，“停電復旧の最短手順を算出するアルゴリズム，”令和5年電学全大，6-129, 2023．
（2024年10月23日受付 2025年2月3日最終受付）
オープンアクセス以外の記事を読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
