Chapter 1

なぜ「順番」はこんなに難しいのか

あなたは Amazon の配送員になった。
今日回るのは 5 軒。スタート地点（営業所）に戻ってくる必要がある。

質問はひとつだけ。
どの順番で回ると、走行距離が最短になる?

ちょっと考えてみてほしい。5 軒ぐらいなら、地図を見ながら頭の中で「ここ通って、こう曲がって…」と組み立てられそうな気がする。

じゃあ実際にやってみよう。

1.1 5 軒のお宅を回るゲーム

図 1.1 — 5 軒のお宅 A〜E と、出発・帰着地点の営業所。

順番の組み合わせは何通りある?
最初の1軒は5通り、次は4通り、その次は3通り、2通り、1通り。かけ算して 5 × 4 × 3 × 2 × 1 = 120 通り。

うーん、120通りなら全部試せそう。実際 PC なら一瞬で全列挙できる。

じゃあ訪問先を 10 軒にしてみよう。
10 × 9 × 8 × … × 1 = 3,628,800 通り。これも PC ならまだ余裕。

20 軒だと?
20! = 2,432,902,008,176,640,000 通り。
… (息を吸う音) …
全部試したら、現代の PC でも数百年かかる。

これが組合せ最適化の最初の罠だ。n が少し増えるだけで、組み合わせの数は爆発する。

1.2 「全部試す」がダメなら、賢く考えればいいじゃん?

そう思うのは健康な反応だ。
だが残念ながら、この種の問題には「全列挙より本質的に賢い解法」がたぶん存在しない。

たぶん、と言ったのは —— これは P ≠ NP 問題という未解決問題と関わっていて、人類は誰も「絶対にない」と証明できていない。だが「たぶんない」というのが、半世紀の研究のコンセンサスだ。

さっきの 5 軒のお宅を回る問題、有名な名前がある。
巡回セールスマン問題 (Traveling Salesman Problem, TSP)。おそらく組合せ最適化で世界一有名な問題。
そして、TSP は NP困難と呼ばれるクラスに属する。これは「効率的に解くのが（たぶん）絶望的」というスタンプだ。

1.3 NP困難ってなに?

ここで NP がどうのとかちゃんとした定義に入るのが普通の教科書だ。
でも本書では、まず直感だけつかんでもらいたい。

P (簡単な問題): 答えを見つけるのに多項式時間でできる。例: 「1万人の社員を年齢順に並べる」「最短経路を計算する」。 n が増えても、計算時間は n² とか n³ の範囲。

NP (検証なら簡単な問題): 答えを渡されたら多項式時間で正しさを確認できる。例: 「この順番なら総距離 100km 以下です」 → 足し算するだけ。
ただし、見つけるのは難しいかもしれない。

NP困難: NP の問題の中でも最強の難しさを持つ。これが効率的に解けたら、世界中のあらゆる NP 問題が全部解ける。

TSP、ジョブショップスケジューリング、ナップサック、配送計画 … 本書で扱う問題はすべて NP困難だ。仲間がいっぱいいて寂しくない。が、つらいことに変わりはない。

1.4 指数関数はどれくらい凶暴か

NP困難の問題に対する「いちばん素朴な全探索」は、指数時間 (例: $2^{n}$ ) か階乗時間 (n!) を要求する。これがどれくらい怖い数字なのか、表で殴られてみよう。

図 1.2 — n が増えたときの計算時間の伸び方。緑 (n³ 以下) なら扱えるが、黄・赤の世界に入ると n=30 でも宇宙が終わる。

n	n³	2ⁿ	n!
10	1,000	1,024	360 万
20	8,000	100 万	2.4 × $10^{18}$
30	27,000	10 億	2.6 × $10^{32}$
50	12.5 万	1,000 兆	3 × $10^{64}$

ちなみに観測可能な宇宙にある原子の数はだいたい $10^{80}$ 。
n=50 の階乗 (3 × $10^{64}$ ) はそれより少ないけど、それでも狂気の数字だ。

1.5 「諦める」のではなく「うまくサボる」

ここまで読むと「もうダメじゃん」と思うかもしれない。
でも実は、人類は半世紀かけて四つのうまいサボり方を編み出してきた。

組み合わせて 使う「貪欲で初期解を作って → 局所探索で磨いて → 残った部分だけ厳密解法に投げる」みたいに

図 1.3 — 「NP困難でも諦めない」四つの戦略。本書は主に D を扱う。

1.6 専門用語マップ — 似た言葉が多すぎる問題

この分野、本当に紛らわしい用語が多い。今のうちに整理しておく。

最初は混乱しても全然OK。「あ、これあそこに出てきたやつ」となるくらいで十分。正確な使い分けは本書を読み進めながら染み込ませよう。

用語	ざっくり言うと	例
ヒューリスティック	「これでだいたい良くなる」経験則。問題ごとにオーダーメイド。	最寄りの店から訪問する
メタヒューリスティック	「ヒューリスティックを動かす上位ルール」。問題を選ばない汎用フレーム。	SA, Tabu, GA, ALNS
近似アルゴリズム	「最適の C 倍以内」を理論的に保証。	TSP の 1.5 近似 (Christofides)
厳密解法	「最適保証」。ただし時間は指数的に最悪。	MIP ソルバー、CP-SAT
マッチヒューリスティクス	ヒューリスティック × 数理計画のハイブリッド。今の流行。	LNS over MIP

本書では、第2〜5章で「ヒューリスティック → メタヒューリスティック」と階段を上り、第6章でいきなり厳密解法側にジャンプして、両者を握手させる。

1.7 「良い解」って何だ?

最適性は諦めるとして、じゃあ何を持って良い解とするのか?
これが意外と曲者。本書を通じて何度も戻ってくるテーマだ。

解の評価軸は、ざっくり 4 つ。

品質: 目的関数の値。低いほど良い (最小化問題なら)。
時間: 答えが出るまでの計算時間。夜間バッチ? それとも 3 秒?
頑健性: 入力がちょっとブレても、解が壊れないか。
説明可能性: 「なぜこの答えになったか」を現場に説明できるか。

1 だけ追うと、品質競争の罠にはまる。
2〜4 を忘れると、本番で使われない。

1.8 銀の弾丸はない (No Free Lunch)

最後に大事な警告を一つ。

1997年に Wolpert と Macready が示した No Free Lunch 定理は、「あらゆる問題を平均すれば、どんなアルゴリズムも同じ性能」と主張する。

平たく言えば: 「これさえ覚えればOK」な万能アルゴリズムはない。

逆に言えば、問題の構造を使えば、汎用アルゴリズムに必ず勝てるということでもある。
だから本書は「アルゴリズムのカタログ」ではなく、**「あなたの問題にどれをどう刺すか」**を考える本になる。

1.9 この章の振り返り

「順番を決める」「割り当てる」系の問題は、n が増えると組み合わせが爆発する。
多くの実問題は NP困難。全列挙より本質的に賢い解法は (たぶん) ない。
でも対処法は四つある。本書は主にメタヒューリスティクスを扱う。
「良い解」は品質だけでなく、時間・頑健性・説明可能性で多面評価する。
銀の弾丸はない。問題の構造を使うのが王道。

さあ、次の章でいよいよ最初の道具を手に取る。最も古く、最もシンプルで、それでも今も現役の道具 —— 貪欲法だ。