Path le moins coûteux dans un tableau trié

Question

Étant donné un tableau trié A par exemple {4,9,10,11,19}. Le coût de passage de i->j est abs(A[j]-A[i]). Commencez à partir d'un élément donné, par exemple 10. Découvrez le chemin le moins coûteux sans visiter le même élément deux fois. Donc, dans cet exemple, la solution serait 10->9->4->11->19 c'est à dire 1 + 5 + 7 + 8 = 21.

J'ai essayé de résoudre ce problème en utilisant l'approche du voisin le plus proche.

 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]

Cette solution ne fonctionne pas dans tous les cas. J'ai réalisé que c'est un problème TSP. Quelle pourrait être la meilleure approche pour résoudre ce problème? Dois-je utiliser l'heuristique TSP comme le Christofides ou un autre algorithme?

Answer 1

Pour votre cas, le moins le coût est de 21, voir

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

Je pense que, pour un cas commun, si vous commencez à partir de la i-tème position, le moins le coût est le chemin, minimum 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

Traitez le plus petit ou l'élément le plus grand, selon lequel est plus proche (en valeur, pas l'index) de l'élément de départ, puis traitez simplement les éléments restants vers la droite ou vers la gauche (selon que nous avons traité le plus petit ou le plus grand élément ).

Alors, donné 4,9,10,11,19 commençant par 10:

La distance de 10 au plus petit élément 4 est 6, la distance de 10 au plus grand élément 19 est 9, alors passez à 4.

Traitez ensuite les éléments restants dans l'ordre trié - 9, 11, 19.

Cela nous donne 10 -> 4 -> 9 -> 11 -> 19, qui coûte 6 + 5 + 2 + 8 = 21.

Cela peut être fait dans O(n).

Noter:

Il convient de noter que tant que nous nous déplaçons d'abord vers le côté le plus proche, puis vers l'autre côté (quel que soit les éléments que nous traitons quand, tant que nous ne changeons pas de direction plus d'une fois), nous obtiendrons un résultat optimal .

C'est pourquoi 10 -> 9 -> 4 -> 11 -> 19 donne aussi 21.