Как мне сгенерировать разделы/пары для проблемы китайского почтальона?
Я работаю над программой для класса, которая включает в себя решение проблема китайского почтальона. Наше задание требует только написать программу для ее решения для жестко закодированного графика, но я пытаюсь решить его для общего случая самостоятельно.
Часть, которая вызывает у меня проблемы, порождает разбиения пар для нечетных вершин.
Например, если у меня были следующие помеченные нечетные вершины в графе:
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 ...
Затем для каждого раздела я беру каждую пару и нахожу кратчайшее расстояние между ними и суммирую их для этого раздела. Выбирается разбиение с общим наименьшим расстоянием между его парами, и я затем удваиваю все ребра между кратчайшим путем между нечетными вершинами (найденными в выбранном разделе).
Они представляют собой ребра, которые почтальон должен будет пройти дважды.
Сначала мне показалось, что я разработал соответствующий алгоритм для создания этих разделов:
-
Начните со всех нечетных вершин, отсортированных в порядке возрастания
12 34 56
-
Выберите пару позади пары, которая в настоящее время имеет максимальную вершину
12 [34] 56
-
Увеличьте вторую цифру в этой паре на 1. Оставьте все на слева от выбранной пары одинаковы, и сделать все справа от выбранная пара - оставшаяся числа в наборе, отсортированные по возрастающий порядок.
12 35 46
-
Повторить
Однако это неверно. Например, я понял, что когда я добираюсь до конца, а пара выбора находится в самом левом положении (т.е.):
[16] .. ..
Алгоритм, который я разработал, остановится в этом случае и не сгенерирует остальные пары, которые начинаются [16], потому что нет пары слева от нее, чтобы изменить.
Итак, он возвращается к чертежной доске.
Есть ли у кого-нибудь, кто изучил эту проблему, какие-либо советы, которые могут помочь мне указать правильное направление для создания этих разделов?
Ответы
Ответ 1
Вы можете построить разделы с помощью рекурсивного алгоритма.
Возьмите самый низкий node, в этом случае node 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)]