Поиск позиций вех с учетом их попарных расстояний

Ответ 1

Я не могу найти алгоритм для этого, который имеет хорошее худшее поведение. Однако для практического решения может быть полезной следующая эвристика:

• Скажите, что первый ориентир находится в нулевом положении. Вы можете найти последний ориентир. Затем во входном массиве должны появиться все другие ориентиры. Их расстояния до последнего знака также должны появиться.
• Давайте построим график на этих возможных ориентирах.
• Если a и b являются двумя возможными ориентирными позициями, то во входном массиве появляется либо |a-b|, либо хотя бы один из a и b не является ориентировочной позицией. Нарисуйте грань между a и b, если во входном массиве появляется |a-b|.
• Итеративно отфильтровать ориентирные позиции, степень которых слишком мала.

Вы завершаете что-то, что почти проблема клики. Найдите подходящую крупную клику; это соответствует расположению ориентиров. Убедитесь, что это позиционирование действительно приводит к правильным расстояниям.

В худшем случае вы сузили возможные ориентиры к более управляемому набору.

Ответ 2

Ok. Я дам свою идею, которая может уменьшить количество перестановок.

Найти n, просто, вы даже можете запустить обратный факториал https://math.stackexchange.com/questions/171882/is-there-a-way-to-reverse-factorials

Предположение: В настоящее время я понятия не имею, как найти номера. Но я предполагаю, что вы как-то узнали цифры. После нахождения n и элементов мы можем применить это для частичного сокращения вычислений.

Рассмотрим проблему типа

|<--3-->|<--6-->|<--1-->|<--7-->|
A       B       C       D       E

Теперь, как вы сказали, сумма, которую они дадут (в случайном порядке тоже) 3,9,10,17,6,7,14,1,8,7.

Но вы можете взять любую комбинацию (в основном это будет неправильно),

6-3-1-7. (say this is our taken combination)
Now,

6+3 -> 9 There, so Yes    //Checking in the list whether the 2 numbers could possibly be adjacent.
3+1 -> 4 NOT THERE, so cannot
1+7 -> 8 There, So Yes
6+7 -> 13 NOT THERE, So cannot be ajacent

Концепция сердца:

Для того, чтобы 2 числа были смежными, их сумма должна быть в списке. Если сумма отсутствует в списке, то числа не смежны.

Оптимизация:

Итак, 3 и 1 не будут приближаться. И 6 и 7 не будут рядом.

Следовательно, выполняя перестановку, мы могли бы исключить

*31*,*13*,*76* and *67*. Где * - 0 или более цифр, предшествующих или следующих.

i.e вместо попытки перестановки для 4!= 24 раза, мы могли проверить только 3617,1637,3716,1736. т.е. только 4 раза. т.е. 84% вычислений сохраняется.

Худший случай:

Скажем, в вашем случае это 5,2,3. Теперь мы должны выполнить эту операцию.

5+2 -> 7 There
2+3 -> 5 There
5+3 -> 8 There

К сожалению, ваш пример - худший случай, когда мы не смогли оптимизировать решение в таких случаях.

Ответ 3

Поместите этапы по одному

EDIT См. новую реализацию ниже (с таймингами).

Основная идея заключается в следующем:

• Создайте список этапов один за другим, начиная с одной вехи в 0 и вехи в max(distances). Позволяет называть их конечными точками.
• Наибольшее расстояние, которое не учитывается, должно быть от одной из конечных точек, которая оставляет не более двух позиций для соответствующей вехи.

Следующая программа Python просто проверяет, можно ли разместить веху с левой конечной точки, а если нет, попытается поместить веху с правой конечной точки (всегда используя наибольшие расстояния, которые не учитываются уже размещенными вехами). Это нужно сделать с отслеживанием обратных ссылок, поскольку места размещения могут оказаться неверными позже.

Обратите внимание, что есть другое (зеркальное) решение, которое не выводится. (Я не думаю, что может быть более двух решений (симметричных), но я этого не доказал.)

Я рассматриваю положение этапов как solution и использую вспомогательную функцию steps для вывода, требуемого OP.

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 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.00s

• n = 100: 0,05 с

• n = 1000: 3.20s

• n = 10000: все еще занимает слишком много времени.

Ответ 4

Наибольшее расстояние в данном наборе расстояния - это расстояние между первым и последним вехами, то есть в вашем примере 10. Вы можете найти это на этапе O (n).

Для каждой другой вехи (за исключением первого или последнего) вы можете найти их расстояния от первого и последнего этапов, ища пару расстояний, суммируемых до максимального расстояния, т.е. в вашем примере 7 +3 = 10, 8 + 2 = 10. Вы можете найти эти пары тривиально в O (n ^ 2).

Теперь, если вы думаете, что дорога с востока на запад, остается то, что для всех внутренних этапов (всего, кроме первого или последнего) вам нужно знать, какое из двух расстояний (например, 7 и 3, или 8 и 2) находится к востоку (другой - к западу).

Вы можете тривиально перечислить все возможности во времени O (2 ^ (n-2)), и для каждой возможной ориентации проверьте, что вы получаете тот же набор расстояний, что и в задаче. Это быстрее, чем перечисление через все перестановки наименьших расстояний в наборе.

Например, если вы предполагаете, что 7 и 8 находятся на запад, то расстояние между двумя внутренними вехами составляет 1 миля, что не находится в задаче. Таким образом, это должно быть 7 к западу, 8 к востоку, что приводит к решению (или это зеркало).

WEST | -- 2 -- | -- 5 -- | -- 3 -- | EAST

Для большего набора этапов вы просто начнете угадывать ориентацию двух расстояний до конечных точек, и всякий раз, когда вы произведете две контрольные точки, которые имеют расстояние между ними, которое не находится в задаче, вы возвращаетесь назад.