この質問は、以前に尋ねた質問の拡張です:
並べ替えられた配列の最小コスト パス
A
ソートされた配列が与えられた場合{4,9,10,11,19}
。からの移動費用i->j
は です
abs(A[j] - A[i]) + cost_incurred_till_i
。特定の要素から開始し10
ます。同じ要素を 2 回訪問せずに最小コスト パスを見つけます。
指定された配列の場合:
10->9->4->11->19 cost: 1+(1+5)+(1+5+7)+(1+5+7+8) = 41
10->4->9->11->19 cost: 5+(5+5)+(5+5+2)+(5+5+2+8) = 47
10->9->11->4->19 cost: 1+(1+2)+(1+2+7)+(1+2+7+15) = 39
10->11->9->4->19 cost: 1+(1+2)+(1+2+5)+(1+2+5+15) = 35 --one of optimal paths
10->11->19->9->4 cost: 1+(1+8)+(1+8+10)+(1+8+10+5) = 53
10->11->19->4->9 cost: 1+(1+8)+(1+8+15)+(1+8+15+5) = 63
...
最近傍法を使用してこれを解決しようとしました。
i = start
While (array is not empty)
ldiff = A[i] - A[i-1]
rdiff = A[i+1] - A[i]
(ldiff < rdiff) ? sum += ldiff : sum += rdiff
remove A[i]
この場合、最近傍は、重み付けされたパスが等しくない場合に機能します。これが TSP の問題であることに気付きました。この問題を解決する最善の方法は何ですか? Christofides やその他のアルゴリズムなどの TSP ヒューリスティックを使用する必要がありますか?