3

给定一个排序数组，A例如{4,9,10,11,19}。搬家的成本i->j是abs(A[j]-A[i])。从给定元素开始，例如10。在不访问相同元素两次的情况下找出成本最低的路径。所以在这个例子中，解决方案是10->9->4->11->19ie 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 问题。解决这个问题的最佳方法是什么？我应该使用像 Christofides 这样的 TSP 启发式算法还是其他算法？

4

2 回答 2

3

对于您的情况，最低成本是 21，请参阅

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

我认为，对于常见的情况，如果你从第 i 个位置开始，最小的成本是路径，最小的

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]
于 2013-11-08T07:06:53.457 回答
1

处理较小或最大的元素，取决于哪个更接近起始元素（在值上，而不是索引上），然后简单地处理右侧或左侧的剩余元素（取决于我们处理的是最小元素还是最大元素）。

所以，给定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.

于 2013-11-08T07:42:04.927 回答