f*******h 发帖数: 43 | 1 设计一个pickup dispatching system。 二维矩阵表示地理区域,分布有M个乘客和N辆
车(M>>N),假设乘客位置固定, 让设计一个算法,保证每辆车都拉到一个乘客,并且
所有的pickup所花费的路程和最小。
这道题看着像best meeting point, 不过又不太一样。 大家有什么思路吗? | r********k 发帖数: 258 | 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***s 发帖数: 117 | 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******a 发帖数: 44 | 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 | r*******y 发帖数: 270 | |
|