6

我正在从算法和数据结构（我在一个月内完成）中学习考试，但我无法为这个问题找到有效的算法：

我们在这条线上得到 1 <= n <= 5000 个点。每个点具有不同的自然坐标 0 <= d <= 10^6 和（不一定不同）自然点时间0 <= t <= 10^9 以秒为单位。我们可以从任意点开始，每秒将当前坐标更改 +/-1。问题是以这样的顺序访问所有点，即在经过他的点时间之前访问每个点。找出这次旅行的最短总时间（以秒为单位），或者说这是不可能的。

例如，给出 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 秒。

任何人都可以帮忙吗？

4

1 回答 1

3

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

我会推荐一种基于为 0 和 n-1 之间的近和远的每个值解决以下子问题的动态编程方法：

假设我们在最近的点并且已经访问了近和远（包括）之间的所有点，那么如果我们有足够的时间访问所有剩余的点，那么它必须是什么时间？

您的问题的答案由 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 秒内）

于 2013-01-10T18:01:19.850 回答