Comprender las rutas minimax/maximin (Floyd-Warshall)

Question

Implementé el algoritmo Floyd-Warshall para resolver el problema de la ruta más corta para todas las parejas. Ahora descubrí que también puedo calcular la ruta minimax o maximin con modificaciones fáciles. Pero no entiendo lo que significa el resultado (qué camino minimax es). Encontré algunos explanations en la web, pero me están confundiendo.

Minimax: Minimax en problemas de gráficos implica encontrar una ruta entre dos nodos que minimice el costo máximo a lo largo de la ruta.

Maximin - al revés de Minimax, aquí tiene problemas donde necesita encontrar la ruta que maximice el costo mínimo a lo largo de una ruta.

¿Podría alguien intentar dar otra explicación o un ejemplo?

Answer 1

Para comprender las rutas maximin (a menudo denominadas rutas de cuello de botella) en un gráfico, considere el siguiente problema. Usted tiene una hoja de ruta de un país como un gráfico donde cada nodo representa una intersección y cada borde representa una carretera. Cada carretera tiene un límite de peso, y si manejas un camión que excede el límite sobre esa carretera, se romperá. Tiene un camión que desea conducir desde una ubicación inicial hasta una ubicación final, y desea colocar la mayor cantidad de peso posible sobre él. Dado esto, ¿qué camino debe manejar el camión para enviar el peso máximo posible?

Si piensa en este problema, para cualquier ruta que tome en el gráfico, el peso máximo que puede enviar a lo largo de esa ruta estará determinado por el borde en esa ruta con la capacidad mínima. Como resultado, desea encontrar la ruta desde el inicio hasta el destino cuyo límite de capacidad mínima se maximiza. La ruta con esta propiedad se denomina ruta máxima o ruta de cuello de botella, y se puede encontrar con un conjunto directo de modificaciones a los algoritmos mot de ruta más corta.

La ruta minimax representa la idea opuesta: la ruta entre dos puntos que minimiza la capacidad máxima de borde.

Espero que esto ayude!