組合せ爆発

提供: miniwiki
2018/8/19/ (日) 17:27時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

組合せ爆発(くみあわせばくはつ、: Combinatorial explosion)は、計算機科学応用数学情報工学人工知能などの分野では、組合せ(combination)的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数階乗などのオーダーで急激に大きくなってしまうために、有限時間であるいは最適解を発見することが困難になることをいう。

概説

それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。

組合せ的爆発(くみあわせてきばくはつ)、組合せ論的爆発(くみあわせろんてきばくはつ)ともいう。計算量の爆発(けいさんりょうのばくはつ)の方がより一般概念であり、それには指数的爆発(しすうてきばくはつ)も含まれる。こういった場合の組み合わせの数のような数を巨大数とも言う。

n多項式オーダーで解ける場合は一般に、組合せ爆発とは言わない。組合せ爆発の変わった例として、再帰的参照を含み急激に巨大化するアッカーマン関数がある。

組合せ爆発を起こす関数をコンピュータで計算しようとすると、入力長に対して急激に出力長が大きくなったり、計算に時間がかかるようになる。そのためアルゴリズムには、組合せ爆発を防ぐ工夫をしたものがある。一方、多項式時間では解けないと証明された問題のクラスもある。

情報システム開発では、上記のような解空間巨大化による計算量増大現象とは言い方が異なるが、組合せ爆発が言われる。情報システムの構成要素やその状態が増えると、その組合せで作られるシステムの複雑性は爆発的に膨張するので、この問題への対応と解決は情報処理の重要な課題である。

日常的には、曽呂利新左衛門が「きょうは1粒、あしたは2粒…」の米を所望した話や、彦一が「将棋盤の1マス目に1粒、次のマス目には2粒」の米を所望した話のように、倍々に増える数の急激さのことなども、組合せ爆発と表現されていることがある。倍々ゲームは指数関数ではあるが、組合せとはいえない。

通信ネットワークにおける組合せ爆発

ファイル:4x2.svg
1対1の通信路を使うと、4ノードで6つの通信路を必要とする。
ファイル:4xn.svg
何らかの媒介手段があれば、各ノードからは1つの通信路で済む。

コンピュータネットワークにおいて、ノードを追加していくと必要な通信路が急激に増大する。このことを組合せ爆発と称する。ただし、実際には指数関数的に増えるEnglish版わけではなく、厳密にはせいぜい多項式的増大である。

2つのノード間で通信する必要があるとき、1対1の適当な通信路1本で直接接続すればよい。しかし、3つめのノードを追加すると、通信路が3本必要となる。4ノードでは6本、5ノードでは10本、6ノードでは15本と増えていく。これを一般化すると、n ノードでの通信路数l は次のように、n の2乗のオーダーで増加する。

[math]l=\frac{n(n-1)}{2}[/math]

これを減らすためのひとつの方法は、情報を媒介する汎用的手段を中心に置くことであり、この場合通信路の数はノード数n に等しくて済む。しかしこの場合の欠点は、

  1. 1対1では電話やテレタイプのように特に手順らしい手順を定めなくとも通信できるかもしれないが、媒介手段に対応するためには通信内容に付加された宛先に基づく経路制御をする必要があるのでTCP/IPSMTPなど何らかの通信プロトコルを導入する必要が生じる点
  2. 中心の媒介手段が障害や性能不足に陥れば全部の通信が影響を受ける点

である。2. の欠点のために、実際の設計では必ずしも通信路の数を減らしさえすればいいわけではなく、ある程度の冗長性を残した複雑なシステムを構築することが多い。

計算機科学における計算量の爆発

計算機科学において、計算複雑性理論は重要な研究テーマである。たとえ解が存在して計算方法があっても、現実的なCPU数やメモリ容量の計算資源を使って、入力問題のサイズの多項式関数で表せるほどの短時間には解けないほど複雑な計算問題が存在する。複雑性クラスにはさまざまあるが、多項式関数の時間で解けない場合は計算量が爆発すると言われる。計算問題が組合せを内包している場合に組合せ爆発または組合せ的爆発といい、また指数関数のサイズになる場合に指数的爆発exponential explosion)という。

素因数分解問題の例

素因数分解問題の計算量は指数時間であって、多項式時間では解けないと予想されている。このおかげで現在広く使われている公開鍵暗号RSA暗号が、パソコンやスーパーコンピュータでは数日、数カ月といった現実的な時間では到底解けないと期待されている。ところが、量子コンピュータを用いれば素因数分解問題は多項式時間で解けてしまうことが発見された(Shor[1]、1994年)。

この例のように、新しい計算モデルによって、組合せ爆発など計算量の爆発が起こるか起こらないかは変わることがある。量子計算などにより計算する側の計算量に爆発を起こすと、計算量の爆発に対応可能となるような計算資源が用意できる(ただし、2016年現在、この例を実際に計算可能な量子コンピュータが実現できる現実的な見通しはまだ無い)。

情報システム開発における組合せ爆発

