Запрос коммивояжера

Question

Я читал, что одним из приближений TSP является следующее: - Вычислить минимальное остовное дерево (MST) - Выполните DFS MST

Цель решения TSP - посетить каждую вершину ровно один раз.Путешественник начинает с точки «А», и ему необходимо посетить все другие точки на графике и вернуться в точку «А» (иногда этот пункт отсутствует), гарантируя, что каждая точка будет посещена ровно один раз.

Предположим, что MST 'T' графа G имеет следующий вид:

DFS этого MST - A-B-C-E-D.

У меня вопрос для решения ТСП, мне нужен список всех городов (точек), которые должен посетить путешественник.Ясно, что в MST нет пути от «E» к «D».Как же тогда это решит проблему?

Answer 1

Не имеет значения, нет ли пути от E к D в MST, пока есть путь от E к D в исходном графе.Обычно TSP включает полностью связанный граф.

Дополнительную информацию см. в разделе 2.1 этого документа: http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf