Ruta de menor costo en una matriz ordenada

Question

Dada una matriz ordenada A p.ej {4,9,10,11,19}. El costo de mudarse de i->j es abs(A[j]-A[i]). Comience desde un elemento dado, por ejemplo, 10. Descubra la ruta de menor costo sin visitar el mismo elemento dos veces. Entonces, en este ejemplo, la solución sería 10->9->4->11->19 es decir 1 + 5 + 7 + 8 = 21.

Traté de resolver esto usando el enfoque de vecinos más cercanos.

 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]

Esta solución no funciona en todos los casos. Me he dado cuenta de que este es un problema de TSP. ¿Cuál podría ser el mejor enfoque para resolver este problema? ¿Debo usar heurísticas TSP como Christofides o algún otro algoritmo?

Answer 1

Para su caso, el menor costo es de 21 años, ver

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

Creo que, para el caso común, si comienza desde la posición I-th, el menor costo es ruta, mínimo de

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

Proceso, ya sea el elemento más pequeño o más grande, dependiendo que esté más cerca (en valor, no índice) al elemento inicial, simplemente procese los elementos restantes a la derecha o hacia la izquierda (dependiendo de si procesamos el elemento más pequeño o más grande ).

Entonces, dado 4,9,10,11,19 empezando desde 10:

La distancia de 10 al elemento más pequeño 4 es 6, la distancia de 10 al elemento más grande 19 son 9, así que muévete a 4.

Luego procese los elementos restantes en orden ordenado - 9, 11, 19.

Esto nos da 10 -> 4 -> 9 -> 11 -> 19, que cuesta 6 + 5 + 2 + 8 = 21.

Esto se puede hacer en O(n).

Nota:

Vale la pena señalar que mientras nos movemos primero hacia el lado más cercano, luego hacia el otro lado (independientemente de los elementos que procesemos cuando, siempre que no cambiemos de dirección más de una vez), obtendremos un resultado óptimo .

Es por eso 10 -> 9 -> 4 -> 11 -> 19 también da 21.