Алгоритм нахождения минимального остовного дерева выбранных вершин

Можно использовать Prim 'Алгоритм или КрускальАлгоритм поиска минимального остовного дерева / графа набора вершин / узлов и ребер / связей. Однако мне нужен алгоритм, который находит минимальный остовный граф этой коллекции, но полученный граф должен включать только произвольно выбранные узлы, а не все узлы. Это'Хорошо, если полученный граф включает больше узлов, чем просто необходимых.

Существует ли такой алгоритм? Возможно, можно просто использовать Prim 'с (или Крускальs) алгоритм после изменения графа для включения только необходимых узлов? Но я'Я не уверен, как изменить график, чтобы сделать это при сохранении его связности.

Например, скажем, у нас есть начальный граф в форме ромба (со стоимостью ссылок в скобках):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

Теперь мы произвольно решаем, что нужны только узлы A и D. Если мы начали в А, мыЯ все еще хочу, чтобы он пошел по левому пути, потому что ((2 + 2) < (1 + 5)).

Скажем, мы немного изменим график:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

Если мы решим, что нужны только узлы A, D и E, мы поймем, что путь с минимальной стоимостью не обязательно является тем, который имеет наименьшее количество ссылок. Взятие A - B - D и A - C - E стоит 7, но A - C - D и C - E стоит 8.

Ответы на вопрос(1)

Решение Вопроса

То, что вы хотите найти, является дискретнымДерево Штейнера, Когда не все вершины в графе являются обязательными, но дерево может разбиваться по необязательным вершинам, проблема NP-трудна.

Википедия говорит (ссылка выше) об этой проблеме:Считается, что сколь угодно хорошие отношения аппроксимации в целом не могут быть достигнуты за полиномиальное время. Существует алгоритм за полиномиальное время, который находит приближение в 1,39 раза минимального дерева Штейнера.

 Tespa4224 нояб. 2012 г., 17:31
Хорошо, я думаю, что я понял. Необязательные узлы являются единственными возможными узлами Штейнера, которые могут использоваться для сокращения длины графа. Я до сих пор нехотя не знаю, насколько приблизительное решение.

Ваш ответ на вопрос