10

n 個のマイルストーンがある直線道路があります。ランダムな順序でマイルストーンのすべてのペア間の距離を含む配列が与えられます。マイルストーンの位置を見つけます。

例：

4 つのマイルストーン (a、b、c、d) がある道路を考えてみましょう。

a ---3km--- b ---5km--- c ---2km--- d

a と b の間の距離は 3

a と c の間の距離は 8

a と d の間の距離は 10

b と c の間の距離は 5

b と d の間の距離は 7

c と d の間の距離は 2

上記の値はすべて、7、10、5、2、8、3 のようにランダムな順序で与えられます。

出力は 3、5、2 または 2、5、3 でなければなりません。

指定された配列の長さが n であると仮定します。私の考えは：

  1. 2 次方程式を x として解いて、マイルストーンの数を計算します。
  2. P(n, x-1) の可能性があります。
  3. 考えられるすべての順列を検証します。

この問題のより良い解決策はありますか?

4

4 に答える 4

0

マイルストーンを 1 つずつ配置する

EDIT以下の新しい実装を参照してください (タイミング付き)。

重要なアイデアは次のとおりです。

  1. 0の 1 つのマイルストーンと のマイルストーンから始めて、マイルストーンのリストを 1 つずつ作成しmax(distances)ます。それらをエンドポイントと呼びましょう。
  2. 考慮されていない最大の距離は、エンドポイントの 1 つからである必要があり、対応するマイルストーンには最大で 2 つの位置が残ります。

次の Python プログラムは、左側のエンドポイントからマイルストーンを配置できるかどうかを単純にチェックし、そうでない場合は、右側のエンドポイントからマイルストーンを配置しようとします (常に、既に配置されたマイルストーンでは考慮されていない最大距離を使用します)。配置が後で間違っていることが判明する可能性があるため、これはバックトラッキングで行う必要があります。

出力されない別の (ミラーリングされた) ソリューションがあることに注意してください。(2 つ以上の解 (対称) はあり得ないと思いますが、証明していません。)

マイルストーンの位置を と見なし、OP が必要とする出力にsolutionヘルパー関数を使用します。steps

from collections import Counter

def milestones_from_dists(dists, milestones=None):
    if not dists: # all dist are acounted for: we have a solution!
        return milestones
    if milestones is None:
        milestones = [0]
    max_dist = max(dists)
    solution_from_left = try_milestone(dists, milestones, min(milestones) + max_dist)
    if solution_from_left is not None:
        return solution_from_left
    return try_milestone(dists, milestones, max(milestones) - max_dist)

def try_milestone(dists, milestones, new_milestone):    
    unused_dists = Counter(dists)
    for milestone in milestones:
        dist = abs(milestone - new_milestone)
        if unused_dists[dist]:
            unused_dists[dist] -= 1
            if unused_dists[dist] == 0:
                del unused_dists[dist]
        else:
            return None # no solution
    return milestones_from_dists(unused_dists, milestones + [new_milestone])

def steps(milestones):
    milestones = sorted(milestones)
    return [milestones[i] - milestones[i - 1] for i in range(1, len(milestones))]

使用例:

>>> print(steps(milestones_from_dists([7, 10, 5, 2, 8, 3])))
[3, 5, 2]
>>> import random
>>> milestones = random.sample(range(1000), 100)
>>> dists = [abs(x - y) for x in milestones for y in milestones if x < y]
>>> solution = sorted(milestones_from_dists(dists))
>>> solution == sorted(milestones)
True
>>> print(solution)
[0, 10, 16, 23, 33, 63, 72, 89, 97, 108, 131, 146, 152, 153, 156, 159, 171, 188, 210, 211, 212, 215, 219, 234, 248, 249, 273, 320, 325, 329, 339, 357, 363, 387, 394, 396, 402, 408, 412, 418, 426, 463, 469, 472, 473, 485, 506, 515, 517, 533, 536, 549, 586, 613, 614, 615, 622, 625, 630, 634, 640, 649, 651, 653, 671, 674, 697, 698, 711, 715, 720, 730, 731, 733, 747, 758, 770, 772, 773, 776, 777, 778, 783, 784, 789, 809, 828, 832, 833, 855, 861, 873, 891, 894, 918, 952, 953, 968, 977, 979]
>>> print(steps(solution))
[10, 6, 7, 10, 30, 9, 17, 8, 11, 23, 15, 6, 1, 3, 3, 12, 17, 22, 1, 1, 3, 4, 15, 14, 1, 24, 47, 5, 4, 10, 18, 6, 24, 7, 2, 6, 6, 4, 6, 8, 37, 6, 3, 1, 12, 21, 9, 2, 16, 3, 13, 37, 27, 1, 1, 7, 3, 5, 4, 6, 9, 2, 2, 18, 3, 23, 1, 13, 4, 5, 10, 1, 2, 14, 11, 12, 2, 1, 3, 1, 1, 5, 1, 5, 20, 19, 4, 1, 22, 6, 12, 18, 3, 24, 34, 1, 15, 9, 2]

コメントからの提案を取り入れた新しい実装

from collections import Counter

def milestones_from_dists(dists):
    dists = Counter(dists)
    right_end = max(dists)
    milestones = [0, right_end]
    del dists[right_end]
    sorted_dists = sorted(dists)
    add_milestones_from_dists(dists, milestones, sorted_dists, right_end)
    return milestones

def add_milestone

s_from_dists(dists, milestones, sorted_dists, right_end):
    if not dists:
        return True # success!
    # find max dist that's not fully used yet
    deleted_dists = [] 
    while not dists[sorted_dists[-1]]:
        deleted_dists.append(sorted_dists[-1])
        del sorted_dists[-1]
    max_dist = sorted_dists[-1]

    # for both possible positions, check if this fits the already placed milestones 
    for new_milestone in [max_dist, right_end - max_dist]:
        used_dists = Counter() # for backing up
        for milestone in milestones:
            dist = abs(milestone - new_milestone)
            if dists[dist]: # this distance is still available
                dists[dist] -= 1
                if dists[dist] == 0: 
                    del dists[dist]
                used_dists[dist] += 1
            else: # no solution
                dists.update(used_dists) # back up
                sorted_dists.extend(reversed(deleted_dists))
                break
        else: # unbroken
            milestones.append(new_milestone) 
            success = add_milestones_from_dists(dists, milestones, sorted_dists, right_end)
            if success:
                return True
            dists.update(used_dists) # back up
            sorted_dists.extend(reversed(deleted_dists))
            del milestones[-1]  
    return False

def steps(milestones):
    milestones = sorted(milestones)
    return [milestones[i] - milestones[i - 1] for i in range(1, len(milestones))]

0 から 100000 までのランダムなマイルストーンのタイミング:

  • n = 10: 0.00 秒

  • n = 100: 0.05 秒

  • n = 1000: 3.20 秒

  • n = 10000: まだ時間がかかりすぎます。

于 2013-06-17T21:45:08.550 に答える