kastin 发表于 2019-3-25 18:57
自己看时间-位移图吧（为了清晰起见，上图只显示了最开始的一部分结果）：
其中下面的黑线为未乘坐车 ...
妙！理解了
搞个程序动态变化。
比如99人的速度各异。从1-99km/h就复杂了。
此问题有一个前提要给数学证明：移动返回98次最优。
不知道利用马尔可夫链是否可以解决？
设最短时间为 H，每人步行时间为 k，则每人搭车时间为(H - k)。
5k + 40(H - K )= 1000 (1)
40H=(99×2-1)×1000-5k*99*2 (2)
由(1),(2)解得H=7885/41
可以想象最优结果必然是大家同时到达终点，而且汽车向前走时都搭人。于是马上推论出所有人坐车的路程相同，而汽车向前路程和向后路程差值固定。然后根据这些信息就可以确定最优解的值了
当载客量增多到某个阈值之外，或者车的速度提升到一定程度，这个最优方案就不再是这样了。
设汽车搭每人走了x公里，所以向前共走了99x,向后走了99x-1000,汽车共走2*99x-1000.每人步行1000-x,其中汽车有一段x距离人没有走路，得出2*99x-1000-x=8(1000-x)
得出x=9000/205,所以时间为(2*99x-1000)/40=192.32小时。
当然最优搭车方法不唯一，汽车搭每人的x公里可以分多段，只要每人搭车总距离相同而且车向前时都搭人即可
王守恩 发表于 2019-3-25 19:34
设最短时间为 H，每人步行时间为 k，则每人搭车时间为(H - k)。
5k + 40(H - K )= 1000 (1)
40H=(99× ...
40H=(99×2-1)×1000-5k*99*2 (2)中*2啥含义？