Решение модифицированной задачи коммивояжера (TSP) с использованием networkx

Question

Я пытаюсь решить модифицированную версию TSP. В моей версии допускается многократное посещение города, если путь самый короткий, а также обязательно посещать только подмножество городов, например, вы можете go через другие города, чтобы посетить все подмножество. города, если путь короче, но если нет, другие города можно игнорировать. NetworkX имеет ок. решение для традиционного TSP с использованием dwave_networkx.algorithms.tsp.traveling_salesperson, но у меня есть проблемы с решением этого. Наивный подход может заключаться в том, чтобы найти все возможные комбинации подмножеств городов и проверить, какая из них имеет наименьшую общую длину пути, но это решение будет иметь сложность ^ 2 для попытки каждой комбинации, плюс сложность для поиска кратчайшего пути для каждых двух городов. Итак, что я должен использовать для решения этой проблемы с помощью NetworkX.

Answer 1

Вы можете выбрать путь случайным образом и оптимизировать путь по нему. Как правило, случайным образом назначают путь между двумя узлами. Чем по узлам, попробуйте найти оптимальный путь для n + 2 узлов. A -> B -> C, если есть путь между кратчайшим, тогда попробуйте A -> D -> C --- E, если есть путь между D и E, кратчайшим, чем D -> K -> E, а затем снова итерации A -> D -> F -> E просто это звучит для меня хорошая идея. У меня сейчас нет доказательств, но это может дать вам кратчайший путь. Я надеюсь, что это будет полезно. Удачи.