algorithm - 最小化两段路由的最大长度

Question

假设一个平面上有 N 个起点和 N 个有向线段(有起点和终点)。 N条路线是从某个起点到某个路段的起点，然后到路段的终点。路线的长度是从起点到路段起点的距离加上路段的长度。问题是在起点和线段之间找到一个(可能是多个之一)一对一匹配，使匹配中的路径的最大长度最小化。

例子:
X 点:(100 100)
Y点:(200 200)
Z点:(300 300)
S1段:开始(200 230)结束(180 220)
S2段:开始(190 190)结束(400 400)
S3 段:开始 (250 250) 结束 (700 700)
可能的答案之一:
X - S2
Y - S3
Z-S1

我最好的尝试是构建从点 i 到路段 j 的路线长度的 NxN 矩阵，迭代过滤掉该矩阵中的最大元素并应用 Hopcroft–Karp检查由过滤矩阵生成的图是否存在 N 对匹配的算法。这种方法的最坏情况性能为 O(N^2.5)*O(N²)=O(N^4.5)。这个问题有更快的算法吗？

如果所有点的坐标都是整数，并且长度由Manhattan distance定义，那么算法还可以改进吗？ (即所有长度也是整数)？

Answer 1

之后

constructing an NxN matrix of route lengths from point i through segment j

您面临的优化问题称为Bottleneck Assignment Problem .

This stack exchange post讨论了一种在 O(N^2.5*log N) 中运行的“简单”算法。

基本思想是对参数 t 进行二分查找。在每次迭代中，您丢弃成本 > t 的所有配对(矩阵条目)。然后执行二分匹配算法(例如 Hopcroft–Karp )。如果找到完全匹配，则减少 t 的值(减半)，否则增加 t(加倍)。当 t 的可能值不再更改输入时，您可以停止。