Как я должен генерировать разделы / пары для китайской проблемы Почтальона?

Question

Как я должен генерировать разделы / пары для китайской проблемы Почтальона?

Я работаю над программой для класса, который включает решение китайской проблемы Почтальона. Наше присвоение только требует, чтобы мы записали программу для решения его для трудно кодированного графика, но я пытаюсь решить его для общего случая самостоятельно.

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

Например, если у меня был следующий маркированный нечетный verticies в графике:

1 2 3 4 5 6

Я должен найти все возможные соединения / разделы, которые я могу сделать с этими вершинами.

Я выяснил, что буду иметь i paritions дан:

  n = num of odd verticies  
  k = n / 2  
  i = ((2k)(2k-1)(2k-2)...(k+1))/2^n

Так, учитывая 6 нечетных verticies выше, мы будем знать, что должны генерировать i = 15 разделы.

Эти 15 партонов были бы похожи:

1 2   3 4   5 6
1 2   3 5   4 6
1 2   3 6   4 5
...
1 6   ...

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

Они представляют края, которые почтальон должен будет обойти дважды.

Сначала я думал, что разработал соответствующий алгоритм для генерации этих разделов:

Запустите со всего нечетного verticies, отсортированного в увеличивающемся порядке

12 34 56

Выберите пару позади пары, которая в настоящее время имеет макс. вершину

12 [34] 56

Увеличьте вторую цифру в этой паре на 1. Оставьте все слева от выбранной пары тем же и сделайте все направо от выбранной пары остающимися числами в наборе, отсортированном в увеличивающемся порядке.

12 35 46

Повториться

Однако это испорчено. Например, я понял, что, когда я достигаю в конец и избранная пара является слева большей частью положения (т.е.):

[16] .. ..

Алгоритм, который я разработал, остановится в этом случае и не генерирует остальную часть пар, которые начинаются [16], потому что нет никакой пары слева от него для изменения.

Так, это возвращается к исходной точке.

Кто-либо, кто изучил эту проблему, прежде чем будут иметь какие-либо подсказки, которые могут помочь указать на меня в правильном направлении для генерации этих разделов?

15

algorithm

задан Bill the Lizard 15 September 2012 в 23:23

1 ответ

Другие вопросы по тегам:

algorithm

Похожие вопросы:

score 4 · Accepted Answer

Вы можете построить разделы, используя рекурсивный алгоритм.

Возьмите самый нижний узел, в данном случае узел 1. Он должен быть спарен с одним из других непарных узлов (от 2 до 6). Для каждого из этих узлов создайте с совпадением 1, затем найдите все пары из оставшихся 4 элементов, используя тот же алгоритм для оставшихся четырех элементов.

В Python:

def get_pairs(s):
    if not s: yield []
    else:
        i = min(s)
        for j in s - set([i]):
           for r in get_pairs(s - set([i, j])):
               yield [(i, j)] + r

for x in get_pairs(set([1,2,3,4,5,6])):
    print x

Это генерирует следующие решения:

[(1, 2), (3, 4), (5, 6)]
[(1, 2), (3, 5), (4, 6)]
[(1, 2), (3, 6), (4, 5)]
[(1, 3), (2, 4), (5, 6)]
[(1, 3), (2, 5), (4, 6)]
[(1, 3), (2, 6), (4, 5)]
[(1, 4), (2, 3), (5, 6)]
[(1, 4), (2, 5), (3, 6)]
[(1, 4), (2, 6), (3, 5)]
[(1, 5), (2, 3), (4, 6)]
[(1, 5), (2, 4), (3, 6)]
[(1, 5), (2, 6), (3, 4)]
[(1, 6), (2, 3), (4, 5)]
[(1, 6), (2, 4), (3, 5)]
[(1, 6), (2, 5), (3, 4)]