Am wenigsten Kostenpfad in einem sortierten Array

Question

Ein sortiertes Array gegeben A z.B {4,9,10,11,19}. Die Kosten für den Umzug von i->j ist abs(A[j]-A[i]). Beginnen Sie von einem bestimmten Element, z. 10. Finden Sie den geringsten Kostenpfad heraus, ohne zweimal das gleiche Element zu besuchen. In dieser Beispiellösung wäre also Lösung 10->9->4->11->19 dh 1 + 5 + 7 + 8 = 21.

Ich habe versucht, diesen Ansatz des nächsten Nachbarn zu lösen.

 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]

Diese Lösung funktioniert in jedem Fall nicht. Ich habe festgestellt, dass dies TSP -Problem ist. Was könnte der beste Ansatz sein, um dieses Problem zu lösen? Soll ich TSP -Heuristiken wie Christofides oder einen anderen Algorithmus verwenden?

Answer 1

Für Ihren Fall sind die geringsten Kosten 21, siehe

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

Ich denke

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

Verarbeiten Sie entweder das kleinere oder das größte Element, je nachdem, welches näher (im Wert, nicht der Index) am Startelement ist, und verarbeiten Sie dann einfach die verbleibenden Elemente rechts oder links (je nachdem, ob wir das kleinste oder das größte Element verarbeitet haben ).

Also gegeben 4,9,10,11,19 ab 10:

Die Entfernung von 10 zum kleinsten Element 4 ist 6, der Abstand von 10 zum größten Element 19 ist 9, also gehen Sie zu 4.

Verarbeiten Sie dann die verbleibenden Elemente in sortierter Reihenfolge - 9, 11, 19.

Das gibt uns 10 -> 4 -> 9 -> 11 -> 19, die kostet 6 + 5 + 2 + 8 = 21.

Dies kann in erledigt werden in O(n).

Notiz:

Es ist erwähnenswert, dass wir uns ein optimales Ergebnis erzielen, solange wir uns zuerst zur nächsten Seite und dann auf die andere Seite bewegen (unabhängig davon, welche Elemente wir verarbeiten, wenn wir, solange wir nicht mehr als einmal die Richtung ändern), ein optimales Ergebnis erhalten werden .

Deshalb 10 -> 9 -> 4 -> 11 -> 19 gibt auch 21.