Algoritmo de PRIM
Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956.
PASOS PARA USARLO
La idea básica consiste en añadir en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:
Paso 1: se elige un vértice u de G y se considera el árbol s= {u}
Paso 2: se considera la arista e de mínimo peso que une un vértice de s y un vértice que no es de s y se hace s=s+se
Paso 3: si el n° de aristas de t es n-1 el algoritmo termina. En caso contrario se vuelve al paso
OBJETIVO DEL ALGORITMO
Encontrar el árbol recubierto más corto
¿CÓMO FUNCIONA?
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima . Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar
No hay comentarios.:
Publicar un comentario