hola

ÁRBOL DE EXPANSIÓN MÍNIMA

1. HISTORIA:
El MST tiene una historia venerable en la optimización combinatoria. Fue formulado inicialmente por Boruvka en 1926 quien se dice tuvo que aprender de éste durante la electrificación del sur de Moraria donde el proporcionó una solución para hallar la distribución más económica a través de una red de una línea de energía. Desde entonces la formulacióndel MST ha sido aplicada en numerosos problemas combinatorios tales como: problemas de transporte, diseño de redes de telecomunicaciones, sistemas distribuidos y otros. Al mismo tiempo algunos algoritmos de tiempo polinomial fueron desarrollados para su resolución por Prim, Kruskal, Dijkstra y Sollin. Los problemas que son extensiones del MST son generalmente problemas NP-Hard para los cuales noexisten algoritmos de orden polinomial que los resuelvan. Debido a su complejidad se han venido empleando Algoritmos Evolutivos para su solución. Desde varias décadas atrás, se han tratado de encontrar algoritmos eficientes para el problema del Árbol de Expansión Mínima Capacitado -AEMC- conocido también como Capacitated Minimum Spanning Tree, cuya finalidad es encontrar un árbol de expansión mínimaque no viole ciertas restricciones de capacidad definidas. El problema del AEMC cae dentro del dominio de los problemas de optimización, en los cuales se trata de encontrar la mejor de varias soluciones posibles -punto óptimo- dentro del espacio de búsqueda, siendo necesario conocer como medir y saber cuando una solución es buena o mala. Este problema es importante en dos aspectos, por el ladoteórico, el AEMC pertenece al conjunto de problemas definidos como NP-Completos, por lo que dado su complejidad es importante encontrar técnicas estocásticas que encuentren soluciones aceptables en tiempos adecuados, ya que las técnicas determinísticas tienen un comportamiento exponencial y en las técnicas heurísticas conocidas se degrada la calidad de la solución conforme crece el tamaño delproblema. Por el lado práctico, problemas como encontrar la configuración óptima de redes de cómputo, redes de carreteras, o en general problemas de flujo son equivalentes al problema del AEMC.

En el diseño de redes donde se tienen un conjunto de terminales - nodos- y otras fuentes de datos diseminadas sobre un área geográfica, con alguna medida de tráfico esperado entre varias fuentes, surgenpreguntas como: ¿Cuántos concentradores se necesitan? ¿Cómo deber ser conectados? ¿Dónde deben ser colocados?, i.e. que terminales deben ser conectadas a un concentrador en particular (clustering problem). A un nivel más bajo, la pregunta de cómo las terminales asociadas con un concentrador en particular deben ser conectadas (terminal layout problem), puede ser respondida mediante el AEMC. La promesa decalidad, eficiencia y robustez de los AG es una idea que atrae a mucha personas para trabajar con ellos, sobre todo porque los métodos tradicionales son buenos para ciertas clases de problemas específicos, pero cuando un problema no se adapta a tales métodos, encontrar la solución al problema puede ser frustrante. Las técnicas estocásticas, al recorrer el espacio de búsqueda del problema, deben detener un balance adecuado entre las partes de exploración y explotación que se hace
sobre el espacio de soluciones posibles. La exploración nos permite que el algoritmo se mueva sobre todo el espacio de soluciones, con lo que evitamos los mínimos locales. Por otro lado, la explotación nos permite, al encontrar una posible solución óptima, moverse en el espacio circundante a ésta para encontrar laque más se acerque el óptimo en dicho vecindario.
2. ÁRBOL:
▪ Es un grafo en el que existe u único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno.
▪ Es un grafo conexo y sin ciclos.
▪ Es un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.

[pic]

3. ÁRBOL DE MÍNIMA EXPANSIÓN:
Árbol...