宅配者になるべくして
コンテキスト
大学には主専攻実験みたいなものがあって学部3年になると実施される。実験は前期・後期に分かれていて、前期は巡回セールスマン問題をよっこいせする実験を選択した。というより第一希望から落ちた。
実験での行動
- 実験参考テキストを読み込んだ
- 実装課題をいくつかやった
- 最終発表に向けて適当なテーマを決めてやる
適当なテーマとして分枝限定法に関する全探索の効率化を行う下界算出アルゴリズムを調べ、いい感じに実装することにしてみた。 結果的に実装バグって実装間に合わない状態ではあったが、アルゴリズムの理解と枝刈り効率について考察できたのである程度の評価は貰えた。
発表資料
発表当日の朝に急いで作ったので白背景に黒文字かつ計測が雑なのは許して。
実装
実装するにあたって、TSPLIBのデータを読み込んで 汎用データ構造化する仕組みを実装してアルゴリズムを実装するだけで良い環境を構築した。 EUC_2Dのデータのみの読み込みになるためかなり雑に作ってあるが、使い回しはできそうなので公開してみた。
参考実装というか、今回の実験で自分が実装したアルゴリズムもいくつかある。
- Brute force
- Dynamic programming
- 最近追加法
- 最近隣接法
- 焼き鈍し法
- 分枝限定法(動いてない)
所感
実験は上半期使って長々と行うのだけど、この実験の内容は一週あればレポートまで終わってしまう内容なので暇。 暇なので真面目に取り組みたい場合は文献を読み漁ったりできるわけだけど、 サーベイ力や継続力を持って取り組める基礎体力に自信が無いのであれば別の実験を選択することをおすすめします。 あとはまぁ、ある程度の実装力を要するのでコーディング無理な人も向いてないかもしれない。
