Ответ 1
Проблема, о которой вы говорили, является известной проблемой NP-hard, называемой дерево Steiner в графиках. В полиномиальное время нет известных решений, и многие считают, что таких решений не существует.
Построить минимальное связующее дерево, покрывающее определенное подмножество вершин
У меня есть неориентированный граф с положительным краем (V, E), для которого требуется минимальное связующее дерево, покрывающее подмножество k вершин V (проблема дерева Штейнера).
Я не ограничиваю размер связующего дерева до k вершин; скорее я точно знаю, какие k вершин должны быть включены в MST.
Начиная со всего MST, я мог бы обрезать ребра/узлы, пока не получу наименьший MST, содержащий все k.
Я могу использовать алгоритм Prim для получения всего MST и начать удаление ребер/узлов, в то время как MST подмножества k не уничтожается; в качестве альтернативы я могу использовать Floyd-Warshall для получения кратчайших путей всех пар и как-то объединить пути. Есть ли лучшие способы приблизиться к этому?
Ответы
Ответ 2
Здесь много путаницы. На основании того, что говорит OP:
Я не ограничиваю размер связующего дерева до k вершин; скорее я точно знаю, какие k вершин должны быть включены в MST.
Это проблема дерева Штейнера на графиках. Это не проблема k-MST. Проблема дерева Штейнера определяется как таковая:
Учитывая взвешенный граф G = (V, E), подмножество S ⊆ V вершин, и корень r ∈ V, мы хотим найти минимальное дерево весов, которое связывает все вершины в S с р. 1
Как уже упоминалось, эта проблема NP-hard. Поэтому вы можете использовать алгоритм аппроксимации.
Ранние/простые алгоритмы приближения
Два известных метода: метод Такахаши и метод Крускала (оба из которых были расширены/улучшены Rayward-Smith):
- Takahashi H, Matsuyama A: приближенное решение задачи Штейнера в графах. Математика Jap 1980, 24: 573-577.
- Kruskal JB: о кратчайшем охватывающем субтриге графа и проблеме коммивояжера. В трудах Американского математического общества, том 7.; 1956:. 48-50
- Rayward-Smith VJ, Clare A: Об обнаружении вершин Штейнера. Сети 1986, 16: 283-294.
Аппроксимация кратчайшего пути Такахаши (с модификацией Rayward-Smith)
Алгоритм аппроксимации Крускала (с модификацией Rayward-Smith)
Современные/более продвинутые алгоритмы приближения
В биологии более поздние подходы рассматривали проблему с использованием метода полости, что привело к методу "модифицированного распространения верований", который показал хорошую точность в больших наборах данных:
- Bayati, M., Borgs, C., Braunstein, A., Chayes, J., Ramezanpour, A., Zecchina, R.: Статистическая механика деревьев steiner. Phys. Rev. Lett. 101 (3), 037208 (2008) 15.
- Для приложения: методы дерева Штейнера для оптимальной идентификации подсетей: эмпирическое исследование. BMC Биоинформатика. BMC Bioinformatics 2013 30; 14: 144. Epub 2013 Apr 30.
В контексте проблем с поисковой системой подходы сфокусированы на эффективности для очень больших наборов данных, которые могут быть предварительно обработаны до некоторой степени.
- G. Бхалотия, А. Халгери, К. Нахе, С. Чакрабарти и С. Сударшан. Поиск и поиск ключевых слов в базах данных с использованием BANKS. В ICDE, стр. 431-440.
- G. Каснеци, М. Раманат, М. Социо, Ф. М. Суханек и Г. Вайкум. STAR: приближение Штайнера-дерева в графах отношений. В ICDE09, страницы 868-879, 2009
Ответ 3
Выполнить алгоритм Prim на ограниченном графе (k, E '), где E' = {(x, y) ∈ V: x ∈ k и y ∈ k}). Построение этого графа принимает O (| E |).