Является ли это вариантом задачи коммивояжёра или другими алгоритмами следующей задачи:
Скажем, G — неполный неориентированный взвешенный граф. V — подмножество вершин G.
Как найти простой замкнутый контур вдоль V (и, возможно, некоторых других вершин G), который имеет минимальный вес между любыми двумя вершинами V.
Спасибо
---------------------- редактировать ------------------------
Есть ли название или опубликованный документ или соответствующая исследовательская работа по этой проблеме?
Во-первых, поскольку V (который, как вы утверждаете, является подмножеством вершин G) сам по себе является взвешенным графом, сначала вычислите ребра V, чтобы вы могли игнорировать G.
Например, этот ввод G:
G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)
Можно упростить до этого ввода V:
Va -- 15 meter --> Vb
Самое интересное начинается, когда у вас есть входные данные с несколькими путями между вершинами V (без других вершин V между ними):
G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)
G1 (Va) -- 7 meter --> G4 (no V) -- 7 meter --> G3 (Vb)
Тогда упрощенная форма (она идет по второму маршруту):
Va -- 14 meter --> Vb
Используйте алгоритм Дейкстры во время этого упрощения.
Во-вторых, примените хороший алгоритм TSP к V. Он NP-полный, поэтому идеального алгоритма не существует. Существует множество доступных фреймворков в зависимости от вашего языка программирования (java, C/C++, ...).
