ざっくり解説: 焼きなまし法はなぜうまくいくのか？

概要焼きなまし法は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられています. 従ってこの文脈では様々な解説記事があるのですが, いわゆるマラソン競技特有の「コツ」や実装方法の説明がほとんどで, 焼きなまし法自体を数理的に深掘りした記事もなくはないのですが, やはり「なぜうまくいくのか」の観点で説明している記事はほとんど見たことがないので, なんとなくこの辺りが気になるという人向けにこの記事で解説していきます (公開時は把握してなかったのですが, 本記事の内容はこちらの記事とほぼ同じ内容になっていますので, 数理的な説明をする記事が全くないというわけではありません). 内容としてはメトロポリ