組合せ爆発とは？10件で360万通り、20件で243京通りに膨らむ理由

組合せ爆発とは何か（数で見るインパクト）

組合せ爆発とは、選択肢や要素の数が増えるにつれ、その組み合わせの総数が指数関数的あるいは階乗的に膨らむ現象です。要素を線形に1つ増やしただけで、組み合わせは桁違いに増加します。直感の届く範囲をはるかに超えた数字が、ごく日常的な計画業務の背景に潜んでいるといえるでしょう。

順列・組合せが指数関数的に膨らむメカニズム

組合せ爆発のメカニズムは、シンプルな掛け算で説明がつきます。たとえば異なる製品をどの順序で生産するかという問題は、数学的には「順列」の問題であり、その総数はnの階乗（n!）で表現されます。製品が5つなら5×4×3×2×1で120通りに過ぎませんが、10個に増えれば10!で約362万通り、20個では20!で約243京通り（2.43×10の18乗）に達します。

要素が2倍になるだけで、組み合わせの規模は何兆倍にも膨らんでしまうわけです。順列だけではなく、複数の選択肢を独立に選ぶ問題（2の累乗で増える形）でも同じ性質が現れます。線形にしか増えていないように見えても、舞台裏ではすさまじい速度で空間が広がっている。これが組合せ爆発の本質的な姿です。

10件・20件で何通りになるのか

具体的な数字に置き換えると、その大きさがより鮮明になります。10件の並べ方は約362万通り。15件で約1.3兆通り。20件で約243京通り。25件まで増えれば1.55×10の25乗通り、もはや日常語彙では呼びようのない領域に入ります。

参考までに、世界人口は約80億人（8×10の9乗）です。20件の並べ方は、世界人口の3億倍に相当します。30件になれば、宇宙に存在する原子の数（約10の80乗）にこそ届きませんが、宇宙の年齢を秒数で数えた値（約4.35×10の17乗秒）よりも桁違いに大きくなる。要素が10件分増えるだけで、こうした非常識な規模に飛んでいくのです。

「とりあえず全パターン試す」が破綻する分岐点

なぜ全パターンを試せないのでしょうか。仮に1秒間に1億通りを評価できる計算機があったとしても、20件の並べ方なら約770年、25件で約49億年、30件にいたっては地球誕生から現在までの時間でも処理しきれない計算になります。

実務でよく扱われる規模、たとえば数十件から数百件の計画問題は、見た目こそ小さく感じますが、組み合わせの観点では計算機の処理能力をはるかに超えた領域に位置しています。全探索が機能する分岐点は、おおよそ十数件あたりにあるといって差し支えありません。それを越えた瞬間、力技ではどうにもならない世界に入っていきます。

計画業務の現場で起きている組合せ爆発

組合せ爆発は理論上の話ではなく、日々の計画業務のなかですでに起きている現象です。製造、配送、シフトのいずれの分野でも、人の頭で扱える限界を大きく超えた組み合わせが、毎日生み出されています。

製造現場で起きる生産順序と段取り替えの爆発

たとえば多品種少量の製造ラインで、20種類の製品を1ラインに流す順序を決めるとします。単純な並べ替えだけで243京通り。実際には製品ごとの段取り替え時間、納期、設備能力、作業員の配置といった条件が絡むため、組み合わせはさらに広がります。

現場で「とりあえずやれそうな順序を作って、ダメなら直す」という運用が長年続いてきたのは、人手で全パターンを比較することが原理的に不可能だからです。Excelで運用されてきた製造現場ほど、組合せ爆発の影響を強く受けやすい構造といえます。

配送現場で起きる巡回ルートと積載パターンの爆発

配送計画の世界では、巡回セールスマン問題と呼ばれる古典的な問題が知られています。20拠点を巡る順路だけで約12京通り、30拠点なら8.84×10の30乗を超えます。ここに車両ごとの容量、積載順序、時間指定、休憩、ドライバーの勤務制限が加われば、現実の問題はさらに膨大な解空間をもつことになります。

