algorithm - 访问点、算法

Question

我正在从算法和数据结构(我在一个月内学习)学习考试，但我无法找到解决此问题的有效算法:

We are given 1 <= n <= 5000 points on the line. Each point has different natural coordinate 0 <= d <= 10^6 and (not necessarily different) natural point-time 0 <= t <= 10^9 in seconds. We can start at any point and in each second change our current coordinate by +/-1. The problem is to visit all the points in such order that every point is visited before elapsing his point-time. Find the minimum total time (in seconds) of this trip, or say it's impossible.

比如给出5个点(坐标，点-时间):

(1,3), (3,1), (5,6), (8,19), (10,15), 有可能，当我们旅行时访问坐标:3 -> 1 -> 5 -> 8 -> 10，我们得到的总时间最少，等于:11。

我的第一个想法是按字典顺序对所有点进行排序:(点-时间，坐标)，然后按此顺序访问它们。当然，当第i个点和第(i+1)个点之间有点时，我们可以在访问第(i+1)个点之前访问它们。但不幸的是，没有人争论为什么这种贪婪的方法应该有效，尽管它很难实现。也许我想太快解决它？ n 很小，所以我想 O(n^2) 应该没问题。

我找到了输入的其他示例，认为它可能会帮助我找到解决方案。但现在我只看到我必须找到所有可能的 $n!$ 排列中的一个排列。

输入示例:

点(也分别由坐标、点时间给出):(0,4)、(1,2)、(4,5):令人惊讶的是(我认为)我们必须访问它们:0 -> 1 -> 4，因为任何不同的顺序都不满足问题文本中最后一句话的条件。

点:(0,7), (1,2), (2,1), (3, 4), (4,11)，唯一有趣的方式是:2 -> 1 -> 3 -> 0 -> 4，这需要我们 10 秒。

有人能帮忙吗？

Answer 1

首先根据坐标对点进行排序。

我会推荐一种基于为 0 和 n-1 之间的每个 near 和 far 值解决以下子问题的动态规划方法:

鉴于我们在near^th点并且已经访问了near和far之间的所有点(包括)，那么如果我们有足够的时间访问所有剩余的点，那么它必须是什么时间？

您的问题的答案由 near=far=x 的子问题的最大值 v(x) 给出，因为 x 在 0 和 n-1 之间变化。如果所有 x 的 v(x)<0，那么您无法到达所有点。但是，如果对于某些 x，v(x)>=0，那么您可以从位置 x 开始，在“所有点的最大点时间”-v 给定的时间内到达所有点。

案例之间的循环是基于考虑从最近的第 ^ 个点向左或向右移动，直到到达您尚未覆盖的第一个点。 (这将涉及到近点或远点的直接邻居，因此重复只需要 O(1) 时间来计算)

有 n^2 个子问题，所以这种方法总体上应该花费 O(n^2) 的时间。

编辑

实现此方法的 Python 代码:

A=[(0,7), (1,2), (2,1), (3, 4), (4,11)]
A.sort()
M=max(a[1] for a in A)
cache={}
def go(near,far):
    """Given that we are at near and have visited all points in [near..far], 
    (near can be > or < or = far)
    return the latest time that allows us to visit all points, 
    and visit the point near itself."""
    if abs(far-near)==len(A)-1:
        return A[near][1]-1

    key=near,far
    if key in cache:
        return cache[key]

    v=-1
    d = 1 if near<=far else -1
    n = near-d
    if 0<=n<len(A):
        v=go(n,far)-abs(A[n][0]-A[near][0])
    n = far+d
    if 0<=n<len(A):
        v=max(v,go(n,near)-abs(A[n][0]-A[near][0]))

    v=min(v,A[near][1]-1)
    cache[key]=v
    return v

v=max((go(x,x),x) for x in xrange(len(A)))
if v[0]<0:
    print 'Impossible'
else:
    print 'Takes',M-v[0]-1,'seconds starting from point',v[1]

对于时间为 1 的点，您必须在时间 t<1 还是在时间 t<=1 到达它，这有点不明确。此解决方案使用时间 t<1，因为它与您的示例匹配。

(如果要求是 t<=1，那么 (0,7), (1,2), (2,1), (3, 4), (4,11) 的解就是路径1 -> 2 -> 3 -> 0 -> 4 在 9 秒内)