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

Question

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

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

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

1 2 3 4 5 6

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

Я понял, что у меня будет i разделений:

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

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

15 разделов будут выглядеть так:

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

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

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

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

1. Начать со всех нечетных вершин, отсортированных в порядке возрастания

   12 34 56

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

   12 [34] 56

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

   12 35 46

4. Повторите

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

[16] .. ..

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

Итак, вернемся к чертежной доске.

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

Answer 1

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

Возьмите самый нижний узел, в данном случае узел 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)]