정렬 된 배열의 최소 비용 경로

Question

정렬 된 배열이 주어졌습니다 A 예를 들어 {4,9,10,11,19}. 이사 비용 i->j ~이다 abs(A[j]-A[i]). 주어진 요소에서 시작하십시오 10. 같은 요소를 두 번 방문하지 않고 최소 비용 경로를 찾으십시오. 이 예에서는 해결책이 될 것입니다 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-th 위치에서 시작하면 최소 비용은 경로, 최소입니다.

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.