2楼jyuntoku
(......)
发表于 2009-1-14 02:06
显示全部帖子
回复 5#Gemini 的帖子
抛砖引玉,我想了一下,不知道这样是否能说清楚。
我们需要构造一个每一步都是最优的坐车策略来实现甲乙到终点的所需时间最短。并且我们将得出在最优策略下,甲乙必然是同时到终点。我们将发现,这种策略和学校公园之间的距离无关,而且这种最优策略可以生成很多等价的最优策略。所谓等价即指各策略下甲乙到终点时移动的距离除以所需时间即甲乙综合速度是一个定值。
第一步:甲乙同时从起点出发(即甲乙处于同一位置),此时的最佳策略是让甲或乙坐车,让另一方步行。不妨先让甲坐车,回头我们将证明在这一步我们让谁坐车都可以构造等价的最优策略。
第二步:车将甲在某一地点放下,此时的最佳策略是让车返回去接乙,甲继续步行。回头我们将证明在乙赶上甲之前甲不能到达终点,否则将不是最优策略。
第三步:车和乙相遇后,乙坐车去追赶甲。
第四步:如果乙赶上甲时(即甲乙又处于同一位置)尚未到终点的,则回到第一步,继续循环。
接下来,我们证明最优策略下,甲乙必须同时到终点。
1 如果将第一步到第四步反复循环多次,必然有最后一次甲乙同处一个位置后,在甲乙到终点之前他们不再相遇。(因为,起点到终点的距离可以分成任意段,但其中总有最后一段。)
2 我们如果观察最后一次甲乙同处一个位置一直到他们到终点,则发现这是和原问题性质上类似的一个问题。只不过在这个问题中,我们已经根据第一步至第三步得到一个甲乙各坐一次车的最优策略(当然我们还不知道在什么地方把先坐车的那个放下来)。现在我们来解决这个问题,证明在这个问题里最优策略是甲乙同时到终点。
3 考虑在第三步的过程中,甲先到终点,乙之后到。注意在我们在之前的讨论中,甲乙是可以互换的,所以我们不妨再一次在第一步中让甲先上车。那么在相应的第三步中如果乙先到终点则甲乙必然在终点前相遇,和2中我们考察的问题的条件不符。
4 考虑甲到终点S后如果不停下来继续步行,直到乙坐车追上甲(甲乙相遇在S’),则乙必然比原来到终点要多花一点时间t才能追上甲。在这段多花的时间里乙的移动速度是车速(V车)。乙和甲相遇时,他们都比原来的终点又多移动了V车×t的距离。
5 如果我们把甲乙共同通过某段距离除以他们全部通过所需的时间定义为甲乙的综合速度的话,在原终点S到甲乙相遇点S‘这段距离中甲乙的综合速度等于车速V车。
6 而终点S之前的距离中,由于甲乙不可能同时坐车移动,且V车>V甲和V乙,所以之前距离所对应的甲乙综合速度必然小于V车。
7 设原终点之前的距离为S,甲乙到原终点需要的时间为T,4中甲乙多移动的距离为s,所花的时间为t。则S/T<s/t ,可得(S+s)/(T+t)。即如果把(S+s)处设为新的终点,则甲乙的综合速度要优于原终点时的综合速度。所谓综合速度更优即意味着甲乙通过同样距离的时间越短,也就是说这个策略更优。
8,7中证明了甲乙同时到比甲先到更优。而由于之前的讨论,乙不可能比甲先到,所以,甲乙同时到时是最优的策略。其实,如果乙又超过了甲的话,只要把以上所有的证明中甲换成乙,乙换成甲就可以证明同样的结论了。
接下来,我们证明第一步中谁先坐车无关最优策略。
1 其实之前已经反复提到了,以上证明中甲乙是对称的,可以互换。
2 同时甲乙必须同时到终点的结论也说明,整个移动的过程也是可逆的,即可以把录像带回放,一样是可行的最优策略。而在回放中,原来的追赶方就会成为被追赶方,原来的先坐车的就会变成后坐车的,并且同一个内容的录像带正放所需的时间和倒放所需的时间是一样的,即正放策略和倒放策略是等价的。这一点下面还会计算验证。
接下来,我们证明我们的这个最优策略的实现形式可以有很多种,并且每一种都是等价的。
1 我们可以这样来叙述我们得到的最优策略:开始时,让甲或乙任何一方上车,另一方步行,在保证第四步甲乙相遇时未到终点的前提下,任意次地进行第一步至第三步的循环,最后一次循环中我们让甲乙同时到达终点。
2 根据Gemini的计算,我们可以发现,给定甲乙和车三者的速度,以及一段距离(我们只需要考虑最后一次循环开始时甲乙离终点的距离)
,则此次循环中先上车的那方下车的地点是唯一确定的。并且无论甲先上车还是乙先上车,到终点所需的时间相同。
3 我们可以计算出,最后一个循环中甲乙的综合速度是一个定值,它仅取决于甲,乙和车三者的速度,和距离无关(可以作为习题)。
4 我们注意到最后一个循环之前的所有循环本质上都是甲乙从一个共同位置出发各坐一次车(经历第一步到第四步)最后又相遇的过程,所以之前的每个循环甲乙的综合速度和最后的一个循环的综合速度相同。当然,甲和乙的步行距离之比也是相同的。这点可以看Gimini的计算。
5 既然之前每个循环的综合速度都和最后一个循环相同,那么无论总共包括多少个循环,在时间最短方面都是最优的。
[ 本帖最后由 jyuntoku 于 2009-1-14 02:14 编辑 ].