Árbol de expansión mínimo capacitado

Tipo de árbol de expansión

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

Algoritmos

Supongamos que tenemos una gráfica con una raíz . Sean todos los demás nodos en . Sea el costo de las aristas 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 Esaú-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 (gráfico de estrellas) 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 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 -ésimo subárbol mediante un borde . Repetimos las iteraciones hasta que no podamos realizar más mejoras en el á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 tiene cambios: para cada nodo = nodo más cercano en un subárbol diferente = - t_max = max ( ) k = i tal que = t_max if ( costo (i) + costo (j) <= c ) T = T - T = T retorno de la unión 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 encuentra utilizando una versión aleatoria de Esau-Williams. La aleatorización se logra ejecutando una combinación aleatoria uniforme de los mejores en lugar del mejor en cada paso. ${\displaystyle p}$

Barrio de búsqueda local

Sea la solución inicial con root . La vecindad 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 manera 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 no se excede la capacidad 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 eficientemente en un vecindario muy grande. Los caminos a través de un gráfico de mejora corresponden a cambios en una solución y el costo del camino es el cambio en el costo de la solución al aplicar el cambio. Aquí, el gráfico de mejora es un multigrafo dirigido creado utilizando 2 copias de cada nodo y hasta 4 aristas de cualquier nodo a cualquier nodo en un componente diferente de . El borde corresponde al cambio de eliminar el nodo de su componente original y reemplazar el subárbol enraizado en el componente de destino. La combinación de nodos y subárboles produce los 4 posibles bordes. Existe una ventaja si el cambio correspondiente no conduce a que el componente objetivo supere la capacidad. El costo de una arista es la diferencia en el costo de los árboles de expansión mínima en los vértices del componente objetivo antes y después del desplazamiento. Así, 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 longitud creciente y solo se almacenan las más favorables 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 contener las rutas. Dado que en cada ciclo negativo hay un nodo tal que todos los caminos dentro de ese ciclo que contienen este nodo tienen un costo negativo, solo se deben considerar los caminos 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 almacenados como números enteros para la velocidad. Sin embargo, esto se debe claramente a muchas colisiones de hash, lo que podría 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 restricciones de espacio (artículo de 2003).

Actuación

En el momento en que se escribió el artículo (2003), este algoritmo era lo último en términos de referencia de investigación de operaciones estándar. La ejecución estuvo dominada por la construcción (respectivamente actualización) del gráfico de mejora. El número de aristas en el gráfico de mejora se escala empíricamente cuadráticamente 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 enormemente el tiempo de ejecución, ya que esto reduce el número de aristas en el gráfico de mejora.

Aplicaciones

El problema CMST es importante en el diseño de redes: cuando hay que conectar muchas computadoras terminales al concentrador central, la configuración en estrella generalmente no es el diseño de costo mínimo. Encontrar un CMST que organice los terminales en subredes puede reducir el costo de implementar 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. Algoritmos , 1 (2): 265–282, doi :10.1145/1103963.1103967, S2CID  8302085
2. Esaú, LR; Williams, KC (1966). "Sobre el diseño de redes de teleprocesamiento: Parte II. Un método para aproximar la red óptima". Revista de sistemas IBM . 5 (3): 142-147. doi :10.1147/sj.53.0142.
3. Ahuja, RK; Orlín, JB; Sharma, D. (2003). "Una estructura de vecindad compuesta a muy gran escala para el problema del árbol de expansión mínimo capacitado". Cartas de investigación operativa . 31 (3): 185-194. doi :10.1016/S0167-6377(02)00236-5.