Problema del árbol de expansión mínimo (MST): dado el gráfico conectado G con pesos de borde positivos, encuentre un conjunto de bordes de peso mínimo que conecte todos los vértices.
MST es un problema fundamental con diversas aplicaciones.
Diseño de red
- teléfono, eléctrico, hidráulico, tv cable, computador, vial
La aplicación estándar es para un problema como el diseño de una red telefónica. Tienes un negocio con varias oficinas; desea arrendar líneas telefónicas para conectarlas entre sí, y la compañía telefónica cobra diferentes cantidades de dinero para conectar diferentes pares de ciudades. Quiere un conjunto de líneas que conecte todas sus oficinas con un costo total mínimo. Debería ser un árbol de expansión, ya que si una red no es un árbol, siempre puede eliminar algunos bordes y ahorrar dinero.
Algoritmos de aproximación para problemas NP-difíciles
Una aplicación menos obvia es que el árbol de expansión mínimo puede usarse para resolver aproximadamente el problema del viajante de comercio. Una forma formal conveniente de definir este problema es encontrar el camino más corto que visita cada punto al menos una vez.
Tenga en cuenta que si tiene una ruta que visita todos los puntos exactamente una vez, es un tipo especial de árbol. Por ejemplo, en el ejemplo anterior, doce de los dieciséis árboles de expansión son en realidad caminos. Si tiene un camino que visita algunos vértices más de una vez, siempre puede soltar algunos bordes para obtener un árbol. Entonces, en general, el peso de MST es menor que el peso de TSP, porque es una minimización sobre un conjunto estrictamente más grande.
Por otro lado, si dibuja un camino que se traza alrededor del árbol de expansión mínimo, traza cada borde dos veces y visita todos los puntos, por lo que el peso TSP es menos del doble del peso MST. Por lo tanto, este recorrido está dentro de un factor de dos de lo óptimo.
Aplicaciones indirectas
- Rutas máximas de cuello de botella
- Códigos LDPC para corrección de errores
- Registro de imagen con entropía Renyi
- Aprendizaje de funciones destacadas para la verificación facial en tiempo real
- Reducción del almacenamiento de datos en la secuenciación de aminoácidos en una proteína
- Localidad modelo de interacciones de partículas en flujos de fluidos turbulentos
- Protocolo de autoconfiguración para puentes Ethernet para evitar ciclos en una red
Análisis de conglomerados
El problema de agrupamiento k puede verse como encontrar un MST y eliminar los bordes más caros k-1.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA