はじめに

K3Tunnel（ケイサントンネル）というプログラミング学習サイトで公開されている「サンタさんの配達ルート」というプログラム例（全列挙、局所探索法）を、ゆるプログラマー視点で、じっくりゆっくり味わっていきます。

なお、全列挙して最適ルートを探すプログラムを組んだのは、1年前の自分、つまり「もはや他人」です。したがって、中の人としての自分が作ったコードを、個人としての自分（もはや他人）が味わっているという状況です。一方、局所探索法の方は、本当の他人が書いたコードであるため、この2つのプログラムは、だいぶ趣が異なっております。

「サンタさんの配達ルート」問題とは

前提となる世界観

北極の近くにいるサンタクロースは、毎年、世界中の子どもたちにプレゼントを届けています。
世界に子どもは、20億人近くいるのでひとりで届けることはできません。
実は、サンタエージェントと呼ばれる人たちが、子どもたちにプレゼントを配っています。
サンタエージェントは、ピラミッド構造をもった組織になっていて、最下層のサンタエージェントは5人の子どもたちにプレゼントを配達しないといけません。

詳細は、同じくK3Tunnelのプログラミング例「サンタさんへの手紙はいつまでに届ければよい？」を参照ください。

最下層サンタエージェントのラストワンマイル問題

サンタエージェントといえども、ラストワンマイル問題から逃げることはできません。
移動距離×プレゼントの重さ（コスト）が一番小さくなるルートを選ぼう。というのが、「サンタさんの配達ルート」問題です。

今回、ゆっくり味わう問題はこちらです。（画像はK3Tunnelサイトより引用）

サンタさんのおうちを原点に、配達先の座標と、プレゼントの重さが示されています。この5件を配達するベストなルートを見つけていきます。ところで、この座標の単位は果たしてメートルなのかキロメートルなのか、フィートなのかマイルなのか記載がありません。夢を与える大人は、徒歩での配達を想像するべきかもしれません。

結果を眺めてみる

グラフの出力結果はこう。サンタさんのおうちを出発して、4→2→5→3→1と周り、サンタのおうちに帰っていきます。

問題設定の図と重ね合わせるとこういう感じに。

ポイントは、最初のおうちのプレゼントが5kgなのに対して、2番目のおうちは10kgであること。「重いものから順番に降ろしていく」順番ではないのです。

「サンタさんの配達ルート」問題を解く方法

K3Tunnelのサイトでは、5箇所を回るルートを全て列挙してその中から最適ルートを探す方法と、局所探索法なるものを使って探す方法が紹介されています。ゆるプログラマーとしては、とりあえず、全部書き出せばいい方を先に味わうことにします。

ルートを全て列挙して最適ルートを探索する

まずは5箇所を回るルートを全て列挙してその中から最適ルートを探す方法から。

全体を概観する

全体図

キュキュキュっと縮小して全体を1画面に収め、少し位置調整して眺めてみます。左下がメインの処理で、それ以外は、メインから呼び出している関数の定義のようです。

「最初の荷物の重さにする」っていう関数は、何をしているのでしょう。。若干、関数名の付け方をミスっているような気がしますが、とりあえず、脇に置いておきます。

メインの処理

メインの処理を拡大して眺めて行きます。

ちゃんと配達ルートを全列挙して、全ての配達ルートでコスト（移動距離×プレゼントの重さ）を計算してベストを保存し、最後にグラフにプロットしていることが見てとれます。

ここから、ひとつずつ確認して行きたいと思います。

じっくり味わうために

「コピーしてプロジェクト作成」するとコード編集できるようになり、他のブロックを使ったり、保存しておいたり、色々試しながらじっくり味わうことができます。

配達ルートの全列挙

最初に「配るおうちリスト」をこう定義しています。

これを引数に「サンタが移動する順序リスト」を作っているのがこの関数です。

この関数によって、こんな感じのリストが作られます。いわゆる順列ってやつです。

サンタ,1,2,3,4,5,サンタ
サンタ,1,2,3,5,4,サンタ
サンタ,1,2,4,3,5,サンタ
サンタ,1,2,4,5,3,サンタ
・・・・　中略
サンタ,5,4,2,1,3,サンタ
サンタ,5,4,2,3,1,サンタ
サンタ,5,4,3,1,2,サンタ
サンタ,5,4,3,2,1,サンタ

関数の定義はこちら。

再帰関数を使って、順列を作っています。再帰関数を使いこなせないゆるプログラマーなので、ここは、雰囲気だけ味わうことにします。

ポイントは

地点リスト（数字のリスト）から、数字を1つずつずらしながら新しい順序を作る処理が再帰的に呼び出されている
in_argは、まだ順序に入れていない地点（数字）のリストになっているので、これが空になったら、順序が完成したことになる（再帰呼び出しが止まる）
出来上がった順序は、「サンタが移動する順序リスト」に入れていて再帰関数の引数にはなっていない

