Как получить подмножество минимального веса?

Question

Вот акциз:

Рассмотрим задачу нахождения связного подмножества T с минимальным весом из взвешенного связного графа G. Вес T является суммой всех весов ребер в T. Приведите эффективный алгоритм для вычисления подмножества T с минимальным весом.

Вот что я получил:

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

2. Сначала я отсортирую ребра, поэтому на первом месте будут отрицательные ребра.

3. Я рассмотрю использование алгоритма Крускала, но должно быть с некоторыми изменениями

4. Поскольку я приветствую отрицательные края, я постараюсь добавить как можно больше отрицательных сторон.

5. Кроме того, некоторые положительные ребра могут быть добавлены на тот случай, если не все отрицательные ребра соединены, и им могут понадобиться положительные ребра в качестве мостов.

---

Хорошо, выше мое мышление. Но когда я пытаюсь испачкать руки, я застреваю.

Как я могу всегда записывать возможные минимальные установленные веса?

Например,

{0, 1} с весом -20

{2, 3} с весом -10

если вес {1, 3} равен 11, то, конечно, я не хочу {1, 3}

или если {1, 3} имеет вес 9, то я хочу

С какой структурой данных я всегда могу сохранить минимальный вес и вершины для этого веса?

---

Стоит отметить, что подмножество этого акциза стремится к edges,

Рассмотрим задачу поиска связного множества ребер T минимального веса из взвешенного связного графа G

Это означает, что все вершины все еще должны быть включены.

И это больше, чем MST. Учтите, что если вершина имеет два ребра, одно равно -1, другое - -2. В обычном алгоритме MST будет взят только край -2. Но в этом акцизе необходимо принять и -1, и -2, чтобы еще больше снизить общий вес.

Answer 1

Я думаю, что ваш алгоритм в основном уже верен, но с небольшими изменениями его реализация становится тривиальной.

Во-первых, каждый отрицательный край должен быть включен, чтобы минимизировать полученный вес. Далее рассчитаем количество подключенных компонентов c, Если c=1Готово. В противном случае вам нужно дополнительное c-1 положительные края.

Теперь, когда вы добавляли отрицательные ребра, рассматривайте это уже как процесс алгоритма Крускала. Каждый отрицательный край может объединить пару деревьев в лесу Крускала. Однако вы добавляете отрицательный край, даже если его концы принадлежат одному и тому же дереву в лесу Крускала - в отличие от обычного алгоритма Крускала, где вы добавляете только те ребра, которые объединяют два разных дерева.

После этого этапа у вас есть график c связанные компоненты (они могут больше не быть деревьями). Теперь просто продолжайте алгоритм Крускала как обычно. Обрабатывайте положительные ребра в порядке возрастания, отслеживая количество союзов, которые вы сделали с положительными ребрами. Как только этот номер попадает в c-1Готово.

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

---

Ниже следует некоторый псевдокод:

sort(edges);
c := n;
for edge in edges:
    if edge.weight < 0:
        if find(edge.firstEnd) != find(edge.secondEnd):
            --c;
        unite(edge.firstEnd, edge.secondEnd);
    else:
        if c == 1: break;
        if find(edge.firstEnd) != find(edge.secondEnd):
            unite(edge.firstEnd, edge.secondEnd);
            --c;

Вот unite а также find являются функциями структуры данных с несвязным множеством.