arrays - 排序数组中的最低成本累积路径

Question

这个问题是之前提出的问题的延伸:
Least cost path in a sorted array

给定一个排序数组 A 例如{4,9,10,11,19}。从 i->j 移动的成本是
abs(A[j] - A[i]) + cost_incurred_till_i。从给定的元素开始，例如10。无需两次访问同一元素即可找到成本最低的路径。

对于给定的数组:

10->9->4->11->19 cost: 1+(1+5)+(1+5+7)+(1+5+7+8) = 41
10->4->9->11->19 cost: 5+(5+5)+(5+5+2)+(5+5+2+8) = 47
10->9->11->4->19 cost: 1+(1+2)+(1+2+7)+(1+2+7+15) = 39 
10->11->9->4->19 cost: 1+(1+2)+(1+2+5)+(1+2+5+15) = 35 --one of optimal paths
10->11->19->9->4 cost: 1+(1+8)+(1+8+10)+(1+8+10+5) = 53
10->11->19->4->9 cost: 1+(1+8)+(1+8+15)+(1+8+15+5) = 63
...

我尝试使用最近邻方法解决这个问题。

 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 启发式算法还是其他一些算法？

Answer 1

你很接近，你可以稍微修改一下最近的邻居。当两个邻居相等时，检查元素过去 那个邻居，然后朝较近的那个相反方向移动(以避免尽可能多地回溯)。如果这些元素的距离相同，请继续向前看，直到它们不一样。如果您在看到差异之前到达了界外，请朝它走。

你的例子很好看:

我们唯一的分支点是决定从 10 开始的第一步是访问 9 还是 11。从两个方向看过去显示 4 和 19。 4 更接近 10，所以远离它(到 11)。

---

显然，对于没有很多连续均匀间隔元素的数组，这会更快。如果它们没有是均匀分布的，它会和你的一样，运行 n 步。

最坏的情况是您必须在每一步都一路查看两端，这将访问每个元素。因为我们为每个 n 元素运行一次，所以它的结果是 O(n^2)。一个示例是一个包含所有 均匀间隔元素的数组，从死点开始搜索。