访问点,算法

Question

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

我们在线上得到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秒.

有人可以帮忙吗？

Answer 1

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

我会推荐一种动态规划方法，该方法基于针对 0 到 n-1 之间的每个近值和远值解决以下子问题：

假设我们在near^th点并且已经访问了near和far（包括）之间的所有点，那么如果我们有足够的时间访问所有剩余的点，那么现在应该是几点呢？

当 x 在 0 到 n-1 之间变化时，near=far=x 的子问题的最大值 v(x) 给出了问题的答案。如果所有 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 -> 9 秒内 2 -> 3 -> 0 -> 4）