Árbol de expansión mínimo capacitado

Tipo de árbol de expansión

Un árbol de expansión mínimo capacitado es un árbol de expansión de costo mínimo de un grafo que tiene un nodo raíz designado y satisface la restricción de capacidad . La restricción de capacidad asegura que todos los subárboles (subgrafos máximos conectados a la raíz por un solo borde) incidentes en el nodo raíz no tengan más de nodos. Si los nodos del árbol tienen pesos, entonces la restricción de capacidad puede interpretarse de la siguiente manera: la suma de pesos en cualquier subárbol no debe ser mayor que . Los bordes que conectan los subgrafos al nodo raíz se denominan puertas . Encontrar la solución óptima es NP-hard . ^[1] ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle c}$

Algoritmos

Supongamos que tenemos un grafo , con una raíz . Sean todos los demás nodos en . Sea el costo de la arista entre los vértices y que forman una matriz de costos . ${\displaystyle G=(V,E)}$ ${\displaystyle n=|G|}$ ${\displaystyle r\in G}$ ${\displaystyle a_{i}}$ ${\displaystyle G}$ ${\displaystyle c_{ij}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{j}}$ ${\displaystyle C={c_{ij}}}$

Heurística de Esau-Williams

La heurística de Esau-Williams encuentra CMST subóptimos que están muy cerca de las soluciones exactas, pero en promedio EW produce mejores resultados que muchas otras heurísticas.

Inicialmente, todos los nodos están conectados a la raíz (grafo en estrella) y el costo de la red es ; cada uno de estos bordes es una puerta. En cada iteración, buscamos el vecino más cercano para cada nodo en y evaluamos la función de compensación: . Buscamos la mayor entre las compensaciones positivas y, si el subárbol resultante no viola las restricciones de capacidad, eliminamos la puerta que conecta el subárbol -ésimo a mediante un borde . Repetimos las iteraciones hasta que no podamos realizar más mejoras al árbol. ${\displaystyle r}$ ${\displaystyle \displaystyle \sum _{i=0}^{n}c_{ri}}$ ${\displaystyle a_{j}}$ ${\displaystyle G-{r}}$ ${\displaystyle t(a_{i})=g_{i}-c_{ij}}$ ${\displaystyle t(a_{i})}$ ${\displaystyle g_{i}}$ ${\displaystyle i}$ ${\displaystyle a_{j}}$ ${\displaystyle c_{ij}}$

Heurística de Esau-Williams para calcular un CMST subóptimo:

función CMST( c , C , r ): T = { , , ..., } mientras tenga cambios: para cada nodo = nodo más cercano en un subárbol diferente = - t_max = max ( ) k = i tal que = t_max si ( costo (i) + costo (j) <= c ) T = T - T = T unión devuelve T ${\displaystyle c_{1r}}$ ${\displaystyle c_{2r}}$ ${\displaystyle c_{nr}}$ ${\displaystyle a_{i}}$  ${\displaystyle a_{j}}$ ${\displaystyle t(a_{i})}$ ${\displaystyle g_{i}}$ ${\displaystyle c_{ij}}$  ${\displaystyle t(a_{i})}$ ${\displaystyle t(a_{i})}$ ${\displaystyle g_{k}}$  ${\displaystyle c_{kj}}$  

Es fácil ver que EW encuentra una solución en tiempo polinomial.

^[2]

La heurística de Ahuja

La heurística de Ahuja ^[3] utiliza una búsqueda local en un gran vecindario de múltiples intercambios a partir de una solución inicial aleatoria y codiciosa .

Solución inicial

La solución inicial se obtiene utilizando una versión aleatoria de Esau-Williams. La aleatorización se logra ejecutando una unión aleatoria uniforme a partir de los mejores en lugar del mejor en cada paso. ${\displaystyle p}$

Búsqueda local de vecindario

Sea la solución inicial con raíz . El vecindario consiste en cualquier combinación de un solo nodo o subárbol (subárboles generales, no como en la introducción de este artículo) que desplaza uno en un componente diferente de tal que la estructura desplazada es el siguiente desplazador, el último desplazador desplaza al primer desplazador, ningún componente original tiene más de un desplazador y la capacidad no se excede en ningún componente resultante. ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle T\setminus r}$

