貪欲法で巡回セールスマン問題を解く
深さ優先探索で巡回セールスマン問題を解く - AccessViolation Exception
の改良となります。
貪欲法
注目すべき点は
動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。
このため得られる解は最適解であるという保証は無い
部分問題の解法と単純なソートのみでプログラムを実装することが可能
この3つ。雑に言えば適当なところから初めて、要所要所で最適値を選択するだけで終了する。
実装
既存のdistancesは(0 -> 0) -> 0のようなものを含んでいるので除外、ついでに距離の短い順にソートしておく
- これまでの移動経路、距離
- まだ行っていないところの中から一番近いところを取得
- 移動経路、距離に加えて再度呼び出す
これだけでアルゴリズムは終了
結果
最初と最後は繋がなくてもわかるからいいや、むしろどこから始めたか見えるし（言い訳
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
まぁ全探索してるんだから遅くて当然だよねって感じ
