kastin 发表于 2019-3-25 19:36
当载客量增多到某个阈值之外，或者车的速度提升到一定程度，这个最优方案就不再是这样了。
这是肯定的
markfang2050 发表于 2019-3-25 19:04
比如99人的速度各异。从1-99km/h就复杂了。
这个可以有满足，比如5km/h开始，依此0.1km/h增加，等你解决啊
速度各不相同的其实也很容易计算，要求每人搭一段路后同时到达终点，同样汽车前进路程必须搭人，就可以计算出最优解。当然这种方法可能会由于某些人走得太快，会得出他们坐车路程是负数，那么把这些人剔除，对余下人使用上面极值条件即可
比如k个步行的人速度分别为vi,汽车速度V,总距离S.设某人搭车距离为xi,那么她花费时间为xi/V+(S-xi)/vi,要求这些表达式关于所有xi相等。而汽车前进总距离为sum{xi},倒退距离必须为sum{xi}-S,可以得出汽车总时间(2sum{xi}-S)/V,这个时间也和前面时间相等。所以k个变量k+1个相等量正好k条方程可以确定唯一解。
如果求解后有某些xi是负数就需要去除对应的人(也就是他们走路即可)再重新求解