深さ優先探索で巡回セールスマン問題を解く
計算量的に頭おかしくなるから様々なアルゴリズムで頑張って早く解こうとされる代表的な例。
クソ真面目に深さ優先探索で全列挙してとくのは問題の規模が小さければ可能なので、簡単にやってみた。scalaで書いてあるけど解き方的に多少参考になればいいと思う
方法
データの扱い方を決める
街の識別子:Int -> (x座標:Int, y座標:Int)
と置くことにする
街間の距離を算出する
実は重複していて(a,b),(b,a)を削り取れるが引数を入れ替えることでコードが複雑化するので無視*1
(出発する街:Int -> 行き先の街:Int) -> 移動コスト:Double
ここまでの流れの計算に必要な物はCityExtendにまとめてスッキリさせた。
道順を列挙する
道順を予めすべて列挙しておくことにする、街を回る順序は逆から出発しても（今回の場合）同一のコストがかかるので数珠順列を列挙すればよい*2
Scalaで数珠順列 - AccessViolation Exception
lazy val roots = (0 until self.size).necklacePer.map(x => x zip (x.tail :+ x.head)).toList
こいつは 0,1,2,3 から ((0,1),(1,2),(2,3),(3,0)) を生成している
移動コストを計算する
ここまで出来たらあとは計算方法に委ねられると思う。今回はrootsを馬鹿正直に全部計算すれば終了
def dfs = roots zip roots.par.map(x => (0.0 /: x)((s,v) => s + distances(v)))
移動経路の距離を全部足しあわせているだけ
絵を描いてみる
まぁグラフィカルに描いたほうが見やすいので描いてみる、各街を描いてその上から最短経路を描いているだけ
こんな感じに仕上がります
まとめ
- 戻り値は省略しないほうが見やすい
- 案の定街の数を増やすと計算が終わらない、地獄を見る
例によってここから改良していくスタンス、そろそろscalaででかいもの創りだしてもいいんだけどねぇ
コード長く見えるけど半分ぐらい画像に書きだすところ
