Постройте минимальное остовное дерево, покрывающее определенное подмножество вершин.

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

Я не ограничиваю размер остовного дерева k вершинами; скорее я точно знаю, какие k вершины должны быть включены в MST.

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

Я могу использовать алгоритм Прима для получения всего MST и начать удаление ребер / узлов, пока MST подмножества k не уничтожается; в качестве альтернативы я могу использовать метод Флойда-Уоршалла, чтобы получить кратчайшие пути для всех пар и как-то объединить пути. Есть ли лучшие способы подойти к этому?


algorithm tree graph-theory graph-algorithm
person atp    schedule 07.10.2011    source источник
comment
Не уверен, что понимаю, но нельзя ли просто запустить свой любимый алгоритм MST на (k,E)?   -  person Mat    schedule 07.10.2011
comment
Хм, чем это отличается от удаления ненужных вершин и запуска Prim (или Kruskal) на оставшихся?   -  person Savino Sguera    schedule 07.10.2011
comment
Я бы подумал о подграфах   -  person sehe    schedule 07.10.2011
comment
Если я удалю ненужные вершины, я также могу потерять промежуточные ребра, соединяющие k вершины, находящиеся далеко друг от друга. Например, если у меня есть: k--o--o--o--k, где o представляет собой ненужную вершину, а k представляет ту, которая мне нужна, если я удалю середину o, не будет возможности построить MST между моими k вершинами.   -  person atp    schedule 07.10.2011
comment
Итак, вас интересует минимальное остовное дерево, которое не обязательно охватывает все вершины, а только вершины в k?   -  person aioobe    schedule 07.10.2011
comment
Точно. MST, который включает как минимум k, а затем как можно меньше всего.   -  person atp    schedule 07.10.2011
comment
@Jasie: тогда вы не можете получить минимальное остовное дерево, потому что подграф не связан.   -  person Fred Foo    schedule 07.10.2011
comment
Привет, не могли бы вы решить вашу проблему? Если возможно, вы можете помочь с псевдокодом / кодом? У меня аналогичная проблема, но график невзвешенный.   -  person phoenix    schedule 14.03.2015
comment
Неясен вопрос, является ли k числом или множеством. Не могли бы вы пояснить?   -  person Palec    schedule 31.12.2015
comment
@ash, не могли бы вы отклонить мой ответ? Как указано в комментариях, алгоритм неисправен, и я хотел бы удалить его, чтобы избежать распространения дезинформации.   -  person aioobe    schedule 07.08.2017
comment
@aioobe done - Я давно не смотрел на это, но знаете ли вы, верны ли другие ответы?   -  person atp    schedule 07.08.2017
comment
Нет, к сожалению, нет. : - /   -  person aioobe    schedule 07.08.2017
comment
Вы можете решить эту проблему, используя реализацию Steiner Graph, представленную в Networkx - networkx.github.io/documentation/stable/reference/algorithms/ steiner_tree(G, terminal_nodes, weight='weight'), а некоторые примеры можно найти в этой теме gis.stackexchange.com/questions/307336/   -  person Timothy Dalton    schedule 04.12.2019

Ответы (3)


arrow_upward
21
arrow_downward

Здесь происходит много путаницы. Основываясь на том, что говорит ОП:

Я не ограничиваю размер остовного дерева k вершинами; скорее я точно знаю, какие k вершин должны быть включены в MST.

Это проблема дерева Штейнера на графах. Это не проблема k-MST. Проблема дерева Штейнера определяется как таковая:

Для взвешенного графа G = (V, E), подмножества S ⊆ V вершин и корня r ∈ V мы хотим найти дерево минимального веса, которое соединяет все вершины в S с r. 1

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

Ранние / простые алгоритмы приближения

Двумя известными методами являются метод Такахаши и метод Крускала (оба из которых были расширены / улучшены Рейвордом-Смитом):

  • Такахаши Х., Мацуяма А: Приближенное решение проблемы Штейнера в графах. Математика. Jap 1980, 24: 573–577.
  • Крускал Дж. Б.: О кратчайшем остовном поддереве графа и проблеме коммивояжера. В трудах Американского математического общества, том 7.; 1956: 48–50.
  • Рейвард-Смит В.Дж., Клэр А. О поиске вершин Штейнера. Сети 1986, 16: 283–294.

