avl*_*den 9 algorithm combinatorics
假设我有N辆出租车,N个客户等着被出租车接走.客户和出租车的初始位置是随机/任意的.
现在我想将每辆出租车分配给一个客户.
客户都是固定的,出租车都以相同的速度移动.为简单起见,我们假设没有障碍物,出租车可以直线移动到指定的客户.
我现在想要最小化直到最后一个顾客进入他/她的出租车的时间.
是否有标准算法来解决这个问题？我有成千上万的出租车/客户.解决方案不一定是最佳的,只是'好'.
该问题几乎可以建模为标准的"分配问题",可使用匈牙利算法(Kuhn-Munkres算法或Munkres分配算法)解决.但是,我希望最大限度地降低成本最高的分配成本,而不是最小化分配成本的总和.
既然您提到了匈牙利算法，我想您可以做的一件事是使用某种不同的距离度量而不是欧几里德距离，然后对其运行匈牙利算法。例如，不要使用
d = sqrt((x0 - x1) ^ 2 + (y1 - y0) ^ 2)
使用
d = ((x0 - x1) ^ 2 + (y1 - y0) ^ 2) ^ 10
这可能会导致算法严重惩罚大数字，从而限制最大距离的长度。
编辑：这篇论文“几何有助于瓶颈匹配和相关问题”可能包含更好的算法。然而，我仍在阅读它。