Вариант минимального связующего дерева коммивояжера

Question

Я пытаюсь решить следующее графическое упражнение:

В неориентированном взвешенном графе есть V вершин и E ребер. Найдите минимальный вес, необходимый для посещения T(T<=V) вершин, начиная с вершины, помеченной как 0. Кроме того, если между двумя посещенными вершинами есть ребро, его вес устанавливается равным 0.

Это не классическая проблема коммивояжера, поскольку добавлено условие, что при посещении двух вершин вес ребра между ними уменьшается до 0.

Подход к нему с помощью алгоритма минимального связующего дерева Prim решает проблему, если T == V, но, поскольку вам не обязательно посещать все вершины, это не всегда возвращает минимальный вес.

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

Какие-нибудь мысли?

РЕДАКТИРОВАТЬ: Я приведу вам пример. Предположим, у нас есть граф с 4 вершинами, помеченными 0,1,2 и 3. У нас есть следующие ребра (от, до, вес): (0,1,1) (0,2,2) (1,3,4) (2,3,1) Минимальное остовное дерево будет содержать ребра: (0,1,1), (0,2,2) и (2,3,1). С его помощью каждая вершина достижима, начиная с 0. Однако цель упражнения состоит в том, чтобы достичь T числа этих вершин. При этом нам, например, может потребоваться только достичь вершин 2 и 3, что делает ненужным ребро (0,1,1), и, следовательно, общий вес, необходимый для достижения наших целевых вершин, составляет 2+1 вместо 1+2+1.

Answer 1

Похоже, что ваша проблема - это, по сути, проблема дерева Штейнера, которая, как известно, является NP-сложной.

Действительно, у вас есть неориентированный взвешенный граф (V, E). Учитывая T, подмножество V, вы хотите найти дерево с минимальным общим весом, которое покрывает все вершины T.

Вот пример, где самые очевидные жадные идеи не будут работать. Предположим, что наш граф - это вершины и ребра нерегулярного тетраэдра ABCD где AB=BC=CA=5 а также AD=BD=CD=3, Если мы хотим соединить A, B и C вместе, лучшее, что мы можем сделать, это использовать ребра AD, BD а также CD для общего веса 9, Если мы решим не использовать D, мы должны взять по два ребра каждого из длины 5 вместо этого, для общего веса 10, Однако каждое двухвершинное подмножество множества ABC использует один прямой край веса 5 (AB, BC или же CA) и нет ребер для вершины D в оптимальном решении.

(Ой! Точная длина невозможна в трехмерной евклидовой геометрии. Тем не менее, она будет служить примером.)