どの順で回るか

近いところから順に回る。 いまいる場所からいちばん近い、まだ行っていない店へ進む。これをくり返すだけです。一瞬で経路ができて、適当な順よりずっと短くなります。ただし、近い店を先に拾ってしまうので、遠くに取り残された店が最後に1軒残り、そこまで長い一本道を走るはめになります。目先の得だけで選ぶこのやり方を貪欲法といいます。

交差をほどく。 経路のどこかが×の形に交わっていたら、その2本を別のつなぎ方に替えると必ず短くなります。短くなるつなぎ替えがある間はそれをくり返し、どこを替えても短くならなくなったら止まります。2本の辺を選び直すので2-optという名前がついています。

焼きなまし法。 交差をほどくやり方は、短くなる手しか選びません。そのせいで、少し遠回りしてからでないと届かない、もっと短い順番を見逃します。そこで、ときどきわざと長くなる手も受け入れます。受け入れやすさを決める数を温度と呼び、最初は高くしておいて、だんだん下げていきます。熱した金属をゆっくり冷ますと内部のひずみが取れる、その冷まし方から名前をとって焼きなまし法といいます。

どれも、すべてを調べたわけではないので「これが最短だ」とは言えません。答えが最短だと保証しないかわりに一瞬で答えを出す、こういうやり方を近似解法といいます。

「別の出発点から20回やり直す」を押すと、バラバラの順番から始めて交差をほどく作業を20回くり返します。出てくる距離は毎回同じではありません。交差をほどく作業は、どこを2本つなぎ替えても短くならないところで止まります。止まった以上そこから先へは進めませんが、その場所が全体でいちばん短い順番だとは限らないのです。周りを見渡すかぎり自分がいちばん低い、でも山を1つ越えた先にもっと低い谷がある。この止まり方を局所最適といいます。

焼きなまし法が、ときどきわざと長くなる手を受け入れるのはこのためです。いったん損をして山を越えないと、隣の谷には行けません。

全部試す ＝ 必ず最短・現実には終わらない　／　近似解法 ＝ 最短の保証なし・一瞬で終わる

この2つのどちらを取るかが、実際に物を運ぶ現場での判断です。配送トラックの回る順番、ゴミ収集車のコース、プリント基板に穴をあける順番、旅行で名所を回る順番。どれも同じ形の問題で、どこでも「最短だと証明された順番」ではなく「十分に短い順番」が使われています。

そしてAIの学習も、まったく同じことをしています。 データに合う答えは無数にあり、その全部を調べることはできません。だから少しずつ良くなる方向へ動かして、これ以上良くならないところで止めます。訓練データに完璧に合わせると、かえって次のデータを外してしまう。完璧な答えを探すこと自体が目的ではない、というのはその裏側です。勝ち負けの記録から少しずつ強くなっていくAIも、山を降りていく途中の姿です。

同じ意思決定シリーズでも、パンを何個焼くか、レジを何台置くかは、答えが式で一発で出ました。こちらは式では出ません。答えが求まる問題と、求まらない問題がある。機械学習理論研究室では、求まらない問題に対して「どこまで良い答えなら保証できるか」を数学で調べています。