送牛奶问题
有一堆客户，每人要一瓶牛奶。你一次最多拿两瓶，城里有几个地方可以补充牛奶。你从其中一个地方出发，给所有客户送奶，最后回到出发点。怎么走才能让总路程最短？
设有 个客户、 个补奶点。对于 undirected 版本，也就是往返距离相同的情况，很容易可以得出一个 的确定性算法。所以对于常数有多项式时间算法。
但是对于 directed 的版本，允许往返距离不同之后，即使只有两个补奶点，我们一直找不到一个确定性多项式时间算法。这个问题我也在不少地方问过不少人，一直没有结果。好多年了😭。
最近在AI帮助下发现这个问题竟然和 exact matching 等价了。所以找不到确定性算法是合理的。
我和 Yichen Yang、Qian Zhang 实际上很多年前就研究了这个问题。最近终于被ISAAC 2026 接收。好多年了，终于完成了。😭