Я прочитал, что одно из приближений для TSP заключается в следующем:
- Вычислить минимальное связующее дерево (MST)
- Выполнить DFS из MST
Целью решения TSP является то, что каждая вершина посещается ровно один раз. Путешественник начинает с точки «А», и ему нужно посетить все остальные точки на графике и вернуться к точке «А» (иногда этот пункт отсутствует), гарантируя, что каждая точка посещается ровно один раз.
Предположим, что MST 'T' графа G имеет следующий вид:
DFS этого MST - A-B-C-E-D.
Мой вопрос для решения TSP, мне нужен список всех городов (точек), которые должен посетить путешественник. Ясно, что в MST не существует пути от «E» до «D». Как это решит проблему тогда?