Путешественник по ориентированному графику с дополнительными кивками

Question

Я читал о разных алгоритмах для решения проблемы коммивояжера, но не могу найти пример, где вы не хотите посещать все кивки на графике. В примере, скажем, у меня есть граф, состоящий из кивок n1, n2, n3, n4, n5, n6. В классической проблеме коммивояжера я хотел бы посетить все кивки в кратчайшие сроки. Но что, если я хочу уйти из n1 и посетить только n3 n5 и n6. Я могу пройти через другие кивки, если придется, но единственные, которые мне нужно посетить, это n1 n3 n5 n6 и обратно в n1. Это означает, что я ищу самый короткий путь от n1 до n1, который проходит через эти 3 точки. Любой намек на то, какой алгоритм будет выглядеть, будет приветствоваться.

Спасибо

Samuel Benitah

Answer 1

Пусть V множество вершин вы обязаны посетить. Пусть d(u,v) - длина кратчайшего пути от u до v. Для каждой пары вершин u и v в V добавьте кромку от u до v с длиной d(u,v). Пусть этот график равен G, т. Е. G - исходный граф, дополненный этими ребрами. Пусть G_V будет G, ограниченным V. Ваша проблема эквивалентна решению TSP на G_V. Чтобы увидеть это, обратите внимание, что если P является сегментом в оптимальном пути в G, удовлетворяющем вашим ограничениям, так что только его конечные точки (например, u и v) лежат в V, тогда длина P должна быть d(u,v). Если нет, вы можете заменить этот сегмент на кратчайший путь от u до v и улучшить оптимальное решение.