Percorso meno a costo in un array ordinato

Question

Dato un array ordinato A per esempio {4,9,10,11,19}. Il costo per spostarsi da i->j è abs(A[j]-A[i]). Inizia da un determinato elemento, ad esempio 10. Scopri il percorso del minor costo senza visitare lo stesso elemento due volte. Quindi in questo esempio la soluzione sarebbe 10->9->4->11->19 cioè 1 + 5 + 7 + 8 = 21.

Ho provato a risolverlo usando l'approccio più vicino.

 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]

Questa soluzione non funziona in ogni caso. Mi sono reso conto che questo è un problema TSP. Quale potrebbe essere l'approccio migliore per risolvere questo problema? Devo usare l'euristica TSP come Christofides o qualche altro algoritmo?

Answer 1

Per il tuo caso il minimo costo è 21, vedi

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

Penso che, per il caso comune, se inizi dalla posizione I-Th, il minimo costo è un percorso, minimo di

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

Elaborare l'elemento più piccolo o più grande, a seconda che è più vicino (in valore, non indice) all'elemento iniziale, quindi elabora semplicemente gli elementi rimanenti a destra o a sinistra (a seconda che abbiamo elaborato il più piccolo o il più grande elemento ).

Quindi, dato 4,9,10,11,19 a partire da 10:

La distanza da 10 All'elemento più piccolo 4 è 6, la distanza da 10 All'elemento più grande 19 è 9, quindi passa a 4.

Quindi elabora gli elementi rimanenti in ordine ordinato - 9, 11, 19.

Questo ci dà 10 -> 4 -> 9 -> 11 -> 19, che costa 6 + 5 + 2 + 8 = 21.

Questo può essere fatto in O(n).

Nota:

Vale la pena notare che fintanto che ci muoviamo per la prima volta verso il lato più vicino, quindi verso l'altro lato (indipendentemente da quali elementi elaboriamo quando, purché non cambiamo direzione più di una volta), otterremo un risultato ottimale .

Ecco perchè 10 -> 9 -> 4 -> 11 -> 19 dà anche 21.