Несколько посещений tsp

Question

Неужели кто-нибудь когда-либо сталкивался с решением проблемы «множественного посещения с асимметричной проблемой путешествий»?

Обычная проблема с продавцом (http://en.wikipedia.org/wiki/Travelling_salesman_problem), что стоимость получения от A-> B такая же, как получение от BA, асимметричная версия обрабатывает случай, когда стоимость от A-> B отличается от стоимости B-> A, но у меня есть проблема, когда лучший случай путешествия требует поездки через повторный узел.

Предполагая, что сеть из четырех узлов А, В, С, D, это может быть выражено в виде матрицы расстояний от

{{0,7,99999,2}, {4,0,2,3 }, {99999,2,0, 2}, {1,3,2,0}}

Стоимость при переходе от AB 7 стоимость перехода от B-> A = 4

Лучшим решением будет 5 прыжков в интернет-узле A-> D D-> C C-> D -> D-> B BA Нормальная асимметричная версия не будет возвращать от C обратно к D

Любые предложения

Dave

Answer 1

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