求问一道U家的算法设计题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求问一道U家的算法设计题

求问一道U家的算法设计题# JobHunting - 待字闺中

f*h2016-12-10 08:12

1 楼

设计一个pickup dispatching system。二维矩阵表示地理区域，分布有M个乘客和N辆
车(M>>N)，假设乘客位置固定，让设计一个算法，保证每辆车都拉到一个乘客，并且
所有的pickup所花费的路程和最小。
这道题看着像best meeting point，不过又不太一样。大家有什么思路吗？

r*k2016-12-10 08:12

2 楼

my feeling is there is no solution to find the answer. they may test you how
you approach the question, and work out a good enough solution.

b*s2016-12-10 08:12

3 楼

这个需要问清楚有什么条件吧
不然不是就找到最近的乘客拉上吗？如果两辆车有冲突，就去找下一个最近的
有点MST的样子，但只是minimum spanning
可能解决冲突，得到最小的路程是难点，需要弄个 DP来
再具体点，我的想法就是有车1 c1, 车2 c2, 对应人1 r1, 人2 r2, 人3 r3,
(c1, r1) = 1
(c1, r2) = 4
(c1, r3) = 7
(c2, r1) = 2
(c2, r2) = 7
(c2, r3) = 7
大家都是对人1最近，但是显然应该车1接人2,而车2去接人1

k*a2016-12-10 08:12

4 楼

这个题需要更多交流。
同一时间，一辆车只能pick一个客人?
每次计算，限制条件都是N辆车pickN个客人的最小COST，是这样么？
笨笨的思路:
1. 按照每辆车计算最近的TOP N candidates，按照距离排序
2. 按照最小距离排序所有车辆
3. 扫描每辆车的candidates并记录，如果candidate未assigned，assign，如果已经
assigned， try next candidate
4. 如果某车所有candidates都被assigned, 放入set S
5. 如果处理结束S不为空，则重复1，2，3，4