AccessViolation Exception

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

貪欲法で巡回セールスマン問題を解く

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

の改良となります。

貪欲法


貪欲法 - Wikipedia

注目すべき点は

  • 動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。

  • このため得られる解は最適解であるという保証は無い

  • 部分問題の解法と単純なソートのみでプログラムを実装することが可能

この3つ。雑に言えば適当なところから初めて、要所要所で最適値を選択するだけで終了する。

実装


既存のdistancesは(0 -> 0) -> 0のようなものを含んでいるので除外、ついでに距離の短い順にソートしておく

  • これまでの移動経路、距離
  • まだ行っていないところの中から一番近いところを取得
  • 移動経路、距離に加えて再度呼び出す

これだけでアルゴリズムは終了

結果


最初と最後は繋がなくてもわかるからいいや、むしろどこから始めたか見えるし(言い訳

f:id:kamiyaowl:20140413230030p:plain

wikiから引用した欠点にあるように初期値の選択によって解が変わってくるので最適解ではないかも可能性が多いにある

速度比較


比較用に適当なクラスを作った

implicit class FuncExtension(val self:() => Unit) {
    def processTime = {
        val s = System.currentTimeMillis
        self()
        println("[process time] : " + (System.currentTimeMillis - s) + "ms")
    }
}

how to use

(() => 0 to 100 sum).processTime

こいつを使って深さ優先探索と比較した結果

貪欲法

[process time] : 22ms

深さ優先探索

[process time] : 2414ms

まぁ全探索してるんだから遅くて当然だよねって感じ

travering salesman problem : greedy with scala