一番良い答えを探せ：山登り法と焼きなまし法

家4軒に、病院を2つ置く

4軒の家に病院を2つ建てます。近くの病院までの距離を足すと、最初は合計17マスでした。

この合計を一番小さくする置き方を探すのが最適化です。

置き方に点数をつける

合計距離を出せば置き方の良さを数値で比べられます。この点数を返す仕組みが目的関数です。

距離が短いほど高くなるよう並べると、全体の選択肢は山と谷の地形に見えてきます。

山の頂上を目指す

好きな場所をタップして「のぼる」を押すと、今より高い隣に進みます。止まった高さが一番高い山と同じか確かめてみましょう。

隣に1マスずつ動かす

病院を1マス動かすのを「隣」と呼び、合計が最も減る隣へ進み続けるのが山登り法です。

今回の例では、合計17マスが11マスまで減って止まりました。

病院2つの置き場所を山登り法で探します。病院を1マス動かした置き方を全部調べたあと、次に進むのはどれでしょう。

問題：病院2つの置き場所を山登り法で探します。病院を1マス動かした置き方を全部調べたあと、次に進むのはどれでしょう。

1. 合計距離がいちばん減る置き方（正解）
2. まだ調べていない遠くの置き方
3. 合計距離が変わらない置き方

解説：山登り法が見るのは1マス動かした隣だけです。合計が一番減る隣へ進み、減らなくなったら止まります。

11で止まったのに、9がある

合計11の場所は隣に動かすと11以上になりますが、離れた場所に合計9の場所がありました。

周りより良いだけの行き止まりを局所解、全体で一番良い答えを大域解と呼びます。

○か✕か

○か✕か：山登り法で病院の置き場所を探すと、どこから始めても合計距離がいちばん小さい置き方にたどり着く。

答え：✕。山登り法は1マス隣しか見ません。合計11で止まり、離れた合計9には届きませんでした。

出発点を変えて、何度も登る

スタート位置をランダムに変えて何度も登り、最高の答えを残すのがランダムリスタートです。

1回目は裏山で止まっても、最高峰のふもとに当たれば届きます。

あえて悪いほうへ進む

もう1つの方法は、評価が下がる隣へあえて進むことです。谷を越えないと高い山へ行けないからです。

これが焼きなまし法です。金属を熱して冷まし構造を整える加工が名前の由来です。

山登りと焼きなましを比べる

同じ裏山から山登りと焼きなましを動かします。あえて下った回数と着いた高さを見比べましょう。

最初は大胆に、最後は慎重に

焼きなまし法は「温度」を高く始めて少しずつ下げます。高い間は悪化する移動もよく受け入れます。

悪化が大きい移動や、温度が下がるほど受け入れにくくなり、最後は山登り法と同じ動きになります。

病院の置き場所探しで、山登り法は合計11の局所解で止まりました。焼きなまし法ならそこから抜け出せることがあるのはなぜでしょう。

問題：病院の置き場所探しで、山登り法は合計11の局所解で止まりました。焼きなまし法ならそこから抜け出せることがあるのはなぜでしょう。

1. 合計が一時的に増える移動も受け入れるから（正解）
2. 合計が減る隣を、より多く調べるから
3. 出発点を変えて、何度もやり直すから

解説：合計11の置き方は、隣がすべて11以上です。焼きなまし法は温度が高いうちは悪くなる移動も許すため、一度合計が増える場所を通って行き止まりから抜け出せます。

10か所を回る道順は、362万通り

全地点を1回ずつ回る最短の道順を探す問題を巡回セールスマン問題と呼びます。

地点が10か所あるだけで、道順は10!の3,628,800通りに跳ね上がります。

2本の道をつなぎ替えて、隣を作る

全通りを比べる代わりに、いまの道の2本をつなぎ替えたルートを「隣」にします。

交差する2本を繋ぎ直せば短くなります。この隣を作れば山登り法や焼きなまし法が使えます。

10か所を回る配達の道順を、焼きなまし法で探します。このとき「隣の道順」として使うのはどれでしょう。

問題：10か所を回る配達の道順を焼きなまし法で探します。このとき「隣の道順」として使うのはどれでしょう。

1. いまの道順の2本の道をつなぎ替えたもの（正解）
2. いまの道順を逆向きにたどり直したもの
3. 地点を1つ減らして9か所にしたもの

解説：2本をつなぎ替えると、全地点を1回ずつ回る条件を守ったまま、少しだけ違う道順ができます。少しずつ違う隣があるから、1歩ずつ良くしていけます。

一番良い答えの探し方

• 置き方や道順に、目的関数で点数をつける
• 山登り法で、点数が良くなる隣へ1歩ずつ進む
• 局所解で止まったら、出発点を変えて登り直す
• 焼きなまし法で、温度が高いうちは悪い移動も受け入れる

4軒の家に病院を2つ置く問題で、山登り法は合計11で止まりましたが、合計9の置き方もあります。焼きなまし法を使わずに、9に届く見込みを上げる工夫は？

問題：4軒の家に病院を2つ置く問題で、山登り法は合計11で止まりましたが、合計9の置き方もあります。焼きなまし法を使わずに、9に届く見込みを上げる工夫は？

1. 出発点を変えて、何度も登り直す（正解）
2. 合計がいちばん減る隣だけを選び続ける
3. 隣を調べる順番を毎回入れ替える

解説：出発点を変えて何度も登れば、どこかが9のふもとに当たる見込みがあります。隣の選び方や順番を変えても、11の周りの隣はすべて11以上のままです。では「隣り合う地域は同じ色にしない」のように、少しでも破るとダメな決まりがある問題はどう解くのでしょう。次は地図の3色塗り分けを解き、決まりを破った瞬間に1歩戻る探し方を見ます。