ベテランドライバーが地図を見ながら経験で組み立てる順路には、確かな知恵が宿っています。ただし、車両10台が30拠点を分担する規模になると、人手では全体最適どころか「悪くない案」を作るだけで何時間もかかってしまうのが実情でしょう。

シフト現場で起きる勤務割当と希望反映の爆発

シフト作成の組み合わせも、見た目以上の規模に膨らみます。30人を31日間、3シフトに割り当てるだけで理論上の組み合わせは3の930乗。ここに資格、休暇希望、夜勤明けの翌日制限、公平性、業務量などのルールが加わると、解空間は天文学的という形容すら控えめに感じる広がりを見せます。

シフト作成に毎月数日を費やしている職場が珍しくないのは、こうした組み合わせの広さに対して、人間の認知資源が圧倒的に足りていないからです。属人化や時間消費といった現場の悩みも、突き詰めれば組合せ爆発に行き着きます。

全探索が現実的に不可能になる根本原因

「組み合わせが多くてもコンピュータで全部試せばよいのでは」という発想は自然なものです。しかし組合せ爆発が発生する問題では、全探索という前提そのものが成立しません。背景には3つの構造的な理由があります。

計算量がn!や2^nで増える非線形性

第一の理由は、計算量の増え方そのものが線形ではないことです。要素を1つ追加するだけで、組み合わせ数は何倍にも膨らみます。19件と20件は、見た目には1件しか違いません。けれども20!は19!の20倍、25!は20!の127万倍にあたります。

要素が線形に増えるのに対し、組み合わせは指数や階乗で増える。この「成長のスケールが違う」という事実こそが、全探索を阻む最大の壁です。問題サイズが小さいうちはなんとかなりますが、ある分岐点を越えた瞬間、計算量が現実時間を突き抜けて伸びていくのです。

制約条件が掛け算で複雑性を増やす

第二の理由は、現場の制約が組み合わせの複雑性をさらに増幅させる点にあります。製造現場であれば「設備の能力」「段取り替えの順序ルール」「作業員のスキル」「納期」「休憩」など、数十種類の制約が同時に効いてきます。

制約が増えると、許される組み合わせの数は減りそうに思えるかもしれません。実際にはそうとばかりは言えず、制約同士の相互作用によって「ある解が他の制約を破る」状況が無数に生じ、解空間の評価が一気に重くなります。現場ルールの掛け算が、問題そのものを一段難しくするのです。

トレードオフ（複数の評価軸）が解空間を歪める

第三の理由は、評価指標が複数あることです。生産計画なら、納期遵守率、稼働率、段取り替え時間、残業時間といった複数の目標を同時に追いかけます。配送計画なら、距離、時間、ドライバー負荷、積載率。シフトなら公平性、希望反映、人件費。

たとえばコストを下げに行けば残業が増え、納期を優先すれば稼働率が下がる。一方を改善するともう一方が悪化する関係が、計画問題には必ずといっていいほど存在します。単一の最大値を探す問題に比べ、複数のバランスパターンを探さなければならない問題は、解空間の形が大きく歪み、しらみつぶしの探索がさらに重くなるのです。

計算機の進化では追いつけない理由

「ハードウェアが速くなれば組合せ爆発はいずれ解決するのでは」という期待は、技術の進歩を信じる立場として自然なものでしょう。ただし数学的には、計算機性能の向上だけでは追いつけない壁が存在します。

宇宙年齢を超える計算時間のスケール

宇宙の年齢は約138億年、秒に直すと約4.35×10の17乗秒です。30!は約2.65×10の32乗。1秒間に1億通りを評価できる計算機を仮定すると、30件の並べ替えだけで約8.4×10の16乗年、宇宙年齢のおよそ600万倍の時間を要する計算になります。

