迷失森林----死亡和生存

寒潭清 · 发表于 2006-1-19 06:11:23

有一片神秘的森林，在里面任何人也无法辨识方向。它存在于一个神奇的空间，这个空间是精确的欧几里得空间。它只有一条直线的边界，即，森林拓展为一个半平面。一个受过严格训练的探险者，他对行进方向的控制能力达到了完美的程度。这个探险者打算区森林中寻找传说的上古时代埋藏在森林的众神宝典。一天，他从森林的边界，提升真气至极限，以6400公里/小时的极限速度，垂直飞行进入森林1000公里，然后调转行进方向90度继续行进，这时他的路线是严格与森林的边界平行的。非常幸运的，他终于看到了传说的遗迹，正当他欣喜若狂的揭开被诅咒了的封印，地动山摇，只觉得好像整个空间都似裂开，他头晕目眩，终于昏死过去....不知过了多久，探险者悠悠醒转，可是，非常不幸的，他完全迷失了方向！空间仍在裂变之中，地域之火正慢慢燃烧，他知道，如果不能在1小时内飞出森林，这里就是他的葬身之地！.........现在请问，是否存在一个飞行策略，使他一定能够活着飞出森林？更难点的问题，能否证明你找到的这个策略是最佳的？

大头羊 · 发表于 2006-1-19 07:02:04

这题是谁出的？我服......

husonghu · 发表于 2006-1-19 08:49:57

我做过此题。非常好，推荐。

LOTUSEATER · 发表于 2006-1-19 14:32:10

SMART Q

huxlnn · 发表于 2006-1-20 04:34:19

依据条件，探险者有着完美的飞行控制能力，那么如下的飞行策略或许有效：

选定一个方向（当然是幸运方向）直线飞行1000公里，然后以出发点为圆心做圆圈轨迹的飞行，直到发现森林边界。如图，当探险者直线飞行1000km以后，如果处在大弧BCDE上，则都能在1小时内飞出森林，因为其飞行距离为：1000+3.14*5/6*2000=6230km,飞行时间小于1小时

如果直线飞行后探险者处在小弧BE上，此时如果不借助对环境的判断，仍然有50%的正确选择概率，如果借助对环境的判断，则在小弧BE上则轻易能飞出森林。

此时总的生还概率为：（2/3）*1+（1/3）*（1/2）=5/6

本贴由[huxlnn]最后编辑于：2006-2-9 7:54:33

husonghu · 发表于 2006-1-20 05:30:13

huxlnn,这是一个yes或no的问题，不能谈概率。你的策略(若有的话)使要保证最坏的情况也能逃生

constant · 发表于 2006-1-20 05:46:49

这题找出解不难，证明是最优解很难（有人发表过论文的）

huxlnn · 发表于 2006-1-20 06:07:55

那就换个策略吧

出发点o到线AB距离1000KM,设

r+2*PI*r*(2*PI-α)/(2*PI)=6400,则有2*PI-α+1=6.4*cos(α/2),由此式

确定的角度和r，形成了必然生存的策略

在出发点先直线飞行距离r,然后以出发点为圆心，作圆形飞行，在1小时内必然能飞出森林

本贴由[huxlnn]最后编辑于：2006-2-9 7:56:23

husonghu · 发表于 2006-1-20 06:44:44

huxlnn · 发表于 2006-1-20 10:26:48

那就在此征解吧[:E]

husonghu · 发表于 2006-1-21 00:39:19

呵呵，我是说，你的式子无解(即：这样还得不到逃生策略)

My IQ 159 · 发表于 2006-1-21 05:30:53

I will fly up in the air to see the edge of the space. If I find it, then I will fly toward the right direction

My IQ 159 · 发表于 2006-1-21 06:12:41

Since the space is perfectly flat. So first fly up in the air a little bit, no far than

3121.875

miles, I believe you will see the edge somewhere during the time you are flying up then fly toward the edge you find. It is not like earth, which is round. It is flat. So when you fly over the top of the forrest, you will be able to see the edge.

寒潭清 · 发表于 2006-1-22 14:59:07

参预应该鼓励

bondbond · 发表于 2006-1-23 13:01:58

此题可解,飞行策略如图 O->B->A->C, 其中OAC角度为pi-x.

