2

这个问题是之前提出的问题的扩展：
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 启发式算法还是其他算法？

4

2 回答 2

0

你很近，你可以稍微修改一下最近的邻居。当两个邻居相等时，检查经过该邻居的元素，然后朝更近者的相反方向前进（以避免尽可能多地回溯）。如果这些元素的距离相同，请继续向前看，直到它们不同为止。如果您在看到差异之前就达到了界外，请朝它前进。

你的例子是一个很好的例子：

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

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

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

于 2013-11-08T20:02:35.110 回答
0

有一个 O(n 2 ) 动态规划解决方案。不知道是不是最优。

下一个选择始终是未访问节点中的直接邻居，因此已访问节点形成一个连续范围。一个逻辑子问题是在给定访问节点范围的情况下找到部分解决方案。子问题的最佳解决方案仅取决于访问范围和最后访问的节点（必须是端点之一）。

可以使用标识访问范围的两个索引对子问题进行编码，顺序指示最后访问的节点。考虑到从min(a,b)到max(a,b)的节点已经被访问并且a是最后访问的节点，子问题(a, b)的解决方案是部分解决方案。它可以递归地定义为更好的

  • insert(a, solve(a - dir, b))
  • insert(a, solve(b + dir, a))

如果b >= a ，则dir为 1 ，否则为 -1。

有两种基本情况。子问题(0, n-1)有解{A[0]}，子问题(n-1, 0)有解{A[n-1]}。这些对应于最终选择，即第一个节点或最后一个节点。

完整问题对应于子问题(s, s)，其中s是起始元素的索引。

于 2013-11-10T09:15:56.980 回答