财经社区女性社区汽车社区军事社区文学社区社会社区娱乐社区游戏社区个人空间
上一主题:梁生!请您解释一下何为“环境”。 下一主题:论坐标时间与物理时间——回jiug...
公布小鹿出逃问题的答案
[楼主] 作者:清华小猪  发表时间:2004/02/18 15:14
点击:395次

一头小鹿在一圆形湖泊中嬉水,忽然岸边出现一头恶狼。

设:

(1)狼不会游泳,在岸上绕湖奔跑一圈时间为T

(2)小鹿游泳速度为狼奔跑速度的K倍

(3)小鹿上岸后比狼跑得快


求:

(1)狼和小鹿各自的最佳行动策略

(2)K至少为多大,才能保证小鹿总能安然上岸逃走

(3)若小鹿能逃走,则至多用多少时间可确保安全上岸

--------------------------------------------------

解答:

先定义

R:湖半径;u:小鹿游泳速度;v:狼奔跑速度;

K圆:以湖心为圆心,半径为KR的圆周,小鹿在该圆上运动时角速度与狼相等

半K圆:通过湖心,半径为KR/2的圆周,小鹿在该圆上运动时角速度与狼相等

半K圆族:所有半K圆的集合

r圆:以湖心为圆心,以r为半径的圆周

狼心线:湖心与狼的连线

鹿心线:湖心与鹿的连线

角距离:以狼心线为角的始边,以狼前进方向为角的正方向,以鹿心线为角的终边形成的夹角

纳什均衡策略:在这样的策略下,任何一方主动改变行动都不会让自己取得更好结果或迫使对方接受更差结果

安全优先策略:是这样的一种纳什均衡策略,小鹿登岸时离狼最远;如果登岸时与狼的距离相同,则用时最少

时间优先策略:是这样的一种纳什均衡策略,小鹿安全上岸但用时最少;如果用时相同,则登岸时离狼最远 

如果K≥1则解很平凡,以下只讨论K<1但小鹿能够安全上岸的情形。

引理一 纳什均衡策略下,任何时候狼和鹿的角距离≤π

引理二 无论安全优先策略还是时间优先策略,对小鹿而言,r圆上角距离大的起始点总是不劣于角距离小的起始点

引理三 无论安全优先策略还是时间优先策略,对小鹿而言,角距离为零时距狼远的起始点总是不劣于距狼近的起始点

引理四 纳什均衡策略下,角距离∈(0,π)的区域内的小鹿轨迹必是直线(即曲线轨迹或变向必在角距离为π或0时发生)

    推论一 纳什均衡策略下,小鹿的轨迹只能由直线段和半K圆弧组成;如果含有半K圆弧,则直线段与半K圆弧相切

    推论二 纳什均衡策略下,小鹿在K圆外的轨迹必是直线段

引理五 纳什均衡策略下,如果某一时刻角距离为零,则该时刻之前的小鹿轨迹必是沿径向的直线段

引理六 安全优先策略下,小鹿上岸前的一段轨迹必是K圆切线的一部分

限于篇幅和难以附图,以上引理不作证明,由读者自行求证,所定义的概念在求证时很有用。而且本题太过复杂,仅给出求解的纲要已经够花篇幅了。因此以下的答案也不给出证明,留给有兴趣的读者吧。部分证明已经在前面的帖子中出现了。

问题一贯穿在问题二、三的解决中,不能单独解。

先解问题二,这是一个安全优先策略。根据引理二和引理三,小鹿最不利的起始位置就是与狼的角距离为零,与狼的直线距离无限接近零。

最不利起始位置下的安全优先策略是:小鹿径直游向湖心,然后在向外移动过程中保持与狼的角距离恒为π,不难证明这段轨迹正好是半K圆。通过半K圆到达K圆后沿切线出逃(既是K圆切线也是半K圆切线)。而狼的策略则是在小鹿到达湖心前不动,在小鹿到达湖心后任选一个方向一直不变地追击。

令狼刚好同时到达登岸点,可得到临界K值(Kc),满足

