c++ - minimax算法中的maximum-edge是什么？

Question

我很难从这个维基百科中理解极小极大或极大极小问题 。我不明白的是，这个问题想要什么？它想要从一个节点到另一个节点的最短路径吗？如果不是这个，比什么？什么是最小重量或最大重量？举例说明会非常有帮助。我真正想要的是最大重量的最小值是多少？我不明白最小值和最大值之间的关系。

Answer 1

通过示例进行解释：（源自维基百科示例）

Maldon 和 Feering 之间的极小极大路径是红色的。

这里，所有边之间的最大值为 9。

max(8,9,7,8,9) = 9

不存在所有边的最大值小于 9 的可能路径。

请注意，这不是最短路径，最短路径将是两者之间的直接路径，成本为 10，但 10 > 9，因此这不是极小极大路径。

Answer 2

问题是要找到一条路径上的最小边尽可能大的路径。

因此，如果您有一条路径 P = e1, ..., ek，其中 ei 是边权重，则令 f(P) 为 min(e1, ..., ek)。您应该找到一条路径 P*，以便 f(P*) 尽可能高。

该问题的另一种可能解释：找到一个最大权重 W ，这样如果您从图中删除每条权重 < W 的边，仍然存在从源到目标的路径。在这种情况下，W = f(P*)。