Минимальный связанный подграф, содержащий заданный набор узлов

Ответ 1

Я не могу придумать эффективный алгоритм для поиска оптимального решения, но, предполагая, что ваш входной граф плотный, следующее может работать достаточно хорошо:

• Преобразуйте свой входной график G(V, E) в взвешенный график G'(N, D), где N - это подмножество вершин, которые вы хотите покрыть, а D - расстояния (длины пути) между соответствующими вершинами в оригинале граф. Это приведет к "краху" всех вершин, которые вам не нужны в ребрах.

• Вычислить минимальное остовное дерево для G'.

• "Разверните" минимальное связующее дерево следующей процедурой: для каждого ребра D в минимальном остовном дереве возьмите соответствующий путь в графе G и добавьте все вершины (включая конечные точки) на пути к результирующему набору V' и всем ребрам в пути к результирующему набору E'.

Этот алгоритм легко отключить, чтобы дать субоптимальные решения. Примерный случай: равносторонний треугольник, в котором есть вершины по углам, в серединах сторон и в середине треугольника, а также по краям по бокам и от углов до середины треугольника. Чтобы покрыть углы, достаточно выбрать одну среднюю точку треугольника, но этот алгоритм может выбрать стороны. Тем не менее, если граф плотный, он должен работать нормально.

Ответ 2

Это точно известная проблема NP-hard

Ответ 3

Самые простые решения будут следующими:

a) на основе mst:  - изначально все узлы V находятся в V '  - построить минимальное связующее дерево графа G (V, E) - называть его T.
 - loop: для каждого листа v в T, который не находится в N, удалите v из V '.
 - повторить цикл до тех пор, пока все листья в T не будут в N.

b) другое решение заключается в следующем - на основе дерева кратчайших путей.
 - выберите любой node в N, назовите его v, пусть v - корень дерева T = {v}.  - удалить v из N.

• цикл: 1) выберите самый короткий путь из любого node в T и любой node в N. кратчайший путь p: {v,..., u}, где v находится в T и u находится в N.  2) каждый node в p добавляется к V '.  3) каждый node в p и в N удаляется из N. --- повторить цикл до тех пор, пока N не станет пустым.

В начале алгоритма: вычислить все кратчайшие пути в G, используя любой известный эффективный алгоритм.

Лично я использовал этот алгоритм в одной из моих работ, но он более подходит для распределенных окружений. Пусть N - это множество узлов, которые нам нужно связать. Мы хотим построить минимально связанный доминирующий набор графа G, и мы хотим выделить приоритет для узлов в N. Каждому node u присваивается уникальный идентификатор id (u). Будем обозначать w (u) = 0, если u лежит в N, иначе w (1). Мы создаем пару (w (u), id (u)) для каждого node u.

• каждый node u строит мультимножество реле node. То есть, множество M (u) 1-ходовых соседей, так что каждый сосед 2-х хопа является соседним по меньшей мере с одним node в M (u). [минимум M (u), тем лучше решение).

• u находится в V 'тогда и только тогда, когда: u имеет наименьшую пару (w (u), id (u)) среди всех ее соседей. или u выбрано в M (v), где v является соседом по 1-хому u с наименьшим (w (u), id (u)).

- трюк, когда вы выполняете этот алгоритм централизованным образом, должен быть эффективным при вычислении соседей по 2-х хопа. Лучшее, что я мог получить от O (n ^ 3), - это O (n ^ 2,37) с помощью матричного умножения.

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

Мне нравится эта ссылка для эвристики дерева steiner: Проблема дерева Штейнера, Хван Фрэнк; Ричардс Дана 1955 - Зимний Павел 1952

Ответ 4

Вы можете попробовать сделать следующее:

• Создание минимального вершинного покрытия для нужных узлов N.

• Свернуть эти, возможно, несвязанные подграфы в "большие" узлы. То есть для каждого подграфа удалите его из графика и замените его новым node. Вызовите этот набор узлов N'.

• Сделайте минимальное вершинное покрытие узлов в N'.

• "Распакуйте" узлы в N'.

Не уверен, дает ли вам приблизительное значение в какой-то определенной области или около того. Возможно, вы даже можете обмануть алгоритм, чтобы сделать некоторые действительно глупые решения.