Наименьший путь затрат в сортированном массиве

Question

Учитывая отсортированный массив A например {4,9,10,11,19}. Анкет Стоимость переезда от i->j является abs(A[j]-A[i]). Анкет Начните с данного элемента, например 10. Анкет Узнайте наименее дорожный путь без посещения того же элемента дважды. Так что в этом примере решение было бы 10->9->4->11->19 т.е. 1 + 5 + 7 + 8 = 21.

Я попытался решить это, используя ближайший соседский подход.

 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]

Это решение не работает в каждом случае. Я понял, что это проблема TSP. Что может быть лучшим подходом для решения этой проблемы? Должен ли я использовать эвристику TSP, как Christifides или какой -то другой алгоритм?

Answer 1

Для вашего случая наименьшие затраты - 21, см.

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

Я думаю, для общего случая, если вы начнете с I-Th Position, наименьшая стоимость-это путь, минимум

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

Процесс либо меньший, либо самый большой элемент, в зависимости от того, что ближе (по значению, а не индекс) к стартовому элементу, а затем просто обработайте оставшиеся элементы вправо или влево (в зависимости от того, обработали ли мы наименьший или самый большой элемент )

Итак, дано 4,9,10,11,19 начиная с 10:

Расстояние от 10 на самый маленький элемент 4 6, расстояние от 10 к крупнейшему элементу 19 9, так что перейти к 4.

Затем обработайте оставшиеся элементы в отсортированном порядке - 9, 11, 19.

Это дает нам 10 -> 4 -> 9 -> 11 -> 19, который стоит 6 + 5 + 2 + 8 = 21.

Это можно сделать в O(n).

Примечание:

Стоит отметить, что, пока мы впервые движемся к ближайшей стороне, затем к другой стороне (независимо от того, какие элементы мы обрабатываем, когда, если мы не изменим направление более одного раза), мы получим оптимальный результат Анкет

Вот почему 10 -> 9 -> 4 -> 11 -> 19 также дает 21.