ソートされた配列の最小コストパス

Question

ソートされた配列が与えられます A 例えば {4,9,10,11,19}. 。移動のコスト i->j は abs(A[j]-A[i]). 。特定の要素から始めます 10. 。同じ要素を2回アクセスせずに、最小コストパスを見つけてください。したがって、この例では、解決策があります 10->9->4->11->19 すなわち 1 + 5 + 7 + 8 = 21.

私はこれを最も近い隣のアプローチを使用して解決しようとしました。

 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ヒューリスティックを使用しますか？

Answer 1

あなたの場合、最小コストは21です

10->9->4->11->19 ==>  1 + 5 + 7 + 8 = 21.

私は、一般的な場合、i番目の位置から開始する場合、最小コストはパスであり、

A[i]->A[i-1]-> ...->A[1] -> A[i+1] -> A[i+2] -> ...->A[n]  and

A[i]->A[i+1]-> ... ->A[n] ->A[i-1] ->A[i-2] -> ...->A[1]

Answer 2

より小さなまたは最大の要素のいずれかを処理します。これは、開始要素に近い（値ではなく）、右または左に残りの要素を単純に処理します（最小の要素または最大の要素を処理したかどうかに応じて）。

だから、与えられた 4,9,10,11,19 から始まる 10:

距離から 10 最小の要素に 4 6、距離からです 10 最大の要素へ 19 9なので、移動します 4.

次に、残りの要素をソートされた順序で処理します - 9, 11, 19.

これは私たちに与えます 10 -> 4 -> 9 -> 11 -> 19, 、コスト 6 + 5 + 2 + 8 = 21.

これはで実行できます O(n).

ノート：

私たちが最初に最も近い側に向かって、次に反対側に向かっている限り（どの要素に関係なく、方向を複数回変更しない限り、どの要素に関係なく）、最適な結果が得られることに注意する価値があります。 。

それが理由です 10 -> 9 -> 4 -> 11 -> 19 また、与えます 21.