排序阵列中的成本路径最少

Question

给定一个排序的数组 A 例如 {4,9,10,11,19}. 。从 i->j 是 abs(A[j]-A[i]). 。从给定的元素开始 10. 。找出最低的成本路径，而没有两次访问同一元素。因此，在此示例中，解决方案将是 10->9->4->11->19 IE 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启发式方法，例如Christofides或其他算法吗？

Answer 1

对于您的情况最少的成本为21，请参阅

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

我认为，对于常见的情况，如果您从第i-th职位开始，成本最小就是路径，最小值

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.