Resolución del problema

Algoritmo de Prim

Es conveniente que sepas que el procedimiento que hemos construido es una versión simplificada del algoritmo de Prim.

La simplificación consiste en que nosotros hemos siempre requerido que el cuadro de costos esté completo, es decir, que siempre haya un costo asociado a la conexión de cada par de puntos. Sin embargo, no es necesario contar con el cuadro completo de costos. Por ejemplo, pensando en la red de antenas, puede ser que un enlace no se pueda instalar porque hay un edificio alto entre dos de los puntos que impide poner las antenas. En este caso el enlace no existe, pero de todas formas tiene sentido pensar en el problema de optimización del resto de la configuración.

En lugar de necesitar que existan los enlaces para conectar los puntos todos con todos, el algoritmo de Prim solo requiere que haya al menos una ruta de enlaces que conecte cualquier par de puntos, es decir, que todos los puntos se encuentren conectados en una sola red. Este algoritmo permite optimizar los costos totales, tanto de forma mínima como máxima.

Espacio de práctica

Este espacio es similar a los que ya conoces. A continuación incluimos un cuadro de costos generados aleatoriamente y la representación gráfica correspondiente. Podrás marcar y desmarcar los enlaces al presionar sobre los puntos anaranjados o sobre los costos del cuadro. Podrás variar entre 3 y 8 el valor de \(N\), que representa el número de puntos a conectar.

El botón Cuadro muestra y esconde el cuadro de costos.
El botón Lista muestra y esconde la lista de costos en orden ascendente.
El botón Solución muestra la solución óptima del problema de minimización de costos planteado.

Si seleccionas un punto para comenzar, o vas avanzando en la construcción de la solución, en la lista se marcarán en verde los enlaces válidos (los que conectan la solución en construcción con el resto del mundo), de los que deberás escoger uno entre los del menor costo disponible (si es que hay varios con exactamente el mismo costo).

Invitación

Una vez que hayas practicado, puedes regresar a la página 3 de la exploración y por fin resolver el problema de la red de fibra óptica con un método infalible.