algorithm - minimo - Construya un árbol de expansión mínimo que cubra un subconjunto específico de los vértices

kruskal algorithm

Question

Tengo un gráfico no dirigido, de borde positivo (V, E) para el cual quiero un árbol de expansión mínimo que cubra un subconjunto k de vértices V (el problema del árbol de Steiner).

No estoy limitando el tamaño del árbol de expansión a k vértices; más bien sé exactamente qué k vértices se deben incluir en el MST.

A partir de todo el MST pude reducir los bordes / nodos hasta obtener el MST más pequeño que contiene todos los k .

Puedo utilizar el algoritmo de Prim para obtener todo el MST, y comenzar a eliminar bordes / nodos mientras que el MST del subconjunto k no se destruye; como alternativa, puedo usar Floyd-Warshall para obtener las rutas más cortas de todas las parejas y, de alguna manera, unir las rutas. ¿Hay mejores formas de abordar esto?

Answer 1

Ejecute el algoritmo de Prim en el gráfico restringido ( k , E '' ) donde E'' = {( x , y ) ∈ V : x ∈ k e y ∈ k }). La construcción de ese gráfico toma O (| E |).

Answer 2

El problema que usted indicó es un famoso problema de NP-hard, llamado árbol de Steiner en gráficos . No hay soluciones conocidas en tiempo polinomial y muchos creen que no existen tales soluciones.

Answer 3

Hay mucha confusión pasando aquí. Según lo que dice el OP:

No estoy limitando el tamaño del árbol de expansión a k vértices; más bien sé exactamente qué k vértices se deben incluir en el MST.

Este es el problema del árbol de Steiner en los gráficos. Este no es el problema k-MST. El problema del árbol Steiner se define como tal:

Dada una gráfica ponderada G = (V, E), un subconjunto S ⊆ V de los vértices, y una raíz r ∈ V, queremos encontrar un árbol de ponderación mínimo que conecte todos los vértices en S a r. 1

Como otros han mencionado, este problema es NP-difícil. Por lo tanto, puede usar un algoritmo de aproximación.

Algoritmos de aproximación temprana / simple

Dos métodos famosos son el método de Takahashi y el método de Kruskal (ambos han sido ampliados / mejorados por Rayward-Smith):

• Takahashi H, Matsuyama A: una solución aproximada para el problema Steiner en gráficos. Mates. Jap 1980, 24: 573-577.
• Kruskal JB: en el subárbol de extensión más corto de un gráfico y el problema del vendedor ambulante. En Proceedings of the American Mathematical Society, Volumen 7.; 1956: 48-50.
• Rayward-Smith VJ, Clare A: Al encontrar vértices Steiner. Networks 1986, 16: 283-294.

Aproximación de ruta más corta por Takahashi (con modificación por Rayward-Smith)

Algoritmo de aproximación de Kruskal (con modificación por Rayward-Smith)

Algoritmos de aproximación modernos / más avanzados

En biología, los enfoques más recientes han tratado el problema usando el método de la cavidad, que ha llevado a un método de "propagación de creencias modificada" que ha demostrado una buena precisión en grandes conjuntos de datos:

• Bayati, M., Borgs, C., Braunstein, A., Chayes, J., Ramezanpour, A., Zecchina, R .: Mecánica estadística de los árboles Steiner. Phys. Rev. Lett. 101 (3), 037208 (2008) 15.
• Para una aplicación: métodos del árbol Steiner para la identificación óptima de la subred: un estudio empírico. BMC Bioinformatics. BMC Bioinformatics 2013 30; 14: 144. Epub 2013 30 de abril.

En el contexto de los problemas del motor de búsqueda, los enfoques se han centrado en la eficiencia de conjuntos de datos muy grandes que pueden procesarse previamente en cierta medida.

• G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti y S. Sudarshan. Búsqueda de palabras clave y navegación en bases de datos usando BANCOS. En ICDE, páginas 431-440.
• G. Kasneci, M. Ramanath, M. Sozio, FM Suchanek y G. Weikum. STAR: aproximación de Steiner-tree en gráficos de relación. En ICDE''09, páginas 868-879, 2009