Понимание путей минимакс/максимин (Floyd-Warshall)

Question

Я реализовал алгоритм Флойда-Варшалла, чтобы решить проблему кратчайшего пути Все пары. Теперь я узнал, что могу также вычислить минимаксный или максиминный путь с легкими изменениями. Но я не понимаю, что означает результат (что такое минимаксный путь). Я нашел explanations в Интернете, но меня это смущает.

Minimax - Минимальная задача в графе включает поиск пути между двумя узлами, который минимизирует максимальную стоимость по пути.

Maximin - наоборот, от Minimax - здесь у вас есть проблемы, когда вам нужно найти путь, который максимизирует минимальную стоимость по пути.

Не могли бы вы попросить дать другое объяснение или пример?

Answer 1

Чтобы понять пути максимина (часто называемые узкими дорожками) на графике, рассмотрим следующую проблему. У вас есть дорожная карта страны в виде графика, где каждый узел представляет собой пересечение, и каждый край представляет собой дорогу. Каждая дорога имеет ограничение по весу, и если вы ведете грузовик, который превышает лимит по этой дороге, он сломается. У вас есть грузовик, который вы хотите проехать от какого-либо стартового местоположения до некоторого конечного местоположения, и вы хотите наложить на него максимально возможное количество веса. Учитывая это, какой путь вы должны водить на грузовике, чтобы отправить максимально возможный вес?

Если вы думаете об этой проблеме, для любого пути, который вы принимаете на графике, максимальный вес, который вы можете отправить по этому пути, будет определяться краем на этом пути с минимальной пропускной способностью. В результате вы хотите найти путь от начала до места назначения, край минимальной емкости которого максимизирован. Путь с этим свойством называется дорогой максимина или узким местом и может быть найден с помощью простого набора модификаций алгоритмов кратчайшего пути.

Минимаксный путь представляет собой противоположную идею - путь между двумя точками, который минимизирует максимальную емкость края.

Надеюсь, это поможет!