Minimax / Maximin 경로 이해 (Floyd-Warshall)

Question

FLOYD-Warshall-Algorithm을 구현하여 모든 쌍 짧은 경로 문제를 해결했습니다.이제는 MiniMax 또는 Maximin 경로를 쉽게 수정할 수 있습니다.그러나 결과가 의미하는 것을 이해하지 못합니다 (MiniMax 경로는 무엇인지).나는 웹에서 설명

minimax - 그래프 문제의 미니 맥스는 경로를 따라 최대 비용을 최소화하는 두 노드 간의 경로를 찾는 것입니다.

maximin - Minimax의 다른 방법 - 여기에서는 경로를 따라 최소 비용을 최대화하는 경로를 찾아야하는 문제가 있습니다.

다른 사람이 다른 설명이나 예제를 시도 할 수 있습니까?

Answer 1

To understand maximin paths (often called bottleneck paths) in a graph, consider the following problem. You have a road map of a country as a graph where each node represents an intersection and each edge represents a road. Each road has a weight limit, and if you drive a truck that exceeds the limit over that road it will break. You have a truck that you want to drive from some start location to some end location, and you want to put the maximum possible amount of weight on it. Given this, what path should you drive the truck in order to send the maximum possible weight?

If you think about this problem, for any path that you take in the graph, the maximum weight you can send along that path is going to be determined by the edge on that path with the minimum capacity. As a result, you want to find the path from the start to the destination whose minimum-capacity edge is maximized. The path with this property is called the maximin path or bottleneck path, and can be found with a straightforward set of modifications to mot shortest-path algorithms.

The minimax path represents the opposite idea - the path between two points that minimizes the maximum edge capacity.

Hope this helps!