これは「処理速度を10倍にすればよい」という議論で片付く話ではありません。問題サイズがあと数件増えるだけで、求められる計算時間は再び桁違いに伸びてしまうからです。物理法則が変わらない限り、力技で組合せ爆発を制圧する道はないと考えてよいでしょう。

ハードウェア性能向上は線形、組合せ爆発は指数

ムーアの法則が成立していた時代でも、計算機の性能は約2年で2倍という、おおむね線形に近いペースで伸びてきました。一方で組合せ爆発は要素1件追加で何倍にもなる、まさに指数の世界。年単位の性能向上を、要素数たった1件の増加が一瞬で食い潰してしまうのが現実です。

つまり「あと数年待てば解ける」という未来は、組合せ爆発に関しては来ません。発想そのものを変える必要があるのです。次の章では、その発想転換がどう設計されているかを見ていきます。

最適化AIが切り拓く解決への道

全探索が機能しないのであれば、別のアプローチが必要です。最適化AIは、すべての候補を試すのではなく「現実的な時間で、十分に良い計画を見つける」ことをゴールに据えて設計されています。守るべきルールを定義し、最も良くしたい指標を定義し、その条件下で良質な解を素早く探し当てる。これが最適化AIの核となる考え方です。

OptHubの最適化AIは、製造、配送、シフト、在庫の4領域で「賢い計画表」を自動で作成します。守るべき制約条件、最大化したい目的、現場固有のルール。これらをモデル化したうえで、力技ではなく経験的に効率の良い探索を行うことで、計画業務の質とスピードを同時に引き上げます。ここからは「導入で何が変わるか」を3つの側面から見ていきましょう。

精度はどう変わるか

人手の計画では、限られた時間の中で確認できる組み合わせは数十から数百が限界でしょう。最適化AIは数十万から数百万単位で候補を評価し、そのなかで最も良いものを返します。243京通りを全探索することはできなくても、構造的に有望な領域を集中的に探索することで、人手で到達不可能な品質の解にたどり着けるわけです。

「現場の勘で作った計画より明らかに良い」という体感が現場の納得感につながり、運用に乗せやすくなる効果も得られます。

スピードはどう変わるか

最適化AIは、人手では数時間から数日かかる計画作成を、数分から数十分の単位で生成できます。配送ルートの立案やシフト作成、生産計画のように変数と制約が多い業務ほど、この高速化の効果が大きく表れます。

スピードが上がる効果は、単なる作業時間の短縮にとどまりません。突発的な受注変更や欠勤に対しても、計画を作り直す余裕が生まれることで、現場の柔軟性そのものが大きく向上していきます。

透明性はどう変わるか

最適化AIは、守るべき制約と達成したいゴールを明示的に定義します。そのため「なぜこの計画になったか」を制約とゴールで説明できる点が、生成AIや勘ベースの計画とは決定的に異なります。

「夜勤明けの翌日は日勤に入れない」「特定の工程は必ず2人以上で担当する」といった現場独自のルールも、制約として組み込めば出力された計画は一切破りません。運用担当者が中身を確認しやすく、属人化していた判断基準が見える化されるという副次効果も期待できます。

まとめ

組合せ爆発は、計画業務の規模が一定を超えた瞬間に必ず姿を現す現象です。10件で360万通り、20件で243京通り、30件では宇宙年齢でも追いつかない時間が必要になる。要素が線形に増えるだけで、組み合わせは桁違いに膨らむという事実が、人手や全探索の限界を生み出しているのです。

それでも「賢く探索を絞り込む」という考え方を採用すれば、現実時間で十分に良質な計画を作ることは可能になります。最適化AIはまさにその思想に基づく仕組みであり、精度・スピード・透明性の三方で計画業務の景色を一新します。組合せ爆発は越えられない壁ではなく、適切な技術と業務整理によって乗りこなせる対象です。

自社の計画業務がどんな組み合わせの広さに直面しているのか。その理解こそが、最適化AI活用の第一歩になります。気になる業務領域から順に、変数と制約を棚卸しすることを、まずお勧めします。