読者です 読者をやめる 読者になる 読者になる

AccessViolation Exception

仕事でもはんだづけ、家でもはんだづけ

深さ優先探索で巡回セールスマン問題を解く

計算量的に頭おかしくなるから様々なアルゴリズムで頑張って早く解こうとされる代表的な例。

クソ真面目に深さ優先探索で全列挙してとくのは問題の規模が小さければ可能なので、簡単にやってみた。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)))

移動経路の距離を全部足しあわせているだけ

絵を描いてみる

まぁグラフィカルに描いたほうが見やすいので描いてみる、各街を描いてその上から最短経路を描いているだけ

f:id:kamiyaowl:20140413181713p:plain

こんな感じに仕上がります

まとめ


  • 戻り値は省略しないほうが見やすい
  • 案の定街の数を増やすと計算が終わらない、地獄を見る

例によってここから改良していくスタンス、そろそろscalaででかいもの創りだしてもいいんだけどねぇ

コード長く見えるけど半分ぐらい画像に書きだすところ

travering salesman problem : depth first search wi ...

*1:方向によってコストが異なる問題にも対応できる

*2:どこが深さ優先探索なのか突っ込み入れられるが、数珠順列の並びがそのまま探索順になっている