2

この質問は、以前に尋ねた質問の拡張です:
並べ替えられた配列の最小コスト パス

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 ヒューリスティックを使用する必要がありますか?

4

2 に答える 2

0

あなたは近くにいるので、最も近い隣人を少し変更するだけです。2 つの隣接要素が等しい場合、その隣接要素を過ぎた要素をチェックし、近い方の反対方向に移動します (バックトラックを避けるため)。それらの要素が同じ距離にある場合は、そうでなくなるまで前方を見続けます。違いがわかる前にアウト オブ バウンズに達した場合は、そこに向かって進みます。

あなたの例はこれを見るのに良いものです:

唯一の分岐点は、 を訪問する9か11、 からの最初のステップであるかを決定すること10です。それらを両方向から見ると、 と が表示さ4れ19ます。4は に近い10ので、そこから離れて ( に11) 向かいます。

明らかに、連続した等間隔の要素が多くない配列では、これはより高速になります。それらのどれも等間隔に配置されていない場合、それはあなたのものと同じで、段階的に実行されnます.

最悪の場合、各ステップで両端までずっと見なければならず、すべての要素にアクセスすることになります。nこれを要素ごとに 1 回実行しているので、結果はO(n^2)になります。例としては、中心から検索を開始する、すべての要素が等間隔に配置された配列があります。

于 2013-11-08T20:02:35.110 に答える
0

O(n 2 ) 動的計画法ソリューションがあります。最適かどうかはわかりません。

次の選択肢は、常に未訪問のノードの中からすぐ近くにあるノードであるため、訪問済みのノードは連続した範囲を形成します。論理的な下位問題は、訪問したノードの範囲が与えられたときに部分的な解を見つけることです。サブ問題の最適解は、訪問した範囲と最後に訪問したノード (エンドポイントの 1 つでなければなりません) にのみ依存します。

サブ問題は、最後に訪問したノードを示す順序で、訪問した範囲を識別する 2 つのインデックスを使用してエンコードできます。部分問題(a, b)の解は、 min(a,b)からmax(a, b) までのノードが既に訪問されており、 aが最後に訪問されたノードである場合の部分解です。の良い方として再帰的に定義できます。

  • insert(a, solve(a - dir, b))
  • insert(a, solve(b + dir, a))

ここで、dirはb >= a の場合は 1、それ以外の場合は -1 です。

2 つの基本ケースがあります。サブ問題(0, n-1)には解{A[0]}があり、サブ問題(n-1, 0)には解 があります{A[n-1]}。これらは、最初のノードまたは最後のノードのいずれかである最終的な選択に対応します。

完全な問題は subproblem (s, s)に対応します。ここで、sは開始要素のインデックスです。

于 2013-11-10T09:15:56.980 に答える