数え上げの変化の不思議と経営学－組合せ爆発の動画を鑑賞して思うこと
教授 鷲崎早雄（経営情報学、経済工学）
少し古い話になるが、2012年9月に友人から一通のメールが届いた。タイトルは「組合せ爆発」となっていた。内容は一本のYouTubeの動画の紹介である。企画・制作は日本科学未来館とJST ERATO湊離散構造処理系プロジェクトという団体である。時間がある方はまず動画を見ていただきたい(http://www.youtube.com/watch?v=Q4gTV4r0zRs)。
ストーリーを追いながら話を進めよう。最初にお姉さんと子供たちが現れて、お姉さんが「今日は数え方の勉強をしようね」というと、子どもたちが元気に「ハーイ！」と言っている。お姉さんが黒板に四角い図形（１×１）を描いて、左上をS（スタート）、右下をG（ゴール）として、「スタートからゴールまで何通りの通り方があるかな？」と子供たちに聞く。子供たちは元気に「2通り」と答える。お姉さんは続いて2×2のマス目を描いて、「では、2×2の場合はどうかな？ でも同じところは2度通ってはダメヨ！」と聞く。子供たちは数え始めて「6通り」というが、お姉さんは１つ１つ通り道を示しながら「いいえ、全部で12通り」と教えている。更に続けてお姉さんは「3×3の時は？」と聞くが子供たちは「難しそう！」と言って手が出ないので、またお姉さんは1つ1つ数えて、「この通り184だね！」と、にこにこしながら答えを教えた。お姉さんは、さらに元気いっぱいに「4×4のとき」と言って数え始める。ところが一向に数え終わらない。お姉さんは必死に数えて「8512だってよ！」と言ってぶっ倒れてしまう。ここまでが第1幕、動画は「何とか人間で数えられる範囲」であることを示している。
次からはお姉さんは疲れて腕が上がらないのでパソコンで数えることを宣言して、5×5をパソコンに実行させる。パソコンは瞬く間に126万2816通りと答えを出した。子供たちは「126万？」とビックリしているが、お姉さんは再び元気に「どんどん行くよ、次は6×6のとき」、ところがパソコンもだいぶ苦しそうで、お姉さんと子供たちが「わっしょい、わっしょい」と声援してやっと5億7578万0564通りという答えが出てきた。子供たちは「6分割で5億通りも組み合わせがあるの？」と目を丸くしている。お姉さんは「次は7×7をやりましょう、でも、もうパソコンは苦しそうだからスーパーコンピュータを使いましょう！」と言い、みんなはスーパーコンピュータの前に座る。すぐにお姉さんが叫ぶ。「出ました7893億6005万3252通り！」、子ども達は「すごーい、さすがスーパーコンピュータ」と大はしゃぎである。
この後、8×8分割では4時間かかって3266兆5984億8698万1642通りになった。またお姉さんが言う。「それでは9×9分割ではどのくらいかかるかな、8×8では4時間くらいだったから今度は2,3日はかかるわね、だから今日はお泊りね！」、子ども達は「お泊りだ、わーい！」と元気そうである。それで9×9分割の計算をスーパーコンピュータで始めたが、何日たっても、何か月たっても答えは出てこない。季節が変わっても、年が変わっても出てこない。ようやく答えが出てきたのは、6年後で、小さかった子供たちは、もう中学生になっていた。答えは4104京4208兆7026億3249万6804通りである。続けてお姉さんは元気に「次は10×10よ！」と言うが、子ども達は「ちょっと待って、8×8では4時間、9×9では6年半、1万倍以上かかっているということは、10×10ではお姉さんが死んじゃう、やめて」と叫ぶ。お姉さんはシリアスな顔で「分かっているわ、でもね、お姉さんはみんなに組合せ爆発のすごさを教えたいの、止めないで！！」と言ってスーパーコンピュータのスイッチを押す。ここから先は感激の筋書きなので書かないことにするが、答えは1ジョ5687垓(ガイ)5803京0464兆7500億1321万4100通りである。毎秒2000億回計算することができるスーパーコンピュータで26万年かかってようやく答えが出てくるのである。それでは、11×11は？ この方法で答えを出すには296億年かかるという。宇宙の年齢は137億円と推定されているから、それより長い時間がかかる。
組合せ爆発のすごさは、2×2では組合せ全部を数え上げるのに、ものの5分くらいで結果が出てくるが、それをたった11×11にしただけで、スーパーコンピュータを使っても296億年かかるという、その変化の異常さにある。このような変化の異常さは、ネズミ算や複利計算に現れる「指数爆発」でも同じである。有名な例としては、碁盤の目にお金を積んでいく話がある。9×9の碁盤の最初のマス目に1円が置いてある。2番目のマス目にはその2倍の2円を置く、3番目のマス目にはその2倍の4円を置く。こうして倍々でお金を置いていった場合に、最後の81番目のマス目には幾らお金を積まなければならないかという問題である。答えは何と1ジョ2089垓2581京9614兆6291億7470万6176円になる。たかだか碁盤の目に積んでいくだけなのに、1兆倍のそのまた1兆倍という、この変化の異常さに目を奪われてしまう。
ところが話はこれだけでは終わらない。お金を積んでいく方は、280の計算をする話であるので計算する式が分かっているが、組合せの方は計算式が今のところ分かっていないのである。従って、一つ一つ数え上げていかなければ答えが見つけられないのである。スーパーコンピュータをいかに早くしても、この手の数え上げの計算は、人間の生命の範囲内では答えを求めることができない。できたとしても、せいぜい1ケタ上げること、今が8×8ができるのであれば、9×9ができるようになるのが精一杯であろう。ところが、日本の北海道大学の湊教授のグループは24×24分割まで答えを正確に求めている。何故なのかというと、早く答えを出すことができる組合せを発見する方法の研究に成功しているからである。このように、コンピュータで答えを求める方法のことを「アルゴリズム」というが、素晴らしいアルゴリズムはスーパーコンピュータのハードウェアの進歩をはるかにしのいで、それまでのやり方の何万倍も発見時間を早くできたのである。
最後に、このような話は経営学にも大いに関係があることを申し添えたい。例えば、病院における看護師の交代勤務表を作成する問題、最適な資源ポートフォリオを決める問題、宅配便のトラックの配送順序を決める問題、受注と生産スケジュールのスケジューリング問題、幾つかの要素がある時にどういう組み合わせで実験していくかという問題（特に、遺伝子分野の実験や創薬の実験で重要である）、あるいはスポーツ運営分野ではテニスのダブルスの組み合わせ表を決める問題など、私たちの身の回りにも関係する問題は沢山ころがっているのである。これらの問題は、頑張って適当な解を発見することはできるかもしれないが、それは”たまたま”な解であって、「全体を見通してそれが良いかどうかという評価をしないと、本当はそれが解なのかどうかわからない」という性質の問題である。経営学には、経営の質を上げるためにはそういう部分があることを、特に文系の人達にもっともっと知ってもらいたいと思う。
少し古い話になるが、2012年9月に友人から一通のメールが届いた。タイトルは「組合せ爆発」となっていた。内容は一本のYouTubeの動画の紹介である。企画・制作は日本科学未来館とJST ERATO湊離散構造処理系プロジェクトという団体である。時間がある方はまず動画を見ていただきたい(http://www.youtube.com/watch?v=Q4gTV4r0zRs)。
ストーリーを追いながら話を進めよう。最初にお姉さんと子供たちが現れて、お姉さんが「今日は数え方の勉強をしようね」というと、子どもたちが元気に「ハーイ！」と言っている。お姉さんが黒板に四角い図形（１×１）を描いて、左上をS（スタート）、右下をG（ゴール）として、「スタートからゴールまで何通りの通り方があるかな？」と子供たちに聞く。子供たちは元気に「2通り」と答える。お姉さんは続いて2×2のマス目を描いて、「では、2×2の場合はどうかな？ でも同じところは2度通ってはダメヨ！」と聞く。子供たちは数え始めて「6通り」というが、お姉さんは１つ１つ通り道を示しながら「いいえ、全部で12通り」と教えている。更に続けてお姉さんは「3×3の時は？」と聞くが子供たちは「難しそう！」と言って手が出ないので、またお姉さんは1つ1つ数えて、「この通り184だね！」と、にこにこしながら答えを教えた。お姉さんは、さらに元気いっぱいに「4×4のとき」と言って数え始める。ところが一向に数え終わらない。お姉さんは必死に数えて「8512だってよ！」と言ってぶっ倒れてしまう。ここまでが第1幕、動画は「何とか人間で数えられる範囲」であることを示している。
次からはお姉さんは疲れて腕が上がらないのでパソコンで数えることを宣言して、5×5をパソコンに実行させる。パソコンは瞬く間に126万2816通りと答えを出した。子供たちは「126万？」とビックリしているが、お姉さんは再び元気に「どんどん行くよ、次は6×6のとき」、ところがパソコンもだいぶ苦しそうで、お姉さんと子供たちが「わっしょい、わっしょい」と声援してやっと5億7578万0564通りという答えが出てきた。子供たちは「6分割で5億通りも組み合わせがあるの？」と目を丸くしている。お姉さんは「次は7×7をやりましょう、でも、もうパソコンは苦しそうだからスーパーコンピュータを使いましょう！」と言い、みんなはスーパーコンピュータの前に座る。すぐにお姉さんが叫ぶ。「出ました7893億6005万3252通り！」、子ども達は「すごーい、さすがスーパーコンピュータ」と大はしゃぎである。
この後、8×8分割では4時間かかって3266兆5984億8698万1642通りになった。またお姉さんが言う。「それでは9×9分割ではどのくらいかかるかな、8×8では4時間くらいだったから今度は2,3日はかかるわね、だから今日はお泊りね！」、子ども達は「お泊りだ、わーい！」と元気そうである。それで9×9分割の計算をスーパーコンピュータで始めたが、何日たっても、何か月たっても答えは出てこない。季節が変わっても、年が変わっても出てこない。ようやく答えが出てきたのは、6年後で、小さかった子供たちは、もう中学生になっていた。答えは4104京4208兆7026億3249万6804通りである。続けてお姉さんは元気に「次は10×10よ！」と言うが、子ども達は「ちょっと待って、8×8では4時間、9×9では6年半、1万倍以上かかっているということは、10×10ではお姉さんが死んじゃう、やめて」と叫ぶ。お姉さんはシリアスな顔で「分かっているわ、でもね、お姉さんはみんなに組合せ爆発のすごさを教えたいの、止めないで！！」と言ってスーパーコンピュータのスイッチを押す。ここから先は感激の筋書きなので書かないことにするが、答えは1ジョ5687垓(ガイ)5803京0464兆7500億1321万4100通りである。毎秒2000億回計算することができるスーパーコンピュータで26万年かかってようやく答えが出てくるのである。それでは、11×11は？ この方法で答えを出すには296億年かかるという。宇宙の年齢は137億円と推定されているから、それより長い時間がかかる。
組合せ爆発のすごさは、2×2では組合せ全部を数え上げるのに、ものの5分くらいで結果が出てくるが、それをたった11×11にしただけで、スーパーコンピュータを使っても296億年かかるという、その変化の異常さにある。このような変化の異常さは、ネズミ算や複利計算に現れる「指数爆発」でも同じである。有名な例としては、碁盤の目にお金を積んでいく話がある。9×9の碁盤の最初のマス目に1円が置いてある。2番目のマス目にはその2倍の2円を置く、3番目のマス目にはその2倍の4円を置く。こうして倍々でお金を置いていった場合に、最後の81番目のマス目には幾らお金を積まなければならないかという問題である。答えは何と1ジョ2089垓2581京9614兆6291億7470万6176円になる。たかだか碁盤の目に積んでいくだけなのに、1兆倍のそのまた1兆倍という、この変化の異常さに目を奪われてしまう。
ところが話はこれだけでは終わらない。お金を積んでいく方は、280の計算をする話であるので計算する式が分かっているが、組合せの方は計算式が今のところ分かっていないのである。従って、一つ一つ数え上げていかなければ答えが見つけられないのである。スーパーコンピュータをいかに早くしても、この手の数え上げの計算は、人間の生命の範囲内では答えを求めることができない。できたとしても、せいぜい1ケタ上げること、今が8×8ができるのであれば、9×9ができるようになるのが精一杯であろう。ところが、日本の北海道大学の湊教授のグループは24×24分割まで答えを正確に求めている。何故なのかというと、早く答えを出すことができる組合せを発見する方法の研究に成功しているからである。このように、コンピュータで答えを求める方法のことを「アルゴリズム」というが、素晴らしいアルゴリズムはスーパーコンピュータのハードウェアの進歩をはるかにしのいで、それまでのやり方の何万倍も発見時間を早くできたのである。
最後に、このような話は経営学にも大いに関係があることを申し添えたい。例えば、病院における看護師の交代勤務表を作成する問題、最適な資源ポートフォリオを決める問題、宅配便のトラックの配送順序を決める問題、受注と生産スケジュールのスケジューリング問題、幾つかの要素がある時にどういう組み合わせで実験していくかという問題（特に、遺伝子分野の実験や創薬の実験で重要である）、あるいはスポーツ運営分野ではテニスのダブルスの組み合わせ表を決める問題など、私たちの身の回りにも関係する問題は沢山ころがっているのである。これらの問題は、頑張って適当な解を発見することはできるかもしれないが、それは”たまたま”な解であって、「全体を見通してそれが良いかどうかという評価をしないと、本当はそれが解なのかどうかわからない」という性質の問題である。経営学には、経営の質を上げるためにはそういう部分があることを、特に文系の人達にもっともっと知ってもらいたいと思う。