というあたりでしょうか。ちょっと書いていてよくわからなくなってきました。

なお、なぜ再帰関数を使いこなせないのに再帰を使えたかというと、以前から再帰関数に憧れていたゆるプログラマーが、「再帰で書きたいのにわからん！！」と騒いでいたら、どこからともなく現れた妖精さん（上司ともいう）が、この関数は作ってくれたのでした。感謝です。いつか再帰関数を使いこなせるようになりたいものです。

おうちconfig

配達ルートを全列挙したら、それぞれのルートで（移動距離×プレゼントの重さ）を計算すれば良いのですが、座標やら重さやらを簡単に取得できるように「おうちconfig」関数を作って、配達先とサンタさんのおうちの座標とプレゼントの重さをまとめて定義しています。引数に1,2,3,4,5またはサンタを渡すとリストでゲットできます。

コスト計算

移動距離×プレゼントの重さ（コスト）を計算している関数はこちらです。引数は、配達ルートの地点のリストで、例えば「サンタ, 1, 2, 3, 4, サンタ」などが渡されます。

最初の荷物の重さにする

「コスト計算」関数の一番上で実行されている「最初の荷物の重さにする」関数。

「荷物の重さ」変数の中身を「最初の荷物の重さ」にしているようです。

「最初の荷物の重さにする」という関数名は、ミスっているのかと思いましたが、ミスっていたわけではなく、命名センスの問題だったようです。他人の目でみると、ありえん！！と思いましたが、見慣れてくると、これも素直でいいかな。と思えてきました。

距離

続いて、配達ルートの地点ごとに、そこまでのコスト計算をしていきます。

この中の「距離」ブロックの定義はこちら。普通に座標から距離を計算しています。

次の地点に行く前に、その地点でのプレゼント分、重さを引いています。

ベストのルートを保存しておく

全列挙した配達ルートのリストについて順番にコスト計算して、それまででコストが最小の場合に、その時のコストとルートを保存しています。

ベストの配達ルートをグラフにプロット

結果を出力しているのは、ここです。

グラフを出すのに使っているブロックはこれ。指定した座標に点を打ってくれます。

ここで、直線を選ぶと、プロットとプロットを線でつなげてくれます。

例えば、サンタさんのおうち（原点）から、①から⑤まで番号順に回って、おうちに戻るルートをプロットするために、こうブロックを並べると、

こうなります。

グラフブロックを味わったところで、もう1度、結果出力しているところを眺めてみると、「最良順序」に収められたリストを順番にプロットしていそうな雰囲気です。

プロットする座標を指定しているのはこれ。

最良順序は、こうなっています。（プログラム例を実行すると下の方に表示されます）

最良順序 = ['サンタ’, 4, 2, 5, 3, 1, 'サンタ']

q=1からq=7までプロットをするので、「おうちconfig」関数に'サンタ’, 4, 2, 5, 3, 1, 'サンタ'が順番に渡され、無事、最適ルートがプロットされています。めでたい。

局所探索法のプログラムを眺める

続いて、局所探索法なるものを使って探す方法も見ていきます。こちらもしみじみ味わおうかなと思いましたが、長くなってしまったし、疲れてきたので、ざざっと眺めてみます。

全体図

キュキュキュっと縮小して全体を１画面に収め、少し位置調整して眺めてみます。左がメインの処理で、コスト算出とグラフ描画（地図描画）が別関数になっています。

局所探索法っぽいところはココ。

局所探索法っぽいところ

こんな感じになっています。なるほど！

トライ回数が多いと、ほぼ毎回、星型になりますが、トライ回数を少なくすると、星型になったりならなかったりします。今回は全列挙できるレベルでしたが、全列挙は厳しいケースでも使えるポピュラーな方法らしいです。なるほど！

終わりに

このプログラム例は、社内のチャットグループで、こんなのどう？という思いつきが投稿されたことが発端で生まれました。プログラム例としてクリスマスに合わせて公開することを決めたのは、クリスマス目前。そこから、問題設定の詳細を検討しつつ、コードを組み始めました。時間もないのに、再帰を使いたいだの、どうせなら星型ルートにしたいだの、重い順に回るのはつまらないだの贅沢を言い始めたり、10kgのプレゼントはセントバーナードの子犬かな？などウキウキしたり、つよつよプログラマーが「局所探索法で実装したよ！」と突然提出してきたり、などなど、わいわいチャットしながら、プライベートでは、最下層サンタエージェントとして我が子への配達業務を遂行しながら作りました。

クリスマスにぴったりな、ファンタジーと現実を融合したプログラム例をゆるっと楽しんでいただけたら、うれしいです。今年も何か作りたいなとは思っています。サンタさん、ネタをください。