PとNP・NP完全 — 答え合わせは一瞬なのに解けない

PとNP・NP完全。組み合わせるパズルと確認済みのチェックリスト、時計。

答え合わせは一瞬なのに、解くのは終わりません。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つしかない(近似・ヒューリスティック・問題を小さくする・時間で打ち切る)

この記事でやること

  1. 作業フォルダ ~/cslab/np を作り、この記事の作業を全部そこに閉じ込める
  2. 巡回セールスマンで、「答え合わせ」と「探す」の時間を両方測って並べる
  3. 総当たりを n=8 / 9 / 10 / 11 / 12 で実測し、壁が立つところを表にする
  4. ナップサック・ハミルトン閉路・最長経路・グラフ彩色を、実際に小さく解いてみる
  5. オイラー路・最短経路と並べて、「似ているのに片方だけ終わらない」を見る
  6. 逃げ道4つを実装して、最適解・所要時間・実装の手間を比べる
  7. 作ったものを全部消す

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
多項式時間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か所に閉じ込めます。

bash
$ mkdir -p ~/cslab/np
$ cd ~/cslab/np
$ node -v
v22.14.0

node が入っていなければ、JavaScriptの基本 の回に入れる手順があります。

まず共通の道具を書きます。都市をランダムに置いて、順路の長さを測るだけのファイルです。

bash
$ nano cities.mjs
// 固定の乱数(毎回同じ都市が出るように)
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つ持ってきたとします。

bash
$ nano verify.mjs
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');
bash
$ node verify.mjs
都市: 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 通りです。全部試します。

bash
$ nano brute.mjs
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 は「配列の要素を入れ替えて、戻す」という書き方です。 入れ替えたら必ず元に戻す。 戻し忘れると、途中から別の配列を並べ替えていることになって、静かに間違った答えが出ます。

まず小さいところから。

bash
$ node brute.mjs 8
n=8 試した順路=5040 最短=2559.8km 時間=24.7ms
  最短順路: A -> C -> D -> H -> B -> F -> E -> G

24.7ミリ秒。 8か所なら一瞬です。ここで油断します。私はここで油断しました。

そして12か所。

bash
$ node brute.mjs 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 が増えると急に無理になる」を、言葉ではなく表で見ます。

bash
$ for n in 8 9 10 11; do node brute.mjs $n; done
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 の何倍か
85,04024.7ms—
940,320105.0ms4.3倍
10362,880510.0ms4.9倍
113,628,8005,599.5ms11.0倍
1239,916,80062,469.5ms11.2倍

n を1増やすたびに、時間がおよそ n 倍になります。 これが n!(階乗)の伸び方です。

「データが10倍になると100倍遅い」の O(n²) でも十分つらいのに、 ここでは「データが1件増えると10倍遅い」です。桁が違います。 O(n²) の話は データが10倍で100倍遅くなる — コンピュータ科学深掘り にあります。

n=15 を待つべきか、計算で出す

走らせません。 n=12 の実測から推定します。

bash
$ nano estimate.mjs
// 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)}`);
}
bash
$ node estimate.mjs
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個の荷物から選んで詰めます。価値の合計を最大に。

bash
$ nano knapsack.mjs
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)}%`);
bash
$ node knapsack.mjs
荷物 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回ずつ通って戻る道はあるか

言い方はほとんど同じです。 難しさは天と地です。

まずグラフを作ります。最短経路と最長経路も、あとで同じファイルから使います。

bash
$ nano graph.mjs
// 会議室・配送先などを模した無向グラフ
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}`);
}

オイラー路とハミルトン閉路を比べます。

bash
$ nano euler-hamilton.mjs
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');
bash
$ node euler-hamilton.mjs
各頂点の次数: 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部グラフ)。 左右の人数が違うと、ハミルトン閉路は絶対に存在しません。 左右を交互にしか進めないからです。

bash
$ nano hamilton-no.mjs
// 左グループ 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`);
}
bash
$ node hamilton-no.mjs
左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困難

同じグラフで両方やります。

bash
$ node graph.mjs
最短 A->J : 12  経路 A->J  時間 0.800ms
最長 A->J : 58  経路 A->C->B->D->F->E->H->G->J  時間 0.425ms  調べた部分経路 110

10頂点では差が出ません。頂点を増やします。

bash
$ nano scale.mjs
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秒ほど固まります。 待ってください。

bash
$ node scale.mjs
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. グラフ彩色 — 会議室の割り当て

同じ人が出る会議は、同じ時間帯に置けません。 最少で何コマ必要か。

bash
$ nano coloring.mjs
// 会議。同じ人が出る会議は同じ時間帯に置けない = 辺で結ぶ
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;
  }
}
bash
$ node coloring.mjs
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

bash
$ nano escapes.mjs
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秒止まります。 固まったのではありません。

bash
$ node escapes.mjs
都市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回ぶんの出発点を試して、その中の最良を返しました。

これが実装としていちばん強い理由は、「終わらない」が構造的に起きなくなるからです。 返答時間が上限で保証されます。 ユーザーは待たされません。

大きい問題で試す

総当たりが絶対に無理な規模でやってみます。

bash
$ nano big.mjs
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)}%`);
bash
$ node big.mjs
配送先 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秒で出せます」です。


後片づけ

作ったものを全部消します。

bash
$ ls ~/cslab/np
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

中身を確認してから消します。

bash
$ cd ~
$ rm -rf ~/cslab/np
$ ls ~/cslab
search

rm -rf は戻せません。 パスを打つ前に、必ず ls で中身を確認してください。 rm の挙動は rmで消したものは戻らない — Linux深掘り にあります。

~/cslab ごと消したい場合は、こちらです。

bash
$ rm -rf ~/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日溶かした原因は、コードではなく「これは頑張れば速くなる問題だ」という思い込みだった

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 17 / 25 本目です。

記事
← 前の記事文字列探索とKMP — grepは1文字ずつ見ていない
→ 次の記事プロセスとスレッドと競合状態 — たまにだけ数が合わない

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Complexity Classes
  • 解くのは大変、確かめるのは一瞬
  • NP完全と分かることは前進

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次