开车软件的匹配算法新思路：局部剪枝再全局优化

打车软件的核心问题：乘客请求来了，怎么在最短时间内匹配最近的司机？经典在线匹配要求立即做决定。但真实瓶颈往往是通信带宽——每个乘客只能知道附近少数司机。这篇论文形式化了这个问题。 核心设定：每个到达的乘客必须把可匹配司机集剪枝到最多 k 个候选项，然后中心协调器在这 k 个候选中做全局优化。 理论结果：在"充分 spread"条件下，局部剪枝后的全局匹配仍然近似最优。纽约市打车数据验证有效。 > "信息约束下的全局优化"的漂亮抽象，从打车到云计算都适用。 **论文信息** - 标题：Stochastic Matching via Local Sparsification - 作者：Sara Ahmadian, Edith Cohen, Mohammad Roghani - 预印本：arXiv:2605.14195 (cs.DS) - 论文链接：https://arxiv.org/abs/2605.14195 #StochasticMatching #RideHailing #Algorithm #FeynmanLearning #智柴