Menos caminho do caminho em uma matriz classificada

Question

Dada uma matriz classificada A por exemplo {4,9,10,11,19}. O custo para se mudar de i->j é abs(A[j]-A[i]). Comece de um determinado elemento, por exemplo, 10. Descubra o menor caminho de custo sem visitar o mesmo elemento duas vezes. Então, neste exemplo, a solução seria 10->9->4->11->19 ou seja 1 + 5 + 7 + 8 = 21.

Tentei resolver isso usando a abordagem do vizinho mais próximo.

 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 solução não funciona em todos os casos. Eu percebi que esse é um problema de TSP. Qual poderia ser a melhor abordagem para resolver esse problema? Devo usar heurísticas de TSP como Christofides ou algum outro algoritmo?

Answer 1

Para o seu caso, o menor custo é 21, veja

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

Eu acho que, para o caso comum, se você começar a partir da posição da posição, o menor custo é o caminho, o 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

Processe o elemento menor ou o maior, dependendo que esteja mais próximo (em valor, não índice) para o elemento inicial e, em seguida, basta processar os elementos restantes à direita ou à esquerda (dependendo se processamos o menor ou o maior elemento ).

Então, dado 4,9,10,11,19 Começando de 10:

A distância de 10 para o menor elemento 4 é 6, a distância de 10 para o maior elemento 19 é 9, então vá para 4.

Em seguida, processe os restantes elementos em ordem classificada - 9, 11, 19.

Isso nos dá 10 -> 4 -> 9 -> 11 -> 19, que custa 6 + 5 + 2 + 8 = 21.

Isso pode ser feito em O(n).

Observação:

Vale a pena notar que, enquanto avançarmos pela primeira vez em direção ao lado mais próximo, depois em direção ao outro lado (independentemente de quais elementos processamos quando, desde que não mudemos de direção mais de uma vez), obteremos um resultado ideal .

É por isso 10 -> 9 -> 4 -> 11 -> 19 também dá 21.