解释如下:
step 1: 飞行距离d=R+(2pi-2x)R+(R-Rcos(x)<=6400.
可得: cos(x)+2x>=2pi-4.4
进一步: x>=Q, Q大约为0.5016;
step 2: 考虑最坏打算, x几乎等于零, 则BA弧度必须至少为3pi/2, 否则不能回到直线,即2pi-2x>=3pi/2.
step 3: 综合step 1 and 2 可得 0.5016 <= x <= pi/4.

因此,只要所飞行的弧度BA = 2pi-2x满足 3pi/2<= 2pi-x <= 5.28, 就能飞出.

下面我们取特殊情况弧度BA = 3pi/2. 若x>=pi/2, 则在结束BA飞行之前已经可以飞出, 飞行距离小于5712公里; 若0

bondbond · 发表于 2006-1-23 16:43:54

答案如上贴, 敬请检验

husonghu · 发表于 2006-1-23 18:33:10

不错，欢迎你

你的解法和我的有点不一样。我等会给你好好检验一番。

husonghu · 发表于 2006-1-24 07:02:31

你的策略是：R+BA弧+AC直线

最坏情况时：

R=1000
BA弧=(3Pi/2)*1000=4712
AC=1000

Total = 6712

请再仔细想一想。

husonghu · 发表于 2006-1-24 07:07:04

按我的飞行策略，我得出最坏的情况要飞的距离是6397.3公里。解法迟点再给

bondbond · 发表于 2006-1-24 12:07:29

不好意思, 我恰好证明了此方法不行...

huxlnn · 发表于 2006-1-24 13:15:10

好象差距最小总是有0.05km

bondbond · 发表于 2006-1-25 14:30:25

出来了,飞行距离1 + sqrt(3) + 7pi/6 <= d <= 6.4, 不知有否其它策略?

husonghu · 发表于 2006-1-25 18:23:23

我想，从数值上说是对了。但还是需要画出图来让大家看看才能令人信服

bondbond · 发表于 2006-1-25 23:20:54

路线如图OABCD, 此路线可以穿过圆的任意一条切线. 下面证明有解.

列出距离函数:
D (x, y) = R/cos(x) + R*tg(x) + (2*pi - 2*x - y)*R + (R - R*cos(y)) <= 6400;

先求得 D(x, y) 的极值点, 然后可以检验存在(x,y)满足 D(x, y) <= 6400 的约束, 进一步 1 + sqrt(3) + 7pi/6 <= D(x, y) <= 6400. 由于D(x,y) 是一个高度非线性函数,精确的(x,y)解很难得到,但可以得到(x,y) 必须满足 pi/6 <= x, y <= pi/2 (必要条件).

取特殊值 x0 = pi/6, y0 = pi/2,可得最小值 D(x0,y0) = 1 + sqrt(3) + 7pi/6 ~= 6397.2.
其实,还有很多点可以达到最小值, 但难以写出闭式解.

husonghu · 发表于 2006-1-26 03:50:45

我想这是唯一解。从求解的过程(求飞行距离极小值)，可知这是最佳解。

好险哪！只有2.8公里的余额(小于1.6秒的飞行时间)。一切都要精确控制，稍有差错就逃不出来了 ---- 当然是指最坏情况下。

真是一道好题。

寒潭清 · 发表于 2006-1-26 04:11:07

欢迎高手加入

husonghu · 发表于 2006-1-26 16:43:50

图示是最坏情况下飞行全程(粗实线所示)：

Y=OA+AB+弧BC+CD
=1000/cos((Pi/2-x)/2) + 1000*tg((Pi/2-x)/2) + 1000*(Pi+x) + 1000

只有一个变数x

由dy/dx=0, 可得 x=Pi/6

由此, Y=6397.2公里

bondbond · 发表于 2006-1-26 17:26:53

确实, 只有在 x0 = pi/6, y0 = pi/2处达到最小值. 确实是好题, 不知出自何处?

		自动登录	找回密码
密码			立即注册

动态微博

迷失森林----死亡和生存

回复：迷失森林----死亡和生存

我做过此题。非常好，推荐。

SMART Q[>:D<][>:D<]

回复：迷失森林----死亡和生存（图）

huxlnn,这是一个yes或no的问题，不能谈概率。你的策略(若有的话)使要保证最坏的情况也能逃生

这题找出解不难，证明是最优解很难（有人发表过论文的）

换个策略（图）

问题可能没那么简单哦[;)][;)]你能保证你的式子有解吗？[:E][:E][:E]

那就在此征解吧[:E]

呵呵，我是说，你的式子无解(即：这样还得不到逃生策略)[:P][:P]

MY answer might be stupid and please do not laugh

Fly up, look for the edge, then fly to it.

参预应该鼓励 [@};-][@};-][>:D<][>:D<]

回复：迷失森林----死亡和生存（图）

答案如上贴, 敬请检验[;)]

不错，欢迎你[@};-][@};-]你的解法和我的有点不一样。我等会给你好好检验一番。

不行啊！按你的策略，最坏的情况要飞的距离是差不多6712公里。

按我的飞行策略，我得出最坏的情况要飞的距离是6397.3公里。解法迟点再给[;)][;)]

不好意思, 我恰好证明了此方法不行...[:%]

回复：不好意思, 我恰好证明了此方法不行...[:%]

出来了,飞行距离1 + sqrt(3) + 7pi/6 <= d <= 6.4, 不知有否其它策略?

我想，从数值上说是对了。但还是需要画出图来让大家看看才能令人信服[:)][:)]

类似于第一个失败策略 ...（图）

对对对，恭喜[@};-]结果是：C点应在正西，B在东南(-Pi/6)；还必须说明R是1000公里..

欢迎高手加入 [@};-][@};-][>:D<]

结果图示如下.....（图）

回复：迷失森林----死亡和生存