У меня есть полный, взвешенный, неориентированный график. Веса ребер - это стоимость соединения между двумя узлами, поэтому минимальное остовное дерево - это подмножество ребер с наименьшей общей стоимостью, так что граф остается подключенным.
MST должен быть подключен постоянно, но, к сожалению, соединения не очень надежны, поэтому я хотел бы добавить избыточность к этому графику / сети.
Можно ли рассчитать подмножество ребер таким образом, чтобы общая стоимость ребра была минимизирована и подключение по ребру превышает определенный минимум?
Я вижу, как это возможно, используя брутфорс, но я искал что-то более практичное. Я не смог найти много об этой проблеме, я думаю, в основном потому, что у меня нет словарного запаса, необходимого для поиска.
Моя текущая идея:
- Вычислить MST
- Пока он все еще ниже определенного уровня соединения
- Найдите узел, находящийся ниже этой связности
- Активировать ребро этого узла с наименьшим весом
Причина, по которой я не нахожу все узлы ниже определенного подключения одновременно, заключается в том, что активация ребра может дать другому достаточно соединения.
Я почти уверен, что это не приведет к 100% доказуемо оптимальным сетям, потому что с помощью этого метода можно переподключить узлы (например, вы активируете k ребер для узла, затем другой узел активирует больше общих ребер, делая некоторые из тех к избыточны). Я надеюсь, что в этом есть смысл.
Любые советы приветствуются!