给定一组坐标，找到最大距离(使用步骤)

Question

给定一组表示飞行路径的坐标，练习是找到最大距离(给定要通过的n个点)。为了说明这个问题，我们在2D网格上表示了一个飞行路径，如下所示：

​

。

下面是算法应该对参数n(整数)所做的操作。

​

​

问题是找到一种算法，它可以扫描所有点，并通过组合所有距离来尝试，并返回最终路径的长度。

我们已经有了一种方法，可以得到两点的距离：

 /**
 * @return the distance between the two coordinates
 */
public double distance(Coordinate destination) {}

 /**
 * @return the farthest coordinate from start
 */
public Coordinate coordMax() {}

 /** 
 * @return max distance using n points
 * I would maybe try to go for a recursive solution 
 * and already have the 2 corner cases down.
 */
public double statMaxDistance(int n) {

    if (n == 0)
        return coordTable[0].distance(coordTable[coordTable.length - 1]);
    if (n == 1)
        return coordTable[0].distance(coordMax());

    // TODO recursive step

    return statMaxDistance();
}

问题是：

有没有一种方法可以完成这个任务，而不需要一个一个地迭代整个路径的每一个点，尝试所有可能的组合，计算所有可能的距离，最终得到最远的一个？

如果遵循这样一种方法，只会在整个路径上移动1到2个点，那么这种算法在计算给定3+参考点的最大距离时会非常贪婪。

Answer 1

这可以通过动态程序来解决。假设D[i][j]是从起点到i-th中间点的最大距离，最后一个点是j。您的解决方案将是D[n][endPoint]。

那么如何解决这个问题呢？第一列D[0][...]易于计算。这仅仅是对应点到起点的距离。其他列则要复杂一些。您需要检查前一列中的所有条目，其中最后一点严格地位于当前点之前。因此，要计算条目D[i][j]，必须计算：

D[i][j] = max_{k < j} (D[i - 1][k] + distance(k, j))

这意味着:迭代所有可能的k，使k小于j (即点k位于当前点j之前)。将得到的距离计算为到k (这是D[i - 1][k]部分)和从k到j的距离之和。将这些值的最大值放入D[i][j]中。如果您需要在最后重构路径(也就是说，您不只是对最大距离感兴趣)，您还可能希望跟踪k。请注意，可能存在没有有效解决方案的单元格(例如，D[1][0] --您不能将0作为第二个(索引1)中间点)。

对每一列中的每一个中间点执行此操作，直到D[n - 1][...]。最后一步是再次对D[n][endPoint]执行此过程，严格地说，它不需要位于D数组中(因为您只对一个值感兴趣，而不是整个列)。

一旦计算了这个值，这就是您的解决方案。如果要查找实际路径，则必须使用存储的每个单元格的k值进行回溯。