tanθ=π+θ

Kc=cosθ

小鹿总能安全逃脱的K值满足

K>Kc

当K>Kc时,小鹿从任意起始位置出发的安全优先策略为:

如果在K圆外并能沿K圆切线逃脱,则沿该切线出逃为完全优先策略;

否则从起始点作半K圆族的切线,如果其中一条切线满足:狼从角距离小于π的方向一直追击,小鹿沿该切线到达切点时,刚好角距离为π,则该切线为小鹿的安全优先策略的第一部分,到达切点后则沿与之相切的半K圆运动,直到到达K圆,然后切向出逃。

如果没有一条切线满足前述要求,则安全优先策略的第一部分为径直游向湖心(其实这里也可以看成是角距离为π的特例),然后沿着保持与狼的角距离为π的半K圆运动,余下部分如前。

接下来解问题三。这是一个时间优先策略。小鹿最不利的起始位置与问题二相同。假定K>Kc。

当Kc<K<1/π时,时间优先策略为:小鹿直接游向湖心,到达湖心后沿着半K圆运动,保持与狼的角距离恒为π。在沿半K圆运动的过程中如果某一时刻沿该半K圆切线游到岸边,狼刚好同时到达,则该切线为临界出逃线。只要在半K圆上多游一个任意小的距离就可改沿切线出逃,刚好安全上岸。所花时间Tc是K和T的函数。

Tc的最大值就是K=Kc时取得的,这个Tc是保证逃脱时间的一致上界。本文只给出这个一致上界,而不给出任意K时的较小的特定上界(读者可自行求解)。

Tc=(R+πKR/2)/u=R(1+πK)/u=R/v(1+πK)/K=T(1+Kπ)/(2πK)=[1+1/(πKc)]T/2

当K>1/π时,时间优先策略上不包括沿半K圆的运动。这时的时间优先策略为:

沿半径向湖心运动,在这过程中一直测试能否刚好沿着这样一个角以直线路径安全逃到岸上,这个角是以小鹿所在半径为起始方向,大小为小鹿所在瞬时位置对K圆直径的张角,称为“最优角”(总是大于π/2)。当K=1/π时,这个刚好能逃掉的位置就是湖心,这时小鹿对湖心的张角为π,最优角就是与走过的半径为π的夹角,正好就原来半径反向沿长为直径的射线。

而狼的对应策略则是在小鹿向湖心运动时不动,在其改向沿最优角射线出逃时追击。

以上是从最不利位置出发的时间优先策略,从任意位置出发的时间优先策略就不解了,还是留给有兴趣的读者。

我出此题时宣布在一周后公布答案,总得有个交待,故写了此帖。但完整而严格的解析这道题恐怕得写一本小书。

到此暂告一段落吧。如果有人能有更简洁的解法,尤其是用泛函来解,本人将非常感兴趣。

本帖地址:http://club.xilu.com/hongbin/msgview-950451-43578.html[复制地址]
上一主题:梁生!请您解释一下何为“环境”。 下一主题:论坐标时间与物理时间——回jiug...
 [2楼]  作者:醉放先生  发表时间: 2004/02/18 19:14 

此问题及其解答值得收藏。博弈只看过一些初步,有时间真想认真看看。


※※※※※※

醉放先生>

[楼主]  [3楼]  作者:清华小猪  发表时间: 2004/02/19 22:33 

更正:计算临界脱逃时间时漏加了最后的切线运动时间。策略和路径没问题。

Tc=(R+πKcR/2+sqrt(R2-(KcR)2)/u=R(1+πKc+sqrt(1-Kc2))/u=T(1+πKc+sqrt(1-Kc2))/(2πKc)

原帖漏掉了根号部分。

精彩推荐>>

  简捷回复 [点此进入编辑器回帖页]  文明上网 理性发言
 推荐到西陆名言:
签  名:
作  者:
密  码:
游客来访 
注册用户 提 交
西陆网(www.xilu.com )版权所有 点击拥有西陆免费论坛  联系西陆小精灵

0.1507260799408