6

私はアルゴリズムとデータ構造 (1 か月で取得したもの) から試験のために学習していますが、この問題の効率的なアルゴリズムを見つけることはできません:

ライン上に 1 <= n <= 5000 ポイントが与えられます。各ポイントは、異なる自然座標 0 <= d <= 10^6 と (必ずしも異なるわけではありません) 自然ポイント時間0 <= t <= 10^9 秒を持ちます。任意の時点から開始して、1 秒ごとに現在の座標を +/-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!$ 順列から 1 つの順列を見つけなければならないことがわかりました。

入力例:

ポイント（それぞれ座標、ポイント時間でも与えられます）：（0,4）、（1,2）、（4,5）：驚くべきことに（私は思う）それらを訪問する必要があります：0 -> 1 -> 4、なぜなら異なる順序は、問題テキストの最後の文の 1 つ前の条件を満たしません。

ポイント: (0,7), (1,2), (2,1), (3, 4), (4,11), 唯一のおかしな方法: 2 -> 1 -> 3 -> 0 -> 4、これには 10 秒かかります。

誰でも助けることができますか？

4

1 に答える 1

3

まず、座標に基づいてポイントを並べ替えます。

0とn-1の間の近距離と遠距離の値ごとに、次のサブ問題を解くことに基づく動的計画法のアプローチをお勧めします。

私たちがニアポイントにいて、ニアとファー（包括的）の間のすべてのポイントをすでに訪問しているとすると、残りのすべてのポイントを訪問するのに十分な時間があれば、何時になりますか？

あなたの問題への答えは、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->になります。 2-> 3-> 0-> 9秒で4）

于 2013-01-10T18:01:19.850 に答える