情報システム開発では、実世界の複雑性を反映して、システムの各部分の状態の数や、モジュール間の関係の数、処理フローの数そしてテストケースの数は、組合せにより爆発的に大きなものになる。このため、設計、開発、テストを決まった期間で行うのは容易なことではない。組合せ爆発の規模を極力おさえ、また爆発を前提としてうまく制御し対応することが、大規模システム開発を成功させる鍵である。

最終起動時刻表示プログラムの例

情報システムの例として、システムが最後に起動した時刻をリクエストにしたがって表示するプログラムを考える。

システムが起動したときに動くようにオペレーティングシステム(OS)に登録する起動時刻記録プログラムが、OSから時刻を取得してディスクファイルに書く。コンソール(コマンドプロンプト)から起動される起動時刻表示プログラムが、上記ディスクファイルから起動時刻を読んでコンソールに表示する、という仕様で作ったとする。これだけなら機能が入力と出力がそれぞれひととおりと数えれば2個しかないので、テストも、システムを起動して1、2回表示コマンドを打って確かめればすむであろう。ところが、会社のコンソールからの照会だけでなく、管理者が出先からメールで照会したらメール返信で教えてほしいとなると、メール受信→受信メール解読と、起動時刻取得後の返信メール編集→メール送信という一連の処理ルートを作り足すことになる。せっかく作るのなら、コンソールでコマンドを入れたら起動時刻を管理者にメールで送信する機能なども欲しいとなれば、入力2×出力2通りの組合せが必要になる。

さて、起動時刻は西暦で24時制で表示していたのを、役所に出す資料にするので和暦の12時制で印刷できるようにしてほしいという要望が出て、では西暦の12時制などもできるようにと、表示が2×2の4通りに発展する。この段階で、(コンソール+メール)×(入力+出力)×(西暦+和暦)×(12時制+24時制)の24で16通りが動くようにプログラムを実装して、少なくとも16通りのテストしなければならない。

さらに、ウェブ経由でブラウザ画面からも照会可能にして日と時刻は色を分けて欲しい、その場合チェックボックスで指定があれば曜日も別の色でつけて欲しい、メールからの場合は照会記録をハードディスクに記録して欲しい、起動から1分後にコンソールに自動的に表示して欲しい、というように仕様が増えてくると、いちど作ってテストし終わった機能も再修正して再テストしなければならない。

個々の機能がもつ何十何百という変数群の値の組合せを列挙していくだけでも、天文学的な量になる。上記時刻を、すべてのありうる時刻についてテストすることが不可能なのは明らかである。一般には、代表的な値、あるいは、障害の出やすい値のみテストする。日、月、年の変わり目、閏年、100年の区切りなど特別扱いしてテストしていくだけでもテストケースの数は多くなり、それに上記の機能の組合せの数を掛けるのであるから、組合せはさらに高次元に爆発する。

テストケースはあらゆる場合を尽くすのが理想ではあるが、現実には組合せ爆発のためにテストケースが多すぎて、実行はもとより記述さえしきれない。変数値の組合せがだめなら、IF文などで分岐する経路だけは全部試そうというアプローチもあるが、それでも数が多すぎる。論理矛盾チェックや装置障害のようにテストが困難な分岐条件もある。手に負えないと開発をあきらめることは許されない。そのためテスト漏れがあって多くの障害が起こるのが宿命であり、現実である。

この例はこれでも単純で、商用のアプリケーションプログラムやOSはこの何百倍から何百万倍以上も複雑である。

システム開発はアプリケーション内部だけの世界ではできない。開発者が理解すべきものには、プログラミング言語の諸機能をはじめ、OS、OSとアプリケーションの中間に位置する(DBMSバッチ処理システムなどの)ミドルウェアハードウェアネットワークなどの、表面的な仕様に加えてどのようなときにどう動くかという振る舞いもある。これら人工物の複雑性が、アプリケーションがサービス対象とする実世界の複雑性に輪をかけて開発を大変にしている。

銀行の勘定系システムの例

ファイル:Six dimensional banking system model.jpg
6次元の銀行システムモデル(大規模情報システム分野における組合せ爆発の例)

大規模アプリケーションプログラムの例として銀行の勘定系システムを取り上げる。

システム機能には大まかにいって、顧客属性(優遇など)×商品属性(利率など)×取引属性(入金など)×端末属性(自動入出金機など)×時間帯(締前締後など)×政策属性(税率など)の6次元以上ある。この各次元が数百項目の変数で制御される。

この数百項目の変数の固まりには、一見同じようでも種類や内容が微妙に異なる種類があって、画面やデータベースやバッチファイルや伝送相手ごとなどの管理単位ごとに、別々のレコードになっている。

