在排序后的数组最少的成本累计路径 [英] Least cost accumulative path in a sorted array

问题描述

此问题是较早提出了一个问题的延伸：
最低成本路径在一个排序的数组

This question is an extension of a question asked earlier:
Least cost path in a sorted array

给出一个排序的数组 A 如 {4,9,10,11,19} 。费用从移动 I-＆GT;Ĵ是
ABS（A [J] - A [1]）+ cost_incurred_till_i 。从一个给定的元件例如启动 10 。发现没有访问相同的元素两倍的最低成本路径。

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]) + cost_incurred_till_i. Start from a given element e.g. 10. Find the least cost path without visiting same element twice.

对于给定的数组：

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

In this case nearest neighbor works for some cases where we don't have equal weighted paths. 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?

推荐答案

有一个为O（n ² ）动态规划的解决方案。我不知道这是否是最佳的。

There is an O(n²) dynamic programming solution. I don't know if it's optimal.

接下来的选择总是从各未访问节点的近邻，所以访问节点形成一个连续范围。逻辑子问题是找到给定访问的节点的范围内的部分解决方案。最优解的子问题仅取决于被访问范围和最后访问的节点（它必须是一个端点）。

The next choice is always an immediate neighbour from amongst the unvisited nodes, so the visited nodes form a contiguous range. A logical subproblem is to find a partial solution given the range of visited nodes. The optimal solutions to the subproblems only depend on the visited range and the last visited node (which must be one of the endpoints).

子问题可连接使用两个指标确定的访问范围codeD，与指示上次访问节点的顺序。解决子间的（A，B）的是给定的部分解决方案，从分的节点（A，B）的到的最大值（A，B）已被访问，而在的是最后一个访问节点。它可以递归定义为更好

Subproblems can be encoded using two indices identifying the visited range, with the order indicating the last visited node. The solution to subproblem (a, b) is the partial solution given that the nodes from min(a,b) to max(a,b) have already been visited and that a was the last visited node. It can be defined recursively as the better of

• 插入（一，解决（A - 目录，B））
• 插入（一，解决（B +方向，一））

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

其中的目录的如果是1的 B 的> = 在的和否则返回-1。

where dir is 1 if b >= a and -1 otherwise.

有两个基例。子问题的（0，N-1）的具有解 {A [0]} ，和子问题的（N-1，0）的有解决方案 {A [N-1]} 。这些相应于在最后的选择，它可以是第一节点或最后一个节点

There are two base cases. Subproblem (0, n-1) has solution {A[0]}, and subproblem (n-1, 0) has solution {A[n-1]}. These correspond to the final choice, which is either the first node or the last node.

完整的问题对应子问题的（S，S）的，其中的取值的是开始元素的索引。

The full problem corresponds to subproblem (s, s), where s is the index of the starting element.

这篇关于在排序后的数组最少的成本累计路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！