algorithm - 了解极小极大/极大极小路径 (Floyd-Warshall)

Question

我已经实现了 Floyd-Warshall 算法来解决全对最短路径问题。现在我发现我还可以通过简单的修改来计算 minimax 或 maximin 路径。但是我不明白结果是什么意思(极小极大路径是什么)。我找到了一些 explanations在网络上，但他们让我感到困惑。

Minimax - Minimax in graph problems involves finding a path between two nodes that minimizes the maximum cost along the path.

Maximin - the other way around from Minimax - here you have problems where you need to find the path the maximizes the minimum cost along a path.

有人可以尝试给出其他解释或示例吗？

Answer 1

要理解图中的最大最小路径(通常称为瓶颈路径)，请考虑以下问题。您有一个国家/地区的路线图作为图形，其中每个节点代表一个十字路口，每条边代表一条道路。每条道路都有重量限制，如果您驾驶的卡车超过该道路的限制，它就会坏掉。你有一辆卡车，你想从某个起始位置开到某个结束位置，你想给它施加最大可能的重量。鉴于此，您应该沿着什么路径驾驶卡车以发送最大可能的重量？

如果您考虑这个问题，对于您在图中采用的任何路径，您可以沿该路径发送的最大权重将由该路径上容量最小的边决定。因此，您想要找到从起点到终点的最小容量边最大化的路径。具有此属性的路径称为最大最小路径或瓶颈路径，可以通过对 mot 最短路径算法的一组直接修改找到。

极小极大路径代表了相反的想法——两点之间的路径使最大边缘容量最小化。

希望这对您有所帮助!