sábado, 8 de noviembre de 2014

Algoritmo para el problema del árbol de mínima expansión


  1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir se pone una ligadura) al nodo más cercano distinto de éste.
  2. Se identifica el nodo no conectado más cercano a un nodo conectado, y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que se hayan conectado todos los nodos.
Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo todavía debe llevar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se buscan las demás formas de romper los empates hasta el final.

La manera más rápida de ejecutar este algoritmo en forma manual es el enfoque gráfico que se ilustra en seguida.

No hay comentarios.:

Publicar un comentario