一道越野赛跑问题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#1

发表于 2010-5-1 09:34 资料主页文集短消息只看该作者

一道越野赛跑问题

小明即将参加越野赛跑，需要穿越平原、草地、荒地、山地等n种地形，他在各种地形上的速度分别为v1, v2, ... ,vn。每种地形都是矩形，宽度无限，纵向距离分别为w1, w2, ..., wn。穿越时还需要横向移动，即在下图中从A移动到B，横向距离为s。

----------------------B
山山山山山山山山
山山山山山山山山
------------------------
荒荒荒荒荒荒荒荒
荒荒荒荒荒荒荒荒
------------------------
草草草草草草草草
草草草草草草草草
------------------------
平平平平平平平平
平平平平平平平平
A-----------------------

由于在各种地形中的速度不同，时间最短的路径不是从起点到终点的直线，而是在各个地形中的直线连接起来构成的折线。求最短时间。

这题是编程题，用代数式是没法解的，列出方程或者给出思路就可以了。

[ 本帖最后由周瑜于 2010-4-30 21:51 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#2

发表于 2010-5-1 09:46 资料个人空间短消息只看该作者

问：宽度无限与后面的横向距离为s 有没有矛盾

另，斜向移动是否要向英杰传那样分成横向和纵向移动？

[ 本帖最后由阿尔法孝直于 2010-5-1 09:47 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#3

发表于 2010-5-1 09:57 资料主页文集短消息只看该作者

虽然宽度无限，但是所使用的仅仅是AB两点中间宽度为s的一段，如果跑到外面去再跑回来，显然比在这个范围内跑所花时间长。

任何时刻，小明所在位置都是一个点，而不是一个面，勿与英杰传混淆。虽然地形名称取自英杰传，但本题与英杰传毫无关系。

斜向移动的距离是勾股定理的弦长，除以该段的速度就是时间。而在每一段地形中的路线都是一条直线。

[广告] 真诚支持说岳，携手共创辉煌


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#4

发表于 2010-5-1 10:10 资料个人空间短消息只看该作者

设A(0,0)，B(s,∑w)，各个分界点为P1(u1,w1)，P2(u2,w2)，……，P[n-1](u[n-1],w[n-1])，Pn(un,wn)，其中Pn与B重合，设穿过各个地形所花时间为t1,t2,……,tn，则
√(u1^2+w1^2)=v1t1，
√(u2^2+w2^2)=v2t2，
……
√(u[n-1]^2+w[n-1]^2)=v[n-1]t[n-1]，
√(un^2+wn^2)=vntn，

最后是求合适的u1,u2,……,u[n-1],un，其中∑u=s，使得

∑t=(√(u1^2+w1^2))/v1+(√(u2^2+w2^2))/v2+……+(√(un^2+wn^2))/vn
最小。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#5

发表于 2010-5-1 10:30 资料个人空间短消息只看该作者

这题很想用递归二分来做，但不知怎么下手。

[广告] 真诚支持说岳，携手共创辉煌


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#6

发表于 2010-5-1 11:25 资料文集短消息只看该作者

我的理解：s和各段横向偏移都在实数里取值吧？
我的思路是：
记第k段的侧向位移为sk，容易证明达到最小值时所有sk符号（方向）相同
根据折射定律，或各段的时间关于相应sk的导数相等（否则可以调整出时间更短的解）
得到 vk * sqrt( 1 + (wk/sk)^2 ) = C, k=1,2,...,n (*)
其中C是一个常数

将(*)式代入“sk的和为s”的等式，可以得到形如"f(C)=s"的等式
而且容易证明f是严格单调的
所以对给定vk,wk，用爬山法就可以求出C的数值解
然后就可以计算出各sk
精度控制可以根据(*)式来做

这个方法：
1. 没法求形式解
2. 没法求精确解
まあ，两个方面本来就是相联系的...

[ 本帖最后由 muzhi 于 2010-5-1 11:33 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#7

发表于 2010-5-2 05:53 资料主页个人空间短消息只看该作者

从A横向移动距离为x1, x2, ..., xn,

最小化 sum{i=1..n} (x(i)^2+w(i)^2)^(1/2)/v(i)
满足
sum{i=1..n}x(i) = s，
x(i) >= 0, i=1..n.

用求最小化的软件解。没有的话，可以用loop求近似解。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#8

发表于 2010-5-2 14:00 资料个人空间短消息只看该作者

----------------------B
山山山山山山山山
山山山山山山山山
------------------------
荒荒荒荒荒荒荒荒
荒荒荒荒荒荒荒荒
------------------------
草草草草草草草草
草草草草草草草草
------------------------
平平平平平平平平
平平平平平平平平
A-----------------------

AB横向距离1000米，山荒草平纵向都是100米，移动速度1,2,3,4米/秒，A点最快到达B点多少时间？这样不就行了

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	phoenixdaizy


	忠英伯靖康军节度使

组别	节度使
级别	骠骑将军
功绩	314
帖子	8800
编号	356
注册	2003-9-4

#9

发表于 2010-5-2 17:39 资料文集短消息只看该作者

QUOTE:

原帖由周瑜于 2010-5-1 09:34 发表
小明即将参加越野赛跑，需要穿越平原、草地、荒地、山地等n种地形，他在各种地形上的速度分别为v1, v2, ... ,vn。每种地形都是矩形，宽度无限，纵向距离分别为w1, w2, ..., wn。穿越时还需要横向移动，即在下图 ...

类似光线折射原理。呵呵。

[广告] 《精忠报国岳飞传完整版》火热发布


	dimeterio (李秀辰)

组别	校尉
级别	镇西将军
好贴	1
功绩	45
帖子	3985
编号	266634
注册	2008-2-7

#10

发表于 2010-5-2 20:23 资料个人空间短消息只看该作者

楼主这个题跟光通过多层媒质折射的本质几乎就是一样的，网上肯定有能搜到的现成答案。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#11

发表于 2010-5-2 22:11 资料个人空间短消息只看该作者

如果和折射问题一样，那就简单了，只需求“入射角即可”

设地形m到地形m+1的“入射角为”am，“折射角”为a[m+1]，则

sin a1/v1=sin a2/v2=……=sin an/vn…………………………(*)
w1*tan a1+w2*tan a2+w3*tan a3+……+wn*tan an=s
tan^2 an=sin an/√(1+sin^2 an)

整理得：

w1*sin a1/√(1+sin^2 a1)+w2v2*sin a1/√(v1^2+(v2*sin a1)^2)+w3v3*sin a1/√(v1^2+(v3*sin a1)^2)+……+wnvn*sin a1/√(v1^2+(vn*sin a1)^2)=s

解该方程求出sin a1，之后再利用(*)式求得具体走法。

[ 本帖最后由阿尔法孝直于 2010-5-2 22:20 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#12

发表于 2010-5-2 22:19 资料文集短消息只看该作者

回复 #11 阿尔法孝直的帖子

本质就是多层折射
问题就是怎么解这个方程

我前面写的就是一个求数值解的思路

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#13

发表于 2010-5-3 10:12 资料主页文集短消息只看该作者

这题做到这步就差不多了，剩下的可以用二分法可以求出入射角正弦与速度之比。注意该比值的范围是0到1/max(v)，否则会发生全反射。

写了个小程序，代入KYOYO所给数据，得到答案413.72秒，各位看看是否正确。

木之说的爬山法不知是怎样的，是否简单介绍一下？

[广告] 真诚支持说岳，携手共创辉煌


	dimeterio (李秀辰)

组别	校尉
级别	镇西将军
好贴	1
功绩	45
帖子	3985
编号	266634
注册	2008-2-7

#14

发表于 2010-5-3 10:22 资料个人空间短消息只看该作者

回复 #13 周瑜的帖子

這個答案顯然不會正確。

如果A和B在同一直線上（s=0），耗時應該是250/1+250/2+250/3+250/4=520.833……

不可能快過這個值。

[广告] 《精忠报国岳飞传完整版》火热发布


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#15

发表于 2010-5-3 10:45 资料文集短消息只看该作者

回复 #13 周瑜的帖子

爬山法更多地是一种笼统的说法吧
思路上就是反复地在之前的解附近取一个解并比较择优
作用是能找到初始解附近的一个局部极值

仔细想想，没有二分法自然也没有二分法来得快
只是因为平时经常看到，就想到它了...

[广告] 真诚支持说岳，携手共创辉煌


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#16

发表于 2010-5-3 10:47 资料文集短消息只看该作者

回复 #14 dimeterio 的帖子

8楼说的是“山荒草平纵向都是100米”，不是250米

[广告] 《精忠报国岳飞传完整版》火热发布


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#17

发表于 2010-5-3 11:36 资料主页文集短消息只看该作者

想了一下，爬山法可能是Gradient descent，x[n+1] = x[n] - c * f'(x[n])
用于寻找局部极值的地方，即f'(x) = 0

而寻找 f(x) ＝ 0 的点，除了二分法还可以用牛顿法，x[n+1] = x[n] - f(x[n])/f'(x[n])

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#18

发表于 2010-5-3 12:19 资料文集短消息只看该作者

回复 #17 周瑜的帖子

爬山法的常见连续版本就是gradient descent
不过也有很多别的做法，总之就是摸到高处就往上爬

很多时候，可能问题是离散的，可能导数不存在的，或者可能计算导数代价较大
我整天面对的都是这样的问题，脑子有点僵硬了，反而有导数不会用了- -b

[广告] 真诚支持说岳，携手共创辉煌


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#19

发表于 2010-5-3 12:20 资料个人空间短消息只看该作者

牛顿法计算量大，但是序列收敛速度快，就用牛顿法吧………………

float shortest(float *w,float * v,float s,int count,float ebs){
  int i;
  float a=0.0;
  float temp=0.0;
  float sum1=0.0;
  float sum2=0.0;
  do {
a=temp;
sum1=sum2=0.0;
for (i=0;i<count;i++){
   sum1+=*(w+i)*sin(a)**(v+i)/sqrt(*v**v+*(v+i)**(v+i)*sin(a)*sin(a));
   sum2+=*(v+i)**(w+i)*cos(a)*sqrt(*v**v+*(v+i)**(v+i)*sin(a)*sin(a))/(v*v+sin(a)*sin(a)**(v+i)**(v+i));
   sum2-=*(v+i)**(v+i)**(v+i)**(w+i)*sin(a)*sin(a)*cos(a)*sqrt(*v**v+*(v+i)**(v+i)*sin(a)*sin(a))/(v*v+sin(a)*sin(a)**(v+i)**(v+i)*sqrt(*v**v+*(v+i)**(v+i)*sin(a)*sin(a));
   temp=a-sum1/sum2;
}
  }while(abs(a-temp)>ebs);
  return(temp);
}

[广告] 《精忠报国岳飞传完整版》火热发布


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#20

发表于 2010-5-3 12:22 资料个人空间短消息只看该作者

------网络问题，请删除此帖------

[ 本帖最后由阿尔法孝直于 2010-5-3 12:56 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	飞雪连天射 (天下无双)

组别	百姓
级别	在野武将
功绩	0
帖子	27
编号	304994
注册	2009-1-9
家族	聚贤山庄

#21

发表于 2010-5-3 20:00 资料短消息只看该作者

我的头快炸了

[广告] 《精忠报国岳飞传完整版》火热发布