Gráfico de mejora

Un gráfico de mejora es una herramienta para buscar un vecindario muy grande de manera eficiente. Las rutas a través de un gráfico de mejora corresponden a cambios en una solución y el costo de la ruta es el cambio en el costo de la solución al aplicar el cambio. Aquí, el gráfico de mejora es un multigrafo dirigido construido utilizando 2 copias de cada nodo y hasta 4 aristas desde cualquier nodo a cualquier nodo en un componente diferente de . La arista corresponde al cambio de eliminar el nodo de su componente original y reemplazar el subárbol enraizado en en el componente de destino. La combinación de nodos y subárboles produce las 4 aristas posibles. Existe una arista si el cambio correspondiente no lleva a que el componente de destino exceda la capacidad. El costo de una arista es la diferencia en el costo de los árboles de expansión mínimos en los vértices en el componente de destino antes y después del desplazamiento. Por lo tanto, los vecinos en la búsqueda local corresponden a ciclos en el gráfico de mejora que contienen como máximo un nodo de cada componente. ${\displaystyle i',i''}$ ${\displaystyle i\in V(T)}$ ${\displaystyle T\setminus r}$ ${\displaystyle i',j''}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i'}$ ${\displaystyle i''}$

Paso de búsqueda local

El paso de búsqueda local utiliza un enfoque de programación dinámica para encontrar un ciclo de costo mínimo en el gráfico de mejora. Se generan rutas a través del gráfico de mejora con una longitud creciente y solo se almacena la más favorable con el mismo inicio y final, así como los componentes involucrados. Para este fin, se utiliza una tabla hash con la tupla de esas 3 propiedades como clave para almacenar las rutas. Dado que en cada ciclo negativo hay un nodo tal que todas las rutas dentro de ese ciclo que contienen este nodo tienen un costo negativo, solo se deben considerar las rutas con costo negativo. Como la comparación de conjuntos de componentes involucrados entre rutas es una de las operaciones más comunes en el algoritmo, se implementa como una comparación de matrices de bits indicadores almacenadas como números enteros para la velocidad. Sin embargo, esto claramente se debe a una gran cantidad de colisiones hash, que podrían ser una consecuencia de la elección particular de la función hash y la estructura de la tabla, así como del alto factor de carga debido a las restricciones de espacio (documento de 2003).

Actuación

En el momento en que se escribió el artículo (2003), este algoritmo era el estado del arte en un punto de referencia de investigación de operaciones estándar. La ejecución estaba dominada por la construcción (respectivamente actualización) del gráfico de mejora. El número de aristas en el gráfico de mejora escalaba empíricamente de manera cuadrática con el tamaño del gráfico de entrada y, dado que esto determina el número de veces que se debe ejecutar el paso comparativamente complejo de encontrar un árbol de expansión mínimo, este es el factor más crítico. Por lo tanto, se puede concluir que los gráficos de entrada menos densos benefician en gran medida el tiempo de ejecución, ya que esto reduce el número de aristas en el gráfico de mejora.

Aplicaciones

El problema de CMST es importante en el diseño de redes: cuando se deben conectar muchos equipos terminales al concentrador central, la configuración en estrella no suele ser el diseño de costo mínimo. Encontrar un CMST que organice los terminales en subredes puede reducir el costo de implementación de una red.

Referencias

1. Jothi, Raja; Raghavachari, Balaji (2005), "Algoritmos de aproximación para el problema del árbol de expansión mínimo capacitado y sus variantes en el diseño de redes", ACM Trans. Algorithms , 1 (2): 265–282, doi :10.1145/1103963.1103967, S2CID  8302085
2. Esau, LR; Williams, KC (1966). "Sobre el diseño de redes de teleprocesamiento: Parte II. Un método para aproximar la red óptima". IBM Systems Journal . 5 (3): 142–147. doi :10.1147/sj.53.0142.
3. Ahuja, RK; Orlin, JB; Sharma, D. (2003). "Una estructura de vecindad compuesta a muy gran escala para el problema del árbol de expansión mínimo capacitado". Operations Research Letters . 31 (3): 185–194. doi :10.1016/S0167-6377(02)00236-5.