ヒューリスティック– tag –
-
コンピュータ科学 深掘り
PとNP・NP完全 — 答え合わせは一瞬なのに解けない
シフト表を自動で組む機能が、いくら速くしても終わらなかった。原因はコードではなく問題のほうでした。巡回セールスマンを Node.js で総当たりして、n を1増やすたびに時間が n 倍になる壁を実測します。「答え合わせは一瞬なのに、探すのは無理」という非対称を見てから、P・NP・NP完全・NP困難を1枚の表で整理します。ナップサック、ハミルトン閉路、最長経路、グラフ彩色を実際に走らせ、オイラー路や最短経路が一瞬で終わるのと並べて比べます。最後に現場の逃げ道4つ(貪欲・2-opt・問題を小さくする・時間で打ち切る)を実装して、最適解・所要時間・実装の手間を表にします。 -
コンピュータ科学 深掘り
最短経路アルゴリズム — ダイクストラは負の重みで壊れる
前の回で「重みが全部同じなら BFS が最短を出す」と分かった。では区間ごとに所要時間が違う路線図では? 10駅の路線図を作り、BFS とダイクストラの答えを同じグラフで並べて、乗り換え1回・40分と乗り換え4回・21分が別物であることを確かめる。次に負の重みを1本だけ入れて、ダイクストラがエラーも出さずに静かに間違えるところを実際に出力する。ベルマン・フォードで正しい答えを出し、負の閉路の検出まで実装して、為替の裁定取引が同じ問題だと確かめる。最後に格子迷路で A* とダイクストラの調べたマス数を数え、最小全域木をクラスカル法とプリム法の両方で解く。
1