答え合わせは一瞬なのに、解くのは終わりません。PとNPの違いを、実際に解かせて確かめます。
前回: 文字列探索とKMP — grepは1文字ずつ見ていない
これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、手元で書いて、走らせて、数字を出します。 飛ばしても本線は進めます。 本線側の計算量の話は 1万件で100倍になる — 計算量とO記法を測る にあります。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。
「シフト表を自動で組む」機能を作ろうとして、3日溶かしました。
要件はこうです。スタッフが12人。1週間ぶん。誰にも希望休があって、資格が要る枠があって、連勤は3日まで。 その条件を全部満たす、一番いいシフト表を出す。
最初に書いたコードは、素直に全部の組み合わせを試すものでした。動きました。スタッフ8人までは。
10人にしたら、返ってきませんでした。
そこから2日、コードを速くすることに使いました。
- 内側のループを配列アクセスに変えた → 3倍速くなった
- 判定を先にやって早めに枝を切った → 10倍速くなった
Mapをやめて添字にした → 2倍速くなった
合わせて60倍です。それでも12人では返ってきませんでした。
理由は、いま書けば身も蓋もありません。
60倍速くしても、スタッフが2人増えれば元通りになる。
私が戦っていた相手は、自分のコードではありませんでした。問題のほうでした。
この記事は、「この仕事、頑張れば速くなるのか。それとも原理的に無理なのか」を見分けるための道具の話です。 試験に出る定義としてではなく、3日溶かす前に気づくための道具として書きます。
これは、個人開発者にとって実用的な話です。 最初に宣言しておきます。
対象レベル: 中級〜上級 / 区分: 発展
この記事でわかること
- 「解くのは大変なのに、答え合わせは一瞬」という非対称が、この話の全部であること
- NP は「解けない」という意味ではない。
Non-Polynomialの略でもない - P ⊆ NP。 速く解ける問題は、全部「速く確かめられる問題」に含まれる
- 「答え合わせが速いなら、解くのも速いはずか?」が未解決で、100万ドルかかっていること
- 最短経路は簡単なのに、最長経路は NP困難。 オイラー路は簡単なのに、ハミルトン閉路は NP完全
- NP完全だと分かることは、敗北ではなく前進。 探すのをやめて、諦め方を選ぶ判断ができる
- 現場の逃げ道は4つしかない(近似・ヒューリスティック・問題を小さくする・時間で打ち切る)
この記事でやること
- 作業フォルダ
~/cslab/npを作り、この記事の作業を全部そこに閉じ込める - 巡回セールスマンで、「答え合わせ」と「探す」の時間を両方測って並べる
- 総当たりを n=8 / 9 / 10 / 11 / 12 で実測し、壁が立つところを表にする
- ナップサック・ハミルトン閉路・最長経路・グラフ彩色を、実際に小さく解いてみる
- オイラー路・最短経路と並べて、「似ているのに片方だけ終わらない」を見る
- 逃げ道4つを実装して、最適解・所要時間・実装の手間を比べる
- 作ったものを全部消す
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 多項式時間 | n n² n³ n log n のように、n のべき乗までで収まる時間。実用の目安 |
| 指数時間・階乗時間 | 2ⁿ n! のように、n が1増えるだけで倍々に増える時間 |
| P | 多項式時間で解ける問題の集まり。「頑張れば速くなる」側 |
| NP | 答えを渡されたら、多項式時間で正しいと確かめられる問題の集まり |
| 証拠(証明書) | 「これが答えです」と差し出される具体的な1つ。NP の主役はこれ |
| NP困難 | NP のどの問題より簡単ではない問題。NP に入っているとは限らない |
| NP完全 | NP に入っていて、かつ NP困難。NP のいちばん硬いところ |
| co-NP | 「そんな答えは無い」ことを短く確かめられる問題の集まり |
| 帰着(きちゃく) | 問題Aを、問題Bを解く道具に言い換えること。「AはBに帰着できる」 |
| ヒューリスティック | 保証は無いが、たいてい良い答えが出る経験則の手順 |
| 近似アルゴリズム | 「最適の◯倍以内」と保証がつく手順。ヒューリスティックとは別物 |
① 準備 — 実験用のフォルダを作る
最後に全部消します。 作業を1か所に閉じ込めます。
v22.14.0
node が入っていなければ、JavaScriptの基本 の回に入れる手順があります。
まず共通の道具を書きます。都市をランダムに置いて、順路の長さを測るだけのファイルです。
// 固定の乱数(毎回同じ都市が出るように)
export function makeRng(seed) {
let s = seed >>> 0;
return function () {
s = (s * 1664525 + 1013904223) >>> 0;
return s / 4294967296;
};
}
export function makeCities(n, seed = 42) {
const rnd = makeRng(seed);
const cities = [];
for (let i = 0; i < n; i++) {
cities.push({
name: String.fromCharCode(65 + i),
x: Math.round(rnd() * 1000),
y: Math.round(rnd() * 1000),
});
}
return cities;
}
export function dist(a, b) {
return Math.hypot(a.x - b.x, a.y - b.y);
}
export function tourLength(cities, order) {
let sum = 0;
for (let i = 0; i < order.length; i++) {
const from = cities[order[i]];
const to = cities[order[(i + 1) % order.length]];
sum += dist(from, to);
}
return sum;
}
Math.random() を使いません。 毎回違う都市が出ると、この記事の数字が再現できないからです。 自前の乱数に種(seed)を渡して、誰が走らせても同じ地図になるようにしています。
order[(i + 1) % order.length] の % が、最後の都市から出発地に戻る辺です。 これを書き忘れると「一周」ではなく「片道」を測ることになります。最初に私が間違えたところです。
② 決定的な非対称 — 解くのは大変、確かめるのは一瞬
ここがこの記事の核心です。 先にこれを見てください。
配送先が12か所あります。全部を1回ずつ回って、出発地に戻ってくる。一番短い順路を出したい。 これが巡回セールスマン問題です。
「答え合わせ」をやってみる
誰かが「この順路なら3200km以下で回れますよ」と、順路を1つ持ってきたとします。
import { makeCities, tourLength } from './cities.mjs';
const cities = makeCities(12);
console.log('都市:', cities.map(c => `${c.name}(${c.x},${c.y})`).join(' '));
// 誰かが「この順路なら3200km以下で回れる」と言ってきた
const claimed = [0, 2, 3, 7, 10, 1, 11, 5, 9, 4, 6, 8];
const t0 = performance.now();
const len = tourLength(cities, claimed);
const ok = len <= 3200;
const t1 = performance.now();
console.log('主張された順路:', claimed.map(i => cities[i].name).join(' -> '));
console.log('合計:', len.toFixed(1), 'km');
console.log('3200km以下か:', ok);
console.log('答え合わせにかかった時間:', (t1 - t0).toFixed(4), 'ms');
都市: A(252,88) B(577,223) C(376,26) D(447,118) E(874,995) F(853,500) G(642,861) H(596,91) I(140,950) J(925,889) K(551,181) L(550,259)
主張された順路: A -> C -> D -> H -> K -> B -> L -> F -> J -> E -> G -> I
合計: 3148.7 km
3200km以下か: true
答え合わせにかかった時間: 0.2818 ms
0.28ミリ秒。
やっていることは12回の足し算だけです。都市が1000か所でも、1000回足すだけで終わります。 つまり答え合わせは、都市の数に正比例します。これは多項式時間です。
📷 スクリーンショット①: node verify.mjs の出力全体。0.28ms という数字が見えるように。
「探す」をやってみる
では、その順路を自分で見つけるのはどうか。
出発地を A に固定すると、残り11か所の並べ方は 11! = 39,916,800 通りです。全部試します。
import { makeCities, tourLength } from './cities.mjs';
// 出発地は 0 に固定。残り n-1 個の並べ方を全部試す。
export function bruteForceTSP(cities) {
const n = cities.length;
const rest = [];
for (let i = 1; i < n; i++) rest.push(i);
let best = Infinity;
let bestOrder = null;
let count = 0;
const perm = (arr, k) => {
if (k === arr.length) {
count++;
const order = [0, ...arr];
const len = tourLength(cities, order);
if (len < best) { best = len; bestOrder = order; }
return;
}
for (let i = k; i < arr.length; i++) {
[arr[k], arr[i]] = [arr[i], arr[k]];
perm(arr, k + 1);
[arr[k], arr[i]] = [arr[i], arr[k]];
}
};
perm(rest, 0);
return { best, bestOrder, count };
}
if (process.argv[1].endsWith('brute.mjs')) {
const n = Number(process.argv[2] || 8);
const cities = makeCities(n);
const t0 = performance.now();
const r = bruteForceTSP(cities);
const ms = performance.now() - t0;
console.log(`n=${n} 試した順路=${r.count} 最短=${r.best.toFixed(1)}km 時間=${ms.toFixed(1)}ms`);
console.log(' 最短順路:', r.bestOrder.map(i => cities[i].name).join(' -> '));
}
perm は「配列の要素を入れ替えて、戻す」という書き方です。 入れ替えたら必ず元に戻す。 戻し忘れると、途中から別の配列を並べ替えていることになって、静かに間違った答えが出ます。
まず小さいところから。
n=8 試した順路=5040 最短=2559.8km 時間=24.7ms
最短順路: A -> C -> D -> H -> B -> F -> E -> G
24.7ミリ秒。 8か所なら一瞬です。ここで油断します。私はここで油断しました。
そして12か所。
n=12 試した順路=39916800 最短=3148.7km 時間=62469.5ms
最短順路: A -> C -> D -> H -> K -> B -> L -> F -> J -> E -> G -> I
62.5秒。
同じ問題です。同じマシンです。都市が4つ増えただけで、24.7ミリ秒が62.5秒になりました。2500倍です。
答え合わせ 0.28ミリ秒。探すの 62.5秒。差は22万倍。
これが NP の核心です。 「答えを作るのは絶望的に大変だが、渡された答えを確かめるのは一瞬」。 この非対称が、これから話す全部の土台になります。
③ 用語を、この非対称で整理する
さっき見たものを、そのまま言葉に当てはめます。
| 言葉 | 意味 | さっきの実験でいうと |
|---|---|---|
| P | 答えを出すのが多項式時間 | 「A から J への最短経路」(後で出します。0.04ms) |
| NP | 渡された答えを確かめるのが多項式時間 | 「この順路は3200km以下か」の答え合わせ 0.28ms |
| NP困難 | NP のどの問題も、これに帰着できる | 「一番短い順路を出せ」(最適化そのもの) |
| NP完全 | NP に入っていて、かつ NP困難 | 「3200km以下の順路はあるか」(はい/いいえの形) |
| co-NP | 「無い」ことを短く確かめられる | 「3000km以下の順路は無い」の証明。短い証拠が知られていない |
ここでほぼ全員が誤解する2つ
誤解1: 「NP = 解けない問題」ではありません。
NP は「答え合わせが速い問題」の集まりです。解きやすさの話をしていません。 たとえば「1 + 1 は 2 か」も NP に入ります。答え合わせが一瞬だからです。
誤解2: 「NP」は Non-Polynomial(非多項式)の略ではありません。
正しくは Nondeterministic Polynomial time(非決定性多項式時間) です。 「もし全部の枝を同時に試せる機械があったら、多項式時間で解ける」という意味です。 Non-Polynomial だと思っていると、「P ⊆ NP」が矛盾に見えて、話が全部おかしくなります。
P ⊆ NP は、当たり前の話
多項式時間で解ける問題は、多項式時間で確かめられます。 なぜなら、答えを渡されても無視して、自分で解き直して比べればいいからです。解くのが速いなら、それでも速い。
P は NP の中にすっぽり入っている。
だから正しい問いは「P は NP か」ではなく、「NP は P より本当に広いのか」です。
NP困難と NP完全の違い
同じに見えて違います。 一言でいうと「NP に入っているかどうか」だけです。
- NP完全 = 硬い + NP の中にいる(答えを渡されれば確かめられる)
- NP困難 = 硬い + NP の中にいるとは限らない(答えを渡されても確かめるのが大変かもしれない)
「一番短い順路を出せ」は NP困難ですが、NP完全ではありません。 順路を1本渡されても、それが世界一短いことは、他を全部見ないと確かめられないからです。
「3200km以下の順路はあるか」というはい/いいえの形にすると、NP完全になります。渡された1本を足せば済むからです。
④ P = NP 問題 — 100万ドルの問い
ここまでを1行にすると、こうなります。
答え合わせが速いなら、解くのも速いはずか?
これが P = NP 問題です。 未解決です。
- P = NP なら、答え合わせが速い問題は全部、解くのも速い。私のシフト表も速く組める
- P ≠ NP なら、原理的に速い方法が存在しない問題がある。何年頑張っても見つからない
クレイ数学研究所のミレニアム懸賞問題の1つで、解けば100万ドルです。 1971年に問いとして立ってから、50年以上解かれていません。
大半の研究者は P ≠ NP だと考えています。 ただしそれも証明されていません。 「たぶん違う」の側に賭けている、というだけです。
もし P = NP だったら、困ったことになる
現代の暗号のかなりの部分は、「作るのは簡単、逆をたどるのは絶望的に大変」という非対称に乗っています。
- パスワードのハッシュ、公開鍵暗号、電子署名。どれも同じ形です
- もし P = NP なら、その「逆をたどるのは絶望的」という前提が崩れます
これは事実の記述です。 ここでは守る側として知っておく話だけを書きます。 どうやるかは書きませんし、この記事の範囲外です。パスワードを預かる側の実務は 速いハッシュは使わない — パスワード保存とbcrypt にあります。
つまり、P ≠ NP は「悔しい制限」であると同時に、いま安全にログインできている理由でもあります。
⑤ 手を動かす — 壁が立つところを実測する
「n が増えると急に無理になる」を、言葉ではなく表で見ます。
n=8 試した順路=5040 最短=2559.8km 時間=24.7ms
最短順路: A -> C -> D -> H -> B -> F -> E -> G
n=9 試した順路=40320 最短=3073.1km 時間=105.0ms
最短順路: A -> C -> D -> H -> B -> F -> E -> G -> I
n=10 試した順路=362880 最短=3090.9km 時間=510.0ms
最短順路: A -> C -> D -> H -> B -> F -> J -> E -> G -> I
n=11 試した順路=3628800 最短=3107.6km 時間=5599.5ms
最短順路: A -> I -> G -> E -> J -> F -> B -> K -> H -> D -> C
n=12 はさっき出しました。まとめます。
| n | 試した順路 | 時間 | 前の n の何倍か |
|---|---|---|---|
| 8 | 5,040 | 24.7ms | — |
| 9 | 40,320 | 105.0ms | 4.3倍 |
| 10 | 362,880 | 510.0ms | 4.9倍 |
| 11 | 3,628,800 | 5,599.5ms | 11.0倍 |
| 12 | 39,916,800 | 62,469.5ms | 11.2倍 |
n を1増やすたびに、時間がおよそ n 倍になります。 これが n!(階乗)の伸び方です。
「データが10倍になると100倍遅い」の O(n²) でも十分つらいのに、 ここでは「データが1件増えると10倍遅い」です。桁が違います。 O(n²) の話は データが10倍で100倍遅くなる — コンピュータ科学深掘り にあります。
n=15 を待つべきか、計算で出す
走らせません。 n=12 の実測から推定します。
// n=12 の実測値から、n を増やしたときの時間を推定する
const BASE_N = 12;
const BASE_MS = 62469.5;
function human(ms) {
const s = ms / 1000;
if (s < 60) return `${s.toFixed(1)}秒`;
if (s < 3600) return `${(s / 60).toFixed(1)}分`;
if (s < 86400) return `${(s / 3600).toFixed(1)}時間`;
if (s < 86400 * 365) return `${(s / 86400).toFixed(1)}日`;
return `${(s / 86400 / 365).toExponential(2)}年`;
}
let ms = BASE_MS;
console.log('n | 順路の通り数 (n-1)! | 推定時間');
console.log('--+---------------------+---------');
for (let n = BASE_N; n <= 20; n++) {
if (n > BASE_N) ms *= (n - 1);
let f = 1;
for (let i = 2; i <= n - 1; i++) f *= i;
console.log(`${String(n).padStart(2)} | ${f.toExponential(3).padStart(19)} | ${human(ms)}`);
}
n | 順路の通り数 (n-1)! | 推定時間
--+---------------------+---------
12 | 3.992e+7 | 1.0分
13 | 4.790e+8 | 12.5分
14 | 6.227e+9 | 2.7時間
15 | 8.718e+10 | 1.6日
16 | 1.308e+12 | 23.7日
17 | 2.092e+13 | 1.04e+0年
18 | 3.557e+14 | 1.77e+1年
19 | 6.402e+15 | 3.18e+2年
20 | 1.216e+17 | 6.04e+3年
配送先が15か所で1.6日。20か所で6000年。
ここで「コードを60倍速くする」がどれだけ無力かが分かります。 60倍速くしても、20か所は100年です。しかも、都市を2つ足せば元に戻ります。
私が2日かけてやったのは、これでした。
📷 スクリーンショット②: node estimate.mjs の表。n=20 で6000年になっているところ。
⑥ 有名な NP完全問題を、実際に小さく解いてみる
教科書の名前で覚えても使えません。 全部「自分のアプリで出てきそうな形」に置き換えます。
| 教科書の名前 | 自分のアプリでの顔 |
|---|---|
| 巡回セールスマン | 配送ルート・営業の訪問順・写真の並べ替え |
| ナップサック | 荷物の詰め方・予算内での機能選び・広告枠の埋め方 |
| ハミルトン閉路 | 全店舗を1回ずつ回って戻る巡回計画 |
| 最長経路 | 工程表で一番長くかかる道(クリティカルパス) |
| グラフ彩色 | 時間割・会議室の割り当て・レジスタ割り当て |
| 集合被覆 | 最少の人数で全シフトを埋める |
6-1. ナップサック — 荷物の詰め方
上限100kgの箱に、22個の荷物から選んで詰めます。価値の合計を最大に。
import { makeRng } from './cities.mjs';
const rnd = makeRng(7);
const N = 22;
const items = [];
for (let i = 0; i < N; i++) {
items.push({
name: `荷物${i + 1}`,
weight: 1 + Math.floor(rnd() * 30),
value: 10 + Math.floor(rnd() * 200),
});
}
const CAP = 100;
// 総当たり: 2^22 通りの「入れる/入れない」を全部試す
function brute(items, cap) {
const n = items.length;
let best = 0, bestMask = 0, checked = 0;
for (let mask = 0; mask < (1 << n); mask++) {
let w = 0, v = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) { w += items[i].weight; v += items[i].value; }
}
checked++;
if (w <= cap && v > best) { best = v; bestMask = mask; }
}
return { best, bestMask, checked };
}
// 貪欲: 価値/重さ が高いものから詰める
function greedy(items, cap) {
const sorted = [...items].sort((a, b) => b.value / b.weight - a.value / a.weight);
let w = 0, v = 0; const picked = [];
for (const it of sorted) {
if (w + it.weight <= cap) { w += it.weight; v += it.value; picked.push(it.name); }
}
return { value: v, weight: w, picked };
}
console.log(`荷物 ${N}個 / 上限 ${CAP}kg`);
console.log(items.map(i => `${i.name}:${i.weight}kg,${i.value}点`).join(' '));
let t0 = performance.now();
const g = greedy(items, CAP);
const gms = performance.now() - t0;
console.log(`貪欲: 価値=${g.value} 重さ=${g.weight}kg 時間=${gms.toFixed(3)}ms`);
t0 = performance.now();
const b = brute(items, CAP);
const bms = performance.now() - t0;
console.log(`総当たり: 価値=${b.best} 試した組合せ=${b.checked} 時間=${bms.toFixed(1)}ms`);
console.log(`貪欲は最適の ${(g.value / b.best * 100).toFixed(1)}%`);
荷物 22個 / 上限 100kg
荷物1:8kg,192点 荷物2:19kg,195点 荷物3:2kg,181点 荷物4:11kg,20点 荷物5:3kg,206点 荷物6:30kg,116点 荷物7:14kg,119点 荷物8:19kg,165点 荷物9:24kg,93点 荷物10:15kg,180点 荷物11:11kg,106点 荷物12:3kg,159点 荷物13:26kg,81点 荷物14:6kg,206点 荷物15:4kg,100点 荷物16:14kg,31点 荷物17:4kg,134点 荷物18:24kg,26点 荷物19:19kg,195点 荷物20:8kg,128点 荷物21:11kg,72点 荷物22:16kg,152点
貪欲: 価値=1876 重さ=91kg 時間=0.412ms
総当たり: 価値=1939 試した組合せ=4194304 時間=791.7ms
貪欲は最適の 96.8%
0.4ミリ秒で、最適の96.8%が出ました。 総当たりは1900倍の時間をかけて、3.2%だけ良い答えを出しています。
貪欲がやっているのは「価値÷重さ が高い順に詰める」だけです。5行です。
これは近似アルゴリズムではありません。ヒューリスティックです。 たまたま96.8%だっただけで、この貪欲法は「最悪でも何%」という保証を持ちません。 作為的な荷物を並べれば、いくらでも悪くできます。
1 << n は n が31以上で壊れます(1 << 31 は負の数になります)。 JavaScript のビット演算は32bit整数で動くためです。 荷物が30個を超えたら、この総当たりはそもそも書けません。
6-2. ハミルトン閉路とオイラー路 — 似ているのに片方だけ簡単
この対比が、この記事でいちばん面白いところです。
- オイラー路: 全部の「辺」を1回ずつ通る道はあるか
- ハミルトン閉路: 全部の「頂点」を1回ずつ通って戻る道はあるか
言い方はほとんど同じです。 難しさは天と地です。
まずグラフを作ります。最短経路と最長経路も、あとで同じファイルから使います。
// 会議室・配送先などを模した無向グラフ
export const V = ['A','B','C','D','E','F','G','H','I','J'];
export const EDGES = [
['A','B',4],['A','C',2],['B','C',5],['B','D',10],['C','E',3],
['E','D',4],['D','F',11],['E','F',7],['F','G',2],['G','H',6],
['H','I',3],['I','J',5],['J','G',8],['E','H',9],['A','J',12],
];
export function adjacency() {
const adj = new Map(V.map(v => [v, []]));
for (const [a, b, w] of EDGES) {
adj.get(a).push([b, w]);
adj.get(b).push([a, w]);
}
return adj;
}
// --- 最短経路(ダイクストラ): これは P ---
export function dijkstra(start, goal) {
const adj = adjacency();
const distMap = new Map(V.map(v => [v, Infinity]));
const prev = new Map();
distMap.set(start, 0);
const unvisited = new Set(V);
while (unvisited.size) {
let u = null, best = Infinity;
for (const v of unvisited) if (distMap.get(v) < best) { best = distMap.get(v); u = v; }
if (u === null) break;
unvisited.delete(u);
for (const [v, w] of adj.get(u)) {
if (distMap.get(u) + w < distMap.get(v)) {
distMap.set(v, distMap.get(u) + w);
prev.set(v, u);
}
}
}
const path = [];
let cur = goal;
while (cur) { path.unshift(cur); cur = prev.get(cur); }
return { length: distMap.get(goal), path };
}
// --- 最長経路(同じ頂点を2回通らない): これは NP困難 ---
export function longestPath(start, goal) {
const adj = adjacency();
let best = -1, bestPath = null, visitedCount = 0;
const seen = new Set([start]);
const path = [start];
const go = (u, total) => {
visitedCount++;
if (u === goal) {
if (total > best) { best = total; bestPath = [...path]; }
return;
}
for (const [v, w] of adj.get(u)) {
if (seen.has(v)) continue;
seen.add(v); path.push(v);
go(v, total + w);
seen.delete(v); path.pop();
}
};
go(start, 0);
return { length: best, path: bestPath, visitedCount };
}
if (process.argv[1].endsWith('graph.mjs')) {
let t0 = performance.now();
const s = dijkstra('A', 'J');
const sms = performance.now() - t0;
console.log(`最短 A->J : ${s.length} 経路 ${s.path.join('->')} 時間 ${sms.toFixed(3)}ms`);
t0 = performance.now();
const l = longestPath('A', 'J');
const lms = performance.now() - t0;
console.log(`最長 A->J : ${l.length} 経路 ${l.path.join('->')} 時間 ${lms.toFixed(3)}ms 調べた部分経路 ${l.visitedCount}`);
}
オイラー路とハミルトン閉路を比べます。
import { V, EDGES, adjacency } from './graph.mjs';
// --- オイラー路(全部の「辺」を1回ずつ): P。次数を数えるだけ ---
function eulerCheck() {
const deg = new Map(V.map(v => [v, 0]));
for (const [a, b] of EDGES) { deg.set(a, deg.get(a) + 1); deg.set(b, deg.get(b) + 1); }
const odd = V.filter(v => deg.get(v) % 2 === 1);
return { deg, odd };
}
// --- ハミルトン閉路(全部の「頂点」を1回ずつ): NP完全。総当たり ---
function hamiltonCycle() {
const adj = adjacency();
const n = V.length;
const seen = new Set([V[0]]);
const path = [V[0]];
let steps = 0, found = null;
const go = (u) => {
steps++;
if (found) return;
if (path.length === n) {
if (adj.get(u).some(([v]) => v === V[0])) found = [...path, V[0]];
return;
}
for (const [v] of adj.get(u)) {
if (seen.has(v)) continue;
seen.add(v); path.push(v);
go(v);
seen.delete(v); path.pop();
if (found) return;
}
};
go(V[0]);
return { found, steps };
}
let t0 = performance.now();
const e = eulerCheck();
const ems = performance.now() - t0;
console.log('各頂点の次数:', V.map(v => `${v}:${e.deg.get(v)}`).join(' '));
console.log('次数が奇数の頂点:', e.odd.length ? e.odd.join(',') : 'なし');
console.log('オイラー路はあるか:', e.odd.length === 0 || e.odd.length === 2);
console.log('判定にかかった時間:', ems.toFixed(4), 'ms');
t0 = performance.now();
const h = hamiltonCycle();
const hms = performance.now() - t0;
console.log('---');
console.log('ハミルトン閉路:', h.found ? h.found.join('->') : '無い');
console.log('試した部分経路:', h.steps);
console.log('判定にかかった時間:', hms.toFixed(4), 'ms');
各頂点の次数: A:3 B:3 C:3 D:3 E:4 F:3 G:3 H:3 I:2 J:3
次数が奇数の頂点: A,B,C,D,F,G,H,J
オイラー路はあるか: false
判定にかかった時間: 0.1494 ms
---
ハミルトン閉路: A->B->C->E->D->F->G->H->I->J->A
試した部分経路: 10
判定にかかった時間: 0.4707 ms
オイラー路の判定に、探索が1つも入っていないことに注目してください。
「次数が奇数の頂点が 0個 か 2個 か」を数えただけです。 これは頂点の数に正比例します。完全に P です。 (オイラーが1736年に示した結果です。280年以上前に、この問題は終わっています。)
ハミルトン閉路のほうは、探索するしか方法が知られていません。 このグラフでは10ステップで見つかりましたが、それは運が良かっただけです。次でそれを見ます。
6-3. 「無い」を確かめるのは、桁違いに大変
ここが co-NP の話です。「答えが無い」ケースを見ると、本当の顔が出ます。
左グループと右グループの人がいて、左右の間にだけ辺があるグラフを考えます(完全2部グラフ)。 左右の人数が違うと、ハミルトン閉路は絶対に存在しません。 左右を交互にしか進めないからです。
// 左グループ L 人、右グループ R 人。左と右の間にだけ辺がある「完全2部グラフ」
function bipartite(L, R) {
const n = L + R;
const adj = Array.from({ length: n }, () => []);
for (let i = 0; i < L; i++)
for (let j = L; j < n; j++) { adj[i].push(j); adj[j].push(i); }
return adj;
}
function hamilton(adj) {
const n = adj.length;
const seen = new Array(n).fill(false);
let steps = 0, found = null;
const path = [0];
const go = (u) => {
steps++;
if (found) return;
if (path.length === n) { if (adj[u].includes(0)) found = [...path, 0]; return; }
for (const v of adj[u]) {
if (seen[v]) continue;
seen[v] = true; path.push(v);
go(v);
seen[v] = false; path.pop();
if (found) return;
}
};
seen[0] = true; go(0);
return { found, steps };
}
for (const [L, R] of [[5, 5], [5, 6], [6, 6], [6, 7], [7, 7], [7, 8]]) {
const adj = bipartite(L, R);
const t0 = performance.now();
const r = hamilton(adj);
const ms = performance.now() - t0;
console.log(`左${L}人 右${R}人 (頂点${L + R}): ${r.found ? 'あった' : '無い'} 試した部分経路=${r.steps.toLocaleString('en-US')} 時間=${ms.toFixed(1)}ms`);
}
左5人 右5人 (頂点10): あった 試した部分経路=10 時間=0.2ms
左5人 右6人 (頂点11): 無い 試した部分経路=39,391 時間=7.3ms
左6人 右6人 (頂点12): あった 試した部分経路=12 時間=0.1ms
左6人 右7人 (頂点13): 無い 試した部分経路=1,378,693 時間=63.8ms
左7人 右7人 (頂点14): あった 試した部分経路=14 時間=0.0ms
左7人 右8人 (頂点15): 無い 試した部分経路=66,177,273 時間=3477.9ms
この表を、上から読んでください。
- 「ある」のときは、頂点14個でも14ステップで終わっています
- 「無い」のときは、頂点15個で6600万ステップかかっています
「ある」の証拠は1本の経路。「無い」の証拠は、全部を試したという事実そのもの。
これが NP と co-NP の違いです。 「ある」は短い証拠で確かめられます。「無い」を短く確かめる方法は、知られていません。
実務の言葉に直すと、こうです。
「この条件でシフトは組めます」より、「この条件ではシフトは組めません」のほうが、機械には遥かに重い。
利用者に「組めません」と返すのが遅いアプリは、たいていこれが原因です。
📷 スクリーンショット③: node hamilton-no.mjs の出力。14ステップと6600万ステップが並んでいるところ。
6-4. 最短経路は簡単、最長経路は NP困難
同じグラフで両方やります。
最短 A->J : 12 経路 A->J 時間 0.800ms
最長 A->J : 58 経路 A->C->B->D->F->E->H->G->J 時間 0.425ms 調べた部分経路 110
10頂点では差が出ません。頂点を増やします。
import { makeRng } from './cities.mjs';
// n個の頂点。各ペアを確率pで繋ぐ「密なグラフ」
function makeGraph(n, p = 0.5, seed = 3) {
const rnd = makeRng(seed);
const adj = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (rnd() < p) {
const w = 1 + Math.floor(rnd() * 20);
adj[i].push([j, w]); adj[j].push([i, w]);
}
}
}
// 全部繋がるように一本の道を保証
for (let i = 0; i + 1 < n; i++) {
if (!adj[i].some(([v]) => v === i + 1)) {
adj[i].push([i + 1, 7]); adj[i + 1].push([i, 7]);
}
}
return adj;
}
function dijkstra(adj, s, g) {
const n = adj.length;
const d = new Array(n).fill(Infinity); d[s] = 0;
const done = new Array(n).fill(false);
for (let k = 0; k < n; k++) {
let u = -1, b = Infinity;
for (let i = 0; i < n; i++) if (!done[i] && d[i] < b) { b = d[i]; u = i; }
if (u < 0) break;
done[u] = true;
for (const [v, w] of adj[u]) if (d[u] + w < d[v]) d[v] = d[u] + w;
}
return d[g];
}
function longest(adj, s, g) {
const n = adj.length;
const seen = new Array(n).fill(false);
let best = -1, steps = 0;
const go = (u, total) => {
steps++;
if (u === g) { if (total > best) best = total; return; }
for (const [v, w] of adj[u]) {
if (seen[v]) continue;
seen[v] = true; go(v, total + w); seen[v] = false;
}
};
seen[s] = true; go(s, 0);
return { best, steps };
}
for (const n of [10, 12, 14, 16]) {
const adj = makeGraph(n);
let t0 = performance.now();
const sd = dijkstra(adj, 0, n - 1);
const sms = performance.now() - t0;
t0 = performance.now();
const lg = longest(adj, 0, n - 1);
const lms = performance.now() - t0;
console.log(`n=${String(n).padStart(2)} 最短=${String(sd).padStart(3)} (${sms.toFixed(3)}ms) 最長=${String(lg.best).padStart(4)} (${lms.toFixed(1)}ms, 部分経路 ${lg.steps.toLocaleString('en-US')})`);
}
最後の n=16 で17秒ほど固まります。 待ってください。
n=10 最短= 12 (0.169ms) 最長= 106 (5.3ms, 部分経路 5,932)
n=12 最短= 6 (0.040ms) 最長= 137 (9.2ms, 部分経路 122,110)
n=14 最短= 8 (0.041ms) 最長= 180 (50.0ms, 部分経路 1,339,438)
n=16 最短= 16 (0.036ms) 最長= 221 (17222.4ms, 部分経路 277,956,188)
同じグラフです。同じ2つの頂点の間です。
- 最短: 0.036ミリ秒
- 最長: 17.2秒(2億7800万通りの部分経路)
47万倍の差です。ちなみに n=18 は6分待っても返ってきませんでした。
「最短が解けるなら最長も解けるはず」は、直感としては自然ですが、間違いです。 ダイクストラは「いま一番近い所は、もう確定していい」という性質に乗っています。 最長にはその性質がありません。 「いま一番遠い所」を確定しても、遠回りすればもっと伸びるからです。
工程表のクリティカルパスが重い理由も、ここにあることがあります。 ただし工程表のように閉路のないグラフに限れば、最長経路も P で解けます。 閉路が1つ入った瞬間に NP困難になります。
6-5. グラフ彩色 — 会議室の割り当て
同じ人が出る会議は、同じ時間帯に置けません。 最少で何コマ必要か。
// 会議。同じ人が出る会議は同じ時間帯に置けない = 辺で結ぶ
const MEETINGS = ['企画', '設計', '定例', '採用', '営業', '経理', '振返り', '勉強会'];
const CONFLICT = [
['企画','設計'],['企画','定例'],['企画','営業'],['設計','定例'],['設計','振返り'],
['定例','採用'],['定例','振返り'],['採用','営業'],['営業','経理'],['経理','勉強会'],
['振返り','勉強会'],['採用','勉強会'],['企画','経理'],
];
const adj = new Map(MEETINGS.map(m => [m, []]));
for (const [a, b] of CONFLICT) { adj.get(a).push(b); adj.get(b).push(a); }
// k色で塗れるか(総当たり)
function colorable(k) {
const color = new Map();
let steps = 0;
const go = (i) => {
steps++;
if (i === MEETINGS.length) return true;
const m = MEETINGS[i];
for (let c = 0; c < k; c++) {
if (adj.get(m).some(n => color.get(n) === c)) continue;
color.set(m, c);
if (go(i + 1)) return true;
color.delete(m);
}
return false;
};
const ok = go(0);
return { ok, steps, color: ok ? new Map(color) : null };
}
for (let k = 1; k <= 4; k++) {
const t0 = performance.now();
const r = colorable(k);
const ms = performance.now() - t0;
console.log(`${k}コマで組めるか: ${r.ok ? 'はい' : 'いいえ'} 試した割当=${r.steps} 時間=${ms.toFixed(3)}ms`);
if (r.ok) {
const slots = {};
for (const [m, c] of r.color) (slots[c] ||= []).push(m);
for (const c of Object.keys(slots).sort()) console.log(` ${Number(c) + 1}コマ目: ${slots[c].join(', ')}`);
break;
}
}
1コマで組めるか: いいえ 試した割当=2 時間=0.137ms
2コマで組めるか: いいえ 試した割当=5 時間=0.047ms
3コマで組めるか: はい 試した割当=9 時間=0.023ms
1コマ目: 企画, 採用, 振返り
2コマ目: 設計, 営業, 勉強会
3コマ目: 定例, 経理
会議8本なら一瞬で組めます。 これが「問題を小さくすれば最適解が出る」という話の実物です。
なお「2色で塗れるか」だけは P で判定できます。 2部グラフかどうかを見るだけです。 3色以上になった瞬間に NP完全になります。 「1つ増えただけ」で世界が変わる、代表的な例です。
そして、この彩色こそが私のシフト表でした。 「同時に置けないものを、別の枠に分ける」は全部この形です。 コンパイラが変数をレジスタに割り当てるのも、同じ問題です。
⑦ だから現場ではどうするか
逃げ道は4つです。 全部、巡回セールスマンで実装して比べます。
逃げ道1と2: 貪欲法と 2-opt
import { makeCities, tourLength, makeRng } from './cities.mjs';
// ① 貪欲(最近傍): いまいる場所から一番近い未訪問へ
export function greedyTour(cities) {
const n = cities.length;
const seen = new Array(n).fill(false);
const order = [0]; seen[0] = true;
for (let k = 1; k < n; k++) {
const cur = cities[order[order.length - 1]];
let best = -1, bd = Infinity;
for (let i = 0; i < n; i++) {
if (seen[i]) continue;
const d = Math.hypot(cur.x - cities[i].x, cur.y - cities[i].y);
if (d < bd) { bd = d; best = i; }
}
seen[best] = true; order.push(best);
}
return order;
}
// ② 2-opt: 交差している2本の辺をほどく、を改善が無くなるまで繰り返す
export function twoOpt(cities, order, log = false) {
let cur = [...order];
let curLen = tourLength(cities, cur);
let improved = true, round = 0;
while (improved) {
improved = false;
for (let i = 1; i < cur.length - 1; i++) {
for (let j = i + 1; j < cur.length; j++) {
const next = [...cur.slice(0, i), ...cur.slice(i, j + 1).reverse(), ...cur.slice(j + 1)];
const len = tourLength(cities, next);
if (len < curLen - 1e-9) { cur = next; curLen = len; improved = true; }
}
}
round++;
if (log) console.log(` ${round}周目: ${curLen.toFixed(1)}km`);
}
return { order: cur, length: curLen };
}
// ③ 時間で打ち切る: ランダムな出発点から2-optを回し、時間切れまで一番いいものを持つ
export function timeboxed(cities, ms) {
const rnd = makeRng(99);
const t0 = performance.now();
let best = null, bestLen = Infinity, tries = 0;
while (performance.now() - t0 < ms) {
const order = [...Array(cities.length).keys()];
for (let i = order.length - 1; i > 0; i--) {
const j = Math.floor(rnd() * (i + 1));
[order[i], order[j]] = [order[j], order[i]];
}
const r = twoOpt(cities, order);
tries++;
if (r.length < bestLen) { bestLen = r.length; best = r.order; }
}
return { order: best, length: bestLen, tries, ms: performance.now() - t0 };
}
if (process.argv[1].endsWith('escapes.mjs')) {
const cities = makeCities(12);
const OPT = 3148.7;
console.log(`都市12。総当たりで出した最適 = ${OPT}km(62.5秒かかった)`);
let t0 = performance.now();
const g = greedyTour(cities);
const gLen = tourLength(cities, g);
const gms = performance.now() - t0;
console.log(`貪欲 : ${gLen.toFixed(1)}km 最適比 ${(gLen / OPT * 100).toFixed(1)}% ${gms.toFixed(3)}ms`);
console.log(` 経路 ${g.map(i => cities[i].name).join('->')}`);
t0 = performance.now();
console.log('2-opt(貪欲の結果から改善):');
const o = twoOpt(cities, g, true);
const oms = performance.now() - t0;
console.log(`2-opt : ${o.length.toFixed(1)}km 最適比 ${(o.length / OPT * 100).toFixed(1)}% ${oms.toFixed(1)}ms`);
console.log(` 経路 ${o.order.map(i => cities[i].name).join('->')}`);
const tb = timeboxed(cities, 5000);
console.log(`5秒打切り: ${tb.length.toFixed(1)}km 最適比 ${(tb.length / OPT * 100).toFixed(1)}% ${tb.ms.toFixed(0)}ms 試した出発点 ${tb.tries}`);
}
最後の「5秒打切り」で、ちょうど5秒止まります。 固まったのではありません。
都市12。総当たりで出した最適 = 3148.7km(62.5秒かかった)
貪欲 : 3288.3km 最適比 104.4% 0.264ms
経路 A->C->D->K->B->L->H->F->J->E->G->I
2-opt(貪欲の結果から改善):
1周目: 3148.7km
2周目: 3148.7km
2-opt : 3148.7km 最適比 100.0% 0.7ms
経路 A->C->D->H->K->B->L->F->J->E->G->I
5秒打切り: 3148.7km 最適比 100.0% 5002ms 試した出発点 35633
ここを、よく見てください。
総当たりが62.5秒かけて出した答えと、まったく同じものを、2-opt は0.7ミリ秒で出しました。
約9万倍です。
2-opt がやっていることは、たった1つです。「順路の一部をひっくり返してみて、短くなったら採用」。 地図に描くと、交差している2本の道をほどく動きになります。
貪欲と2-optの結果の違いは、1文字分です。
貪欲 : A->C->D->K->B->L->H->F->J->E->G->I
2-opt : A->C->D->H->K->B->L->F->J->E->G->I
H の位置が動いただけです。それで139km縮んでいます。 貪欲は「近いから」で H を後回しにして、あとから取りに戻っていました。 2-opt はその戻りをほどきました。
2-opt にも「最適の◯倍以内」という保証はありません。 ヒューリスティックです。 たまたま最適に一致しただけで、別の地図では 2〜5% 悪いところで止まります。 「2周目で改善が0だった」は「最適だ」という意味ではなく、「この動かし方では、もう縮まない」という意味だけです。
逃げ道3: 問題を小さくする
さっき見たとおり、n=10 なら総当たりで0.5秒です。 つまり問題を10か所に切れれば、最適解が出せます。
- 配送先200件を、エリアで20件×10グループに分ける
- シフト表を、週ごと・チームごとに切る
- 会議室の割り当てを、フロアごとに分ける
「制約を足して候補を減らす」のも、同じ効果があります。 私のシフト表は、「連勤は3日まで」を最初に判定へ入れただけで、探す枝が桁で減りました。 制約は敵ではなく、味方です。
逃げ道4: 時間で打ち切る
「5秒考えて、その時点で一番いいものを返す」。これで実務はほとんど足ります。
上の実行では、5秒で35,633回ぶんの出発点を試して、その中の最良を返しました。
これが実装としていちばん強い理由は、「終わらない」が構造的に起きなくなるからです。 返答時間が上限で保証されます。 ユーザーは待たされません。
大きい問題で試す
総当たりが絶対に無理な規模でやってみます。
import { makeCities, tourLength } from './cities.mjs';
import { greedyTour, twoOpt } from './escapes.mjs';
const cities = makeCities(200, 1234);
console.log('配送先 200件。総当たりの通り数 = 199! ≈ 10^372(宇宙が終わっても終わらない)');
let t0 = performance.now();
const g = greedyTour(cities);
const gLen = tourLength(cities, g);
const gms = performance.now() - t0;
console.log(`貪欲 : ${gLen.toFixed(0)}km ${gms.toFixed(1)}ms`);
t0 = performance.now();
const o = twoOpt(cities, g);
const oms = performance.now() - t0;
console.log(`2-opt : ${o.length.toFixed(0)}km ${oms.toFixed(0)}ms 貪欲比 ${(o.length / gLen * 100).toFixed(1)}%`);
配送先 200件。総当たりの通り数 = 199! ≈ 10^372(宇宙が終わっても終わらない)
貪欲 : 14244km 4.3ms
2-opt : 11210km 1275ms 貪欲比 78.7%
200件です。総当たりは、宇宙の年齢を何度使っても終わりません。 それでも 1.3秒で、貪欲より21%短い順路が出ています。
最適解が何kmなのかは、私には分かりません。 出せないからです。 でも実務では、それで困りません。 昨日より短ければ、ガソリン代は減ります。
4つを並べる
| やり方 | 最適解か | 所要時間(12件) | 200件で使えるか | 実装の手間 |
|---|---|---|---|---|
| 総当たり | 必ず最適 | 62,469ms | 不可能 | 小(20行) |
| 貪欲(最近傍) | 保証なし(今回104.4%) | 0.26ms | 使える(4.3ms) | 小(15行) |
| 2-opt | 保証なし(今回100.0%) | 0.7ms | 使える(1,275ms) | 中(20行) |
| 問題を小さくする | 分割の中では最適 | 分割次第 | 分け方の設計が要る | 大(設計そのもの) |
| 時間で打ち切る | 保証なし(今回100.0%) | 必ず5,000ms | 使える(上限が保証される) | 小(ループを包むだけ) |
表の一番右の列が、実務ではいちばん効きます。 「問題を小さくする」は理屈としては最強ですが、分け方を間違えると答えが大きく悪化します。 配送先をエリアで割ると、エリアの境目をまたぐ移動が丸ごと無駄になります。
私が最初に取るべきだったのは、一番下の行でした。 やることは、既存のループを while (performance.now() - t0 < 5000) で包むだけです。
⑧ 判断のしかた — 3日溶かす前に確認する
自分の問題が NP完全かどうかを、どうやって疑うか。 順番はこうです。
手順1: 「全部の組み合わせを試している」形になっていないか
コードにこの形が出たら、いったん手を止めます。
// 危険信号1: 順列を作っている
for (const order of allPermutations(items)) { /* ... */ }
// 危険信号2: 部分集合を全部作っている
for (let mask = 0; mask < (1 << n); mask++) { /* ... */ }
// 危険信号3: 「入れる/入れない」で再帰が2股に分かれている
const go = (i) => { go(i + 1); pick(i); go(i + 1); unpick(i); };
n! か 2ⁿ が出ていたら、まず疑ってください。
手順2: 既知の NP完全問題に似ていないか
言い換えてみます。 自分の問題を、次の言葉に置き換えられるか。
| 自分の問題がこう言えたら | これに似ている |
|---|---|
| 「全部を1回ずつ、順番に回る」 | 巡回セールスマン / ハミルトン閉路 |
| 「上限の中で、選んで最大にする」 | ナップサック |
| 「同時に置けないものを、最少の枠に分ける」 | グラフ彩色 |
| 「これらの条件を全部同時に満たす組み合わせはあるか」 | 充足可能性(SAT) |
| 「最少の◯◯で全部をカバーする」 | 集合被覆 |
完全に一致していなくてかまいません。 「似ている」だけで、警戒する理由になります。 似た問題に速い解法が50年見つかっていないなら、自分が今日見つける確率は低いからです。
手順3: n がいくつまで来るかを、先に確認する
これを飛ばして最適化に入ってはいけません。
| 実際の n | 判断 |
|---|---|
| 10以下で固定 | 総当たりでいい。 悩む時間のほうが高い |
| 20くらいまで | 総当たり + 枝刈り、または動的計画法を検討 |
| 数百〜 | 最初から近似・ヒューリスティックで設計する |
| 上限が読めない | 必ず時間で打ち切る。 上限のない探索を本番に出さない |
「速いアルゴリズムを探して3日溶かす」前に、ここを確認します。 私は手順3をやらずに、手順ゼロ(コードの最適化)から入りました。 それが3日の中身です。
手順4: 「最適」が本当に要るのかを、利用者に確認する
これがいちばん効きます。 次の章に書きます。
⑨ 現実的な結論 — NP完全は敗北ではない
NP完全だと分かった瞬間に、できることが増えます。
| 分かる前 | 分かった後 |
|---|---|
| 「もっと速く書けるはずだ」と探し続ける | 探すのをやめる根拠ができる |
| 「終わらないのは自分のせいだ」 | 問題の性質だと説明できる |
| 完璧な答えを目指してリリースできない | どこを諦めるかを、選んで決める |
| n が増えたときの挙動が読めない | n=10 で切る、5秒で切る、と設計できる |
「速い方法を探す」から「諦め方を選ぶ」への切り替えは、後退ではありません。設計です。
そして、もっと大事なことがあります。
利用者は、最適解を求めていないことが多い。
私のシフト表の件で、最後にこう報告しました。
「完璧な組み方は出せませんでした。だいたい良い表が3秒で出るところまでです」
返ってきたのは、これでした。
「え、3秒で出るなら十分ですけど。いまは手で2時間かけてます」
最適解を求めていたのは、私だけでした。
- 「そこそこ良いシフト表が3秒」 は、「完璧なシフト表が3日後」 より、ほぼ常に嬉しい
- そして「完璧なシフト表が永遠に出ない」 よりは、無限に嬉しい
要件に「最適」と書いてあったら、それが本当に「最適」なのかを1回聞いてください。 たいていは「いまより良ければいい」です。 そこを確認するのに、5分もかかりません。
3日の最初の5分でそれをやっていれば、この記事は書けませんでした。
つまずいたところ
1. 「一周」を測っていなかった
tourLength の % を書き忘れて、最後の都市から出発地に戻る辺を数えていませんでした。 症状は「答えは出るが、明らかに変な順路が最短になる」。エラーは出ません。
気づいた方法: 手で計算できる3都市で試したら、合計が合いませんでした。 こういう関数は、必ず「手で検算できる最小サイズ」で1回確かめます。
2. perm で入れ替えたまま戻し忘れた
[arr[k], arr[i]] = [arr[i], arr[k]];
perm(arr, k + 1);
// ここで戻していなかった
症状は「試した順路の数は 5040 で正しいのに、同じ順路が何度も出てくる」。 カウントは合うので、余計に気づきにくい。 count が合っていても安心できません。
3. n=13 を「ちょっと待てば終わる」と思って走らせた
12.5分です。 その間 VM が張り付いて、SSH の反応も鈍くなりました。
走らせる前に、必ず推定を出します。 estimate.mjs を先に書いたのは、これで一度やられたからです。 止めるときは Ctrl + C です。
4. ナップサックの総当たりが、荷物32個で無言で壊れた
for (let mask = 0; mask < (1 << n); mask++)
JavaScript のビット演算は32bit整数で動きます。 1 << 32 は 1 に戻ります。 つまりループが即座に終わって、「価値0が最適です」と平然と返ってきます。
エラーになりません。静かに嘘をつきます。 2 ** n を使うか、そもそも n が30を超えたら総当たりを選ばないことです。
5. 「NP完全だから動的計画法は使えない」と思い込んだ
間違いです。 ナップサックは NP完全ですが、動的計画法で O(n × 上限) で解けます。
「上限」が式に入っているのが肝です。 上限が100なら速い。上限が10億なら遅い。 入力の桁数に対しては指数時間なので、NP完全であることと矛盾しません(擬多項式時間といいます)。
実務では、これが大きな抜け道になります。 重さが整数で、上限が現実的な大きさなら、最適解が普通に出ます。
6. 貪欲法を「近似アルゴリズム」と呼んでしまった
別物でした。
- 近似アルゴリズム: 「最適の2倍以内」のような保証がある
- ヒューリスティック: 保証はない。 たいてい良い、というだけ
今回の貪欲は104.4%でしたが、それは実測値であって、保証ではありません。 記事や設計書に「最適の96%出ます」と書くときは、実測なのか保証なのかを必ず区別します。 (巡回セールスマンには「最適の1.5倍以内」を保証する手順もありますが、それは別の回に回します)
7. 2-opt が終わらないことがあった
改善判定を if (len < curLen) と書いたら、小数の誤差で「0.0000001km 改善した」が延々と続きました。
if (len < curLen - 1e-9) { /* 採用 */ }
小数の比較には、必ず余裕(イプシロン)を入れます。 小数がなぜぴったりにならないかは 0.1+0.2が0.3にならない — コンピュータ科学深掘り にあります。
8. 「NP完全」と「解けない」を混ぜて説明してしまった
チームに説明したとき、「これは解けない問題です」と言いました。 正しくありません。
解けます。 総当たりで、いつか必ず答えが出ます。「現実的な時間で解ける方法が知られていない」だけです。
「解けない問題」は別にあります(停止性問題のように、どんな手順を使っても原理的に判定できないもの)。 混ぜると、相手に「じゃあ諦めるしかないんですね」と伝わってしまいます。 正しくは「最適は諦めますが、十分良い答えは3秒で出せます」です。
後片づけ
作ったものを全部消します。
big.mjs brute.mjs cities.mjs coloring.mjs escapes.mjs estimate.mjs euler-hamilton.mjs graph.mjs hamilton-no.mjs knapsack.mjs scale.mjs verify.mjs
中身を確認してから消します。
search
rm -rf は戻せません。 パスを打つ前に、必ず ls で中身を確認してください。 rm の挙動は rmで消したものは戻らない — Linux深掘り にあります。
~/cslab ごと消したい場合は、こちらです。
まとめ — 理解できたこと
- この記事の全部は、1つの非対称に乗っている。 巡回セールスマンの答え合わせ 0.28ms、探索 62.5秒。22万倍
- NP は「解けない」ではない。「答えを渡されたら、速く確かめられる」という意味
- NP は
Non-Polynomialの略ではない。Nondeterministic Polynomial timeの略 - P ⊆ NP。 速く解けるなら、渡された答えを無視して解き直せばいいので、確かめるのも速い
- NP困難と NP完全の違いは「NP に入っているか」だけ。 「一番短い順路を出せ」は NP困難、「3200km以下はあるか」は NP完全
- P = NP は未解決で、100万ドルがかかっている。 大半の研究者は P ≠ NP 側だと考えている
- もし P = NP なら、現代の暗号の前提が崩れる。 つまり P ≠ NP は、いま安全にログインできている理由でもある
- 実測した壁: n=8 で 24.7ms、n=12 で 62.5秒、n=15 の推定が1.6日、n=20 が6000年
- 60倍速くしても、n が2増えれば元通り。 私が2日かけたコード最適化は、そこで無力になった
- オイラー路(辺を1回ずつ)は次数を数えるだけの P。ハミルトン閉路(頂点を1回ずつ)は NP完全
- 「ある」は14ステップ、「無い」は6600万ステップ。 これが NP と co-NP の差。「組めません」のほうが機械には重い
- 最短経路は 0.036ms、最長経路は 17.2秒(n=16、2億7800万通り)。 47万倍
- ダイクストラは「いま一番近い所は確定していい」に乗っている。最長にはその性質がない
- 2色で塗れるかは P。3色になった瞬間に NP完全。 シフト表も会議室の割り当ても、正体はグラフ彩色
- 逃げ道は4つ。 近似・ヒューリスティック・問題を小さくする・時間で打ち切る
- 2-opt は、総当たりが62.5秒かけた答えを 0.7ms で出した(約9万倍)。 ただし保証は無い
- 200件では最適解は永久に出せないが、1.3秒で貪欲より21%短い順路が出る。 実務はそれで足りる
- 「上限が読めない探索」を本番に出さない。 5秒で打ち切るだけで、返答時間が保証される
1 << nは n が31を超えると静かに壊れる。 エラーにならず「価値0が最適」と返る- NP完全でも動的計画法が効くことがある(ナップサックの擬多項式時間)。「NP完全だから諦める」は早い
- NP完全だと分かることは、敗北ではなく前進。 「速い方法を探す」から「諦め方を選ぶ」に、根拠を持って切り替えられる
- 利用者は最適解を求めていないことが多い。 「そこそこ良いシフト表が3秒」は、「完璧なシフト表が3日後」より嬉しい
- 私が3日溶かした原因は、コードではなく「これは頑張れば速くなる問題だ」という思い込みだった
参考リンク
- roadmap.sh — Computer Science
- Clay Mathematics Institute — Millennium Problems
- MDN — performance.now
- MDN — Math.hypot
- MDN — Array.prototype.reverse
- MDN — ビット演算子
- MDN — BigInt
- Node.js — Performance measurement APIs
次に読む
この記事は 【深掘り】コンピュータ科学 の 17 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 文字列探索とKMP — grepは1文字ずつ見ていない |
| → 次の記事 | プロセスとスレッドと競合状態 — たまにだけ数が合わない |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 解くのは大変、確かめるのは一瞬
- NP完全と分かることは前進
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント