Exploración inicial del problema
Optimización de una red arbitraria
Como te prometimos, ahora trabajaremos con un cuadro de costos generado al azar, simulando una problemática real cualquiera.
Podrás variar entre 3 y 9 el valor de \(N\), que representa el número de puntos a conectar.
¿Solución inválida?
Es importante aclarar a qué se refiere esta situación.
Si obtuviste
este resultado al trabajar con la escena anterior, o incluso en
alguna de las previas, ya sabes de qué se trata. Si no fue así,
puedes obtenerlo, por ejemplo, si ajustas a 5 el número de
puntos y marcas los siguientes enlaces: AB, BC, CA y DE.
¿Qué pasa?, ¿por qué, a pesar de que todos los puntos están conectados
con algún otro y el número de enlaces es suficiente para unir
todos los puntos, esta configuración no nos es útil para
solucionar el problema?
Después de haber practicado varias veces la búsqueda de la solución óptima, seguramente ya tienes algunas ideas del procedimiento.
- ¿Cuáles son estas ideas o recomendaciones generales?
- ¿Qué pasos te permiten acercarte a la solución óptima?
- ¿Crees que el procedimiento para solucionar este tipo de problemas puede modificarse si en lugar de buscar la suma mínima de costos, nos interesara lo contrario y buscásemos la suma máxima de costos?
- ¿Se te ocurre alguna situación donde el costo máximo, a lo mejor visto como capacidad, voltaje o ganancia, por ejemplo, tenga sentido?
En relación con la última pregunta, en la parte de las matemáticas que se dedica a estudiar este tipo de problemas, la terminología que generalmente se usa en lugar de costo es peso. También a los puntos se les conoce como vértices o nodos y a los enlaces como aristas.
En la siguiente sección estudiaremos algunos conceptos y daremos solución al problema desarrollando un procedimiento general que será aplicable tanto para minimizar como para maximizar la suma de pesos.