在排序后的数组最低成本路径

本文介绍了在排序后的数组最低成本路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个排序的数组 A 如 {4,9,10,11,19} 。成本从 I-＆GT运动;Ĵ是 ABS（A [J] -A [I]）。从一个给定的元件例如启动 10 。找出没有访问相同的元素两倍的最低成本路径。因此，在这个例子中的解决办法是 10→9＆GT; 4- GT; 11-＆GT; 19 即 1 + 5 + 7 + 8 = 21 。

Given a sorted array A e.g. {4,9,10,11,19}. The cost for moving from i->j is abs(A[j]-A[i]). Start from a given element e.g. 10. Find out the least cost path without visiting same element twice. So in this example solution would be 10->9->4->11->19 i.e. 1 + 5 + 7 + 8 = 21.

我试图解决这个使用最邻近的方法。

I tried to solve this using nearest neighbor approach.

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的启发式像赫里斯托菲或其他算法？

This solution does not work in every case. I have realised that this is TSP problem. What could be the best approach to solve this problem? Shall I use TSP heuristics like Christofides or some other algorithm?

推荐答案

对于你的情况最少的费用是21，看

for your case least cost is 21, see

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

我想，对于通常情况下，如果从第i个起始位置，最少成本路径，最短

I think, for common case, if you start from i-th position, least cost is path, minimum of

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]