項目には、法人個人区分のように真偽の2個だけをとる単純なブール型もある。一方、定期預金口座残高のように1兆円もの数を収容できる(すなわちそれほどの状態数をもてる)ものもある。残高を十分大きい18桁の10進数で定義したから1個の状態で代表させようなどとあなどることはできない。18桁全部使い切らないがためにいろいろな処理が必要になる。入出力する最大金額や、税制・商品仕様等で決まる境界金額などそれぞれについて、イコールおよび1小さい値を考慮し、数値を丸める、エラーメッセージを返す、係員に警告するなどの処理が必要なこともある。これらをコーディングするだけでテストしないと、「1千万円以上の定期預金は金利優遇」のはずがちょうど1千万円のときに適用されないというプログラムミスに気づかないかもしれない。さらに、基本的な0円や、各種桁数でちょうどあるいは半端な金額を扱い、負の数値が許されないならエラー処理も扱う。このように、1個の“箱”であっても、中の数値によって数十通りの状態を意識して設計、実装、テストしなければならない。

以上の状態の数をすべて掛け合わせれば100億以上にもなりえる。開発作業は、その超空間に浮かぶ100億以上もの状態点を意識しながらなるべくまとめて処理するよう、慎重に進められる。

組合せ爆発の制御と対応

この組合せ爆発を緩和するために、独立(直交)する機能ごとに分けることが一般的である。構造化プログラミングを行ったうえで、独立した機能をもった共通モジュールを設けるアプローチ、あるいは、オブジェクト指向プログラミングが採用されてきた。つまり現実世界の組合せ爆発を、直交した機能モジュールの組合せ爆発とぴったり対比させることで、うまくコントロールしようという努力といえる。

しかし現実のアプリケーションは機能が直交するように分けきれないことが多い。それに、直交するように分けたつもりでも、現実の世界で機能が直交していないために、新たな要件が生じると直交していないことが分かることも多い。

たとえば、上記最終起動時刻表示プログラムにおいて、時刻編集とウェブ画面編集は機能が直交すると考えて別モジュールにしたとしても、ウェブをアクセスしているブラウザの種類に応じて画面に送る曜日の漢字の文字コードを変えて欲しいとなれば、整合性のあるように両方のモジュールを直す必要がある。しかも、直さなかった部分が壊れなかったかの確認テストEnglish版も含めて、おびただしい数のテストをしなければ安心できない。

オブジェクト指向では変数を他のオブジェクトから扱えないように隠蔽English版conceal)することで、保守を独自にできるようにする効果がある。しかし内部変数のとりうる状態の数は実はそのオブジェクトの果たす機能と密接であり、他のオブジェクトの設計者がそれらを意識しなければならないことも多い。すなわち、オブジェクト化で組合せの数を減らそうとしてもそれほど単純には減らない。

そして直交する機能にあるいは直交できなかった機能に細分化されたモジュールやオブジェクトの量がひとつのシステムで数千から数十万にも達すると、それら相互の関係の数あるいはインタフェースの数は組合せ爆発を起こす。これが、人間の理解や記憶を難しくし、生産性を下げる。同じ人が同じ機能のモジュールを忘れて二度開発する現象はその典型であって笑い話になるが、別の人同士がよく似た機能のモジュールを次々に作る現象は日常のことである。同じ会社でも別プロジェクト同士なら当たり前になっている。むしろ重複開発を回避するのには非凡な労力が必要となる。

このため、機能が4倍になったら開発工数は比例で4倍になるのではなく、たとえば8倍になるといった非線形な増え方をすることに注意を要する。既存機能の調査、関連モジュールの修正、テスト、デバッグと、それぞれが開発チーム内やチーム間の共同作業になる。既存機能が大きくて複雑であればあるほど追加工数は増える。 上記の銀行システムのような大規模システムでは、機能がなるべく直交するように最適にモジュール化しても、できあがるプログラムは、3百万~1千万行にもなる。組合せ爆発などのせいで開発生産性は1人月あたり200~400行に落ちる。すなわち20~50分間に1行の割なので一見楽な作業に思えるかもしれないがそうではない。千人規模のチームメンバーの頭の中に、上記の100億規模の組合せのイメージを分散共有してプログラムを設計し実装しテストするには、これだけの時間もかかる。

今後の解決アプローチ

オブジェクト指向プログラミングだけでは解決しきれない組合せ爆発の問題に対して、さらに人間の考え方に近い仕様の記述からプログラム自動合成をするアプローチも取られている。アスペクト指向プログラミングデザインパターンなどが研究され、より強力なプログラミング言語仕様記述言語モデリング言語などが次々に生まれてきている。

これらは、よくできたコンポーネントをよくできた自動処理でコントロールして意図的に起こす組合せ爆発をもって、実世界の複雑性に起因するシステムの組合せ爆発を制する、という挑戦ともいえる。並列度の高い超並列コンピュータバイオコンピュータによれば実現性はさらに高まると考えられる。

ただ、そうした研究を積み重ねても、現実世界の複雑性を反映するソフトウェアの組合せ爆発が今後数年、十数年で解決しそうにもない。そこで、設計、開発、運用に至るまで、

  1. 経験や障害予想能力を活用し、
  2. 安定したコンポーネントを再利用し、
  3. (上記超空間中で実装されている交点にあたるセルを突く)意味のあるデータあるいは本番データによるテストを極力自動化し、
  4. 試行期間確保、段階的移行その他のリスク分散策をとる

など、多面的に手法を駆使して対処していかなければならない。

参考文献

関連項目

外部リンク