はじめに

複数の都市を1回ずつ訪問して、元の出発点に戻ってくるまでの「一番短いルート」を見つける問題。情報科学の世界では「巡回セールスマン問題（TSP）」と呼ばれる有名な難問です。

今回、この問題をブラウザ上でアニメーションさせながら解いてくれる「最短ルート発見アプリ」を開発しました！Reactなどのフレームワークは使わず、HTMLとVanilla JS（素のJavaScript）だけでサクサク動くように作っています。

👉 実際に遊んでみる（公開URL）

ブラウザ（JS）の限界に挑む！総当たりモードの驚異的なスピード

このアプリには、優秀なルートを推測する「AI探索」モードと、すべての組み合わせを計算する「総当たり（Brute Force）」モードがあります。

巡回セールスマン問題の「総当たり」は、都市の数が増えると計算量が階乗（!）で爆発します。
例えば、都市が10個なら約18万通りですが、13個になると約2億3900万通りにもなります。

「さすがにブラウザのJavaScriptじゃ厳しいかな…？」と思いつつ、13都市を設定して総当たりモードを実行してみたところ……なんと、調子の良い時は秒間で500万〜700万ルートを計算・評価することができました！

モダンブラウザのV8エンジン（JavaScriptの実行環境）の最適化パワーはすさまじく、ブラウザ上で何億回という計算を数秒〜数十秒で終わらせてしまう光景は、見ていてとてもロマンがあります。

【初心者向け】どうやって計算を速くしているの？（内部ロジック解説）

「いくらブラウザが優秀でも、普通にコードを書くとそんなに速くならないのでは？」と思うかもしれません。
実は、裏側で計算を極限まで軽くするための3つの工夫をしています。プログラミング初心者の方にも分かりやすく解説します！

1. 距離の「カンペ」を最初に作っておく（LUT）

ルートの長さを測るには、都市と都市の距離を計算する必要があります。これには通常、ピタゴラスの定理（Math.sqrt というルート計算）を使います。
しかし、これを毎秒何百万回も計算すると、パソコンが疲れてしまいます。

そこで、スタート時に「A市からB市は〇〇km」「A市からC市は〇〇km」という全パターンの距離一覧表（カンペ）をあらかじめ作成し、メモリに保存しておきます（これをLUT：Look-Up Tableと呼びます）。
探索中は計算するのではなく、「カンペを見るだけ」にするため、劇的にスピードが上がります。

// 毎回計算するのではなく…
// const d = Math.sqrt(dx*dx + dy*dy); ←遅い

// カンペ（配列）から答えを引っ張ってくるだけ！
const d = distanceLUT[cityA * n + cityB]; // ←超速い

2. ゴミ拾い（GC）をさせないエコなメモリ管理

JavaScriptは、使い終わったデータ（配列など）を自動で掃除してくれる機能（ガベージコレクション）があります。しかし、掃除の瞬間はアプリが一瞬フリーズしてしまいます（カクつきの原因）。

このアプリでは、「新しい配列（データを入れる箱）を絶対に作らない」という縛りを設けています。
最初に決まった数の箱を用意し、あとは中身を入れ替えて使い回す（Zero Allocation）ことで、掃除の時間をゼロにし、常にフルスピードで走り続けられるようにしています。

3. 「AI探索」モードの仕組み（進化のシミュレーション）

総当たりモードは14都市を超えると、宇宙の寿命ほどの時間がかかってしまいます。そこで実用的なのが「AI探索」モードです。
これは「遺伝的アルゴリズム」という、生物の進化を真似た仕組みをベースにしています。

誕生: 適当に作ったルートを150個（親）用意する。
交配: 成績の良かったルート同士をくっつけて、新しいルート（子供）を作る。
突然変異: たまに、少しだけルートの順番をランダムに入れ替える。
4.これを何度も繰り返し、どんどん短いルートへと進化させていく。

これにより、50都市や100都市でも、数秒で「ほぼ正解に近い最短ルート」をパッと導き出してくれます。

おわりに

普段何気なく使っているWebブラウザですが、工夫次第で秒間数百万回の計算をゴリゴリこなしてくれる強力な計算機になります。

都市数を増やしてAIの賢さを眺めるもよし、12〜13都市にして総当たり計算の暴力的なスピード（秒間500万ルート！）をベンチマークとして楽しむもよし。
スマホからでもサクサク動くので、ぜひリンクから遊んでみてください！

👉 最短ルート発見アプリを開く