小特集 11. 組合せ遷移への招待

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 11.

組合せ遷移への招待

Invitation to Combinatorial Reconfiguration

伊藤健洋

伊藤健洋 正員 東北大学大学院情報科学研究科システム情報科学専攻

Takehiro ITO, Member (Graduate School of Information Sciences, Tohoku University, Sendai-shi, 980-8579 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.288-292 2018年3月

©電子情報通信学会2018

abstract

 組合せ遷移とは,パズルや持続的システムといった動的な状況を定式化することに適し,最近10年ほどで急速に研究が発展・深化した研究トピックである.実行可能解が一つでも存在するか判定する従来の問題に比べ,組合せ遷移では実行可能解が形成する解空間での到達可能性が問われる.本稿ではまず,組合せ遷移の枠組みと研究背景を紹介する.次に,最近の研究動向を解説するとともに,組合せ遷移におけるアルゴリズム開発を紹介する.

キーワード:組合せ遷移,PSPACE完全,グラフ彩色,パズル

1.は じ め に

 15パズル,箱入り娘,ラッシュアワー等のパズルで遊んだことがある方も多いであろう.これらなじみの深いパズルにも関連する「組合せ遷移」と呼ばれるトピックが,近年盛んに研究されている.

 組合せ遷移の枠組みは,動的な状況を定式化することに適する.大まかには,「初期状態」からスタートし,「許された変更操作」を繰り返しながら,「目標状態」に遷移させたい,という枠組みである.(15パズルの例を図1に示す.)詳細は後述するが,ここでいう「状態」とは「実行可能解(制約条件を満たす解)」を意味しており,遷移の過程で現れる状態もまた,実行可能解でなければならない.従来研究されてきた探索問題の多くでは,実行可能解が一つでも存在するかが問われた.それに比べ,組合せ遷移では,実行可能解が形成する解空間における連結性や到達可能性が問われる.

fig_1.png

 組合せ遷移は,様々な分野で研究がなされてきた.理論計算機科学の分野,特にグラフに関連する問題については,最近10年ほどで急速に研究が発展・深化し,その理論体系化が進んでいる.本稿ではまず,組合せ遷移の枠組みと研究背景を紹介する.次に,最近の研究動向を解説するとともに,組合せ遷移におけるアルゴリズム開発の難しさ(筆者としては,面白さ)をお伝えしたい.

2.組合せ遷移の枠組み

 前章で大まかに述べたように,組合せ遷移の具体的な問題は,「実行可能解」と「許される変更操作」の二つを指定することで定義される.本章では,例を挙げながら,組合せ遷移の枠組みを導入する.

 なお,理論計算機科学分野におけるトピック名を「組合せ遷移」といい,その具体的な問題を「遷移問題」と呼ぶ.また,混乱を避けるために,実行可能解が一つでも存在するかどうか判定する問題を「従来型の探索問題」と呼ぶことがある.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。