Аппроксимация кратчайшего пути Такахаши (с модификацией Рейворда-Смита)

введите описание изображения здесь

Алгоритм аппроксимации Крускала (с модификацией Рейворда-Смита)

введите описание изображения здесь

Современные / более сложные алгоритмы аппроксимации

В биологии более поздние подходы решили проблему с использованием метода полости, который привел к методу «модифицированного распространения убеждений», который показал хорошую точность на больших наборах данных:

  • Баяти, М., Боргс, К., Браунштейн, А., Чайес, Дж., Рамезанпур, А., Зеккина, Р.: Статистическая механика деревьев Штейнера. Phys. Rev. Lett. 101 (3), 037208 (2008) 15.
  • Для приложения: методы дерева Штейнера для оптимальной идентификации подсети: эмпирическое исследование. BMC Bioinformatics. BMC Bioinformatics 2013 30; 14: 144. Epub 2013 30 апреля.

В контексте проблем поисковых систем подходы были сосредоточены на эффективности очень больших наборов данных, которые могут быть предварительно обработаны до некоторой степени.

  • Г. Бхалотия, А. Хулгери, К. Нахе, С. Чакрабарти и С. Сударшан. Поиск и просмотр по ключевым словам в базах данных с помощью БАНКОВ. В ICDE, страницы 431–440.
  • Г. Каснечи, М. Раманат, М. Созио, Ф. М. Сучанек и Г. Вейкум. ЗВЕЗДА: приближение дерева Штейнера в графах отношений. В ICDE’09, страницы 868–879, 2009 г.
person user2398029    schedule 28.01.2016
comment
Спасибо вам большое за это. Этот пост привел меня к хорошей реализации R в пакете SteinerNet - person Daniel Freeman; 18.04.2020

arrow_upward
11
arrow_downward

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

person meh    schedule 24.01.2012
comment
Фактически, дерево Штейнера в графах имеет фиксированный набор из k вершин в качестве входных данных, в то время как OP дает только k и позволяет алгоритму найти набор. Эта проблема называется k -MST и также является NP -жесткий. См. Также проблемы, связанные с MST в Википедии. - person Palec; 31.12.2015
comment
@Palec На самом деле это неправильно. Я не ограничиваю размер остовного дерева k вершинами; скорее я точно знаю, какие k вершин должны быть включены в MST. Эта проблема является проблемой дерева Штейнера. - person user2398029; 28.01.2016
comment
Кроме того, от -1 до @meh, потому что тот факт, что проблема NP-сложная, не означает, что мы не можем получить полезные решения с помощью алгоритмов аппроксимации. Этот ответ не помогает ОП в решении его проблемы. - person user2398029; 28.01.2016

arrow_upward
1
arrow_downward

Запустите алгоритм Прима на ограниченном графе (k, E '), где E' = {(x, < em> y) ∈ V: x ∈ k и y ∈ k < / em>}). Для построения этого графа требуется O (| E |).

person Fred Foo    schedule 07.10.2011
comment
Иногда это может работать нормально, но даже не гарантируется, что E 'подключена - и даже если это так, можно было бы сэкономить сколь угодно большое расстояние, введя точку Штейнера (т. Е. Вершину, не входящую в k ). (Меньше, чем произвольно, если расстояния подчиняются неравенству треугольника, но ничто не говорит, что они должны это делать.) - person j_random_hacker; 21.12.2015
comment
@j_random_hacker заинтересован в размещении альтернативного решения? - person user2398029; 25.12.2015
comment
@ user2398029: Я поддержал ответ Мех (и я не знаю, почему Билл Ящер удалил гораздо более ранний ответ Ади, в котором говорилось в основном то же самое). По сути, это NP-сложная проблема для оптимального решения; если вы гуглите аппроксимацию дерева Штейнера, вы, вероятно, сможете получить некоторые нормальные алгоритмы. - person j_random_hacker; 25.12.2015
comment
@ user2398029: Было бы полезно посмотреть главу 3 этой ссылки из ответа Ади: cc.gatech.edu/fac/Vijay.Vazirani/book.pdf. (Я (повторно) публикую это здесь, так как вижу удаленные сообщения, но я не уверен, какое ограничение для этого предусмотрено.) - person j_random_hacker; 25.12.2015