Chapter 1

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

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

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

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

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

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

営業所 A B C D E
図 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困難の問題に対する「いちばん素朴な全探索」は、指数時間 (例: 2n2^{n}) か階乗時間 (n!) を要求する。 これがどれくらい怖い数字なのか、表で殴られてみよう。

問題サイズ n → 計算時間 n³ (現実的) 2ⁿ (絶望) n! (即死) 「効率的に解ける」とは、緑のカーブの世界にいられること
図 1.2 — n が増えたときの計算時間の伸び方。緑 (n³ 以下) なら扱えるが、黄・赤の世界に入ると n=30 でも宇宙が終わる。
nn³2ⁿn!
101,0001,024360 万
208,000100 万2.4 × 101810^{18}
3027,00010 億2.6 × 103210^{32}
5012.5 万1,000 兆3 × 106410^{64}

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

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

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

A. 全力で正攻法 分枝限定、MIP、CP 枝刈りで間引く → 中規模なら勝てる → 第6章 B. 楽な問題に変身 最短路、フロー、 マッチング、LP → 多項式時間で解ける 運がよければ C. 「だいたい」で妥協 近似アルゴリズム 「最適の 1.5 倍以内保証」 → 理論的に美しい → 実用は限定的 D. 経験で押し切る 貪欲、局所探索、 メタヒューリスティクス → 保証なし、実戦最強 → 第2〜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 つ。

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

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

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

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

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

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

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

1.9 この章の振り返り

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