Я хочу решить проблему, похожую на TSP (проблема с продавцом). У меня есть N (N> 0, N < 20) узлов, и я должен посетить все узлы. Стоимость между узлами равна. Я могу посетить узел неограниченное время. Я хочу найти более одного пути, и стоимость не имеет ограничений. Скажите мне несколько эффективных алгоритмов об этой проблеме?Алгоритм графика: Подобно TSP
Вот решение, которое работает с взвешенным графиком.
Во-первых, наивное решение, перечисляющее.
Он работает в O(n!), потому что есть гальтонианские пути (n-1)!, и вам нужно O (n), чтобы проверить каждый.
Существует лучше алгоритм, с динамическим программированием в O(n*2^n)
Определить состояние, как следующее: для x узла, и S набор узлов, содержащий x:
w[S][x] = вес самых коротких путь, начинающийся с узла x, и проходит через весь узел в наборе S, а затем заканчивается на 0.
Отметьте, что 0 необязательно относится к категории S.
S = {x} является основной случай: w[S][x] = weight(w,0)
Затем рекурсии формула:
Если S больше, {x}, Итерация по поводу возможного следующего шага y
w[S][x] = min(weight(x,y) + w[S\x][y] for all y in S\x)
Этот алгоритм будет выводить всего один оптимальный путь.
Добро пожаловать в Переполнение стека. Я опубликовал решение, которое работает в 'N * 2^N', намного лучше, чем наивное в' N! ', Поэтому с' N <20' это становится полностью выполнимым. Он выводит один оптимальный путь. Не могли бы вы рассказать о том, что вы имеете в виду, когда пишете «несколько путей»? Вы хотите перечислить все оптимальные пути? – galath