标题: 一道越野赛跑问题 [打印本页]
作者:
周瑜 时间: 2010-5-1 09:34 标题: 一道越野赛跑问题
小明即将参加越野赛跑，需要穿越平原、草地、荒地、山地等n种地形，他在各种地形上的速度分别为v1, v2, ... ,vn。每种地形都是矩形，宽度无限，纵向距离分别为w1, w2, ..., wn。穿越时还需要横向移动，即在下图中从A移动到B，横向距离为s。
----------------------B
山山山山山山山山
山山山山山山山山
------------------------
荒荒荒荒荒荒荒荒
荒荒荒荒荒荒荒荒
------------------------
草草草草草草草草
草草草草草草草草
------------------------
平平平平平平平平
平平平平平平平平
A-----------------------
由于在各种地形中的速度不同，时间最短的路径不是从起点到终点的直线，而是在各个地形中的直线连接起来构成的折线。求最短时间。
这题是编程题，用代数式是没法解的，列出方程或者给出思路就可以了。
[ 本帖最后由 周瑜 于 2010-4-30 21:51 编辑 ]
作者:
阿尔法孝直 时间: 2010-5-1 09:46
问： 宽度无限 与后面的 横向距离为s 有没有矛盾
另，斜向移动是否要向英杰传那样分成横向和纵向移动？
[ 本帖最后由 阿尔法孝直 于 2010-5-1 09:47 编辑 ]
作者:
周瑜 时间: 2010-5-1 09:57
虽然宽度无限，但是所使用的仅仅是AB两点中间宽度为s的一段，如果跑到外面去再跑回来，显然比在这个范围内跑所花时间长。
任何时刻，小明所在位置都是一个点，而不是一个面，勿与英杰传混淆。虽然地形名称取自英杰传，但本题与英杰传毫无关系。
斜向移动的距离是勾股定理的弦长，除以该段的速度就是时间。而在每一段地形中的路线都是一条直线。
作者:
阿尔法孝直 时间: 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
最小。
作者:
阿尔法孝直 时间: 2010-5-1 10:30
这题很想用递归二分来做，但不知怎么下手。
作者:
muzhi 时间: 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 时间: 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求近似解。
作者:
KYOKO 时间: 2010-5-2 14:00
----------------------B
山山山山山山山山
山山山山山山山山
------------------------
荒荒荒荒荒荒荒荒
荒荒荒荒荒荒荒荒
------------------------
草草草草草草草草
草草草草草草草草
------------------------
平平平平平平平平
平平平平平平平平
A-----------------------
AB横向距离1000米，山荒草平纵向都是100米，移动速度1,2,3,4米/秒，A点最快到达B点多少时间？这样不就行了
作者:
phoenixdaizy 时间: 2010-5-2 17:39
原帖由 周瑜 于 2010-5-1 09:34 发表
小明即将参加越野赛跑，需要穿越平原、草地、荒地、山地等n种地形，他在各种地形上的速度分别为v1, v2, ... ,vn。每种地形都是矩形，宽度无限，纵向距离分别为w1, w2, ..., wn。穿越时还需要横向移动，即在下图 ...
类似光线折射原理。呵呵。
作者:
dimeterio 时间: 2010-5-2 20:23
楼主这个题跟光通过多层媒质折射的本质几乎就是一样的，网上肯定有能搜到的现成答案。
作者:
阿尔法孝直 时间: 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 编辑 ]
作者:
muzhi 时间: 2010-5-2 22:19 标题: 回复 #11 阿尔法孝直 的帖子
本质就是多层折射
问题就是怎么解这个方程
我前面写的就是一个求数值解的思路
作者:
周瑜 时间: 2010-5-3 10:12
这题做到这步就差不多了，剩下的可以用二分法可以求出入射角正弦与速度之比。注意该比值的范围是0到1/max(v)，否则会发生全反射。
写了个小程序，代入KYOYO所给数据，得到答案413.72秒，各位看看是否正确。
木之说的爬山法不知是怎样的，是否简单介绍一下？
作者:
dimeterio 时间: 2010-5-3 10:22 标题: 回复 #13 周瑜 的帖子
這個答案顯然不會正確。
如果A和B在同一直線上（s=0），耗時應該是250/1+250/2+250/3+250/4=520.833……
不可能快過這個值。
作者:
muzhi 时间: 2010-5-3 10:45 标题: 回复 #13 周瑜 的帖子
爬山法更多地是一种笼统的说法吧
思路上就是反复地在之前的解附近取一个解并比较择优
作用是能找到初始解附近的一个局部极值
仔细想想，没有二分法自然也没有二分法来得快
只是因为平时经常看到，就想到它了...
作者:
muzhi 时间: 2010-5-3 10:47 标题: 回复 #14 dimeterio 的帖子
8楼说的是“山荒草平纵向都是100米”，不是250米
作者:
周瑜 时间: 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])
作者:
muzhi 时间: 2010-5-3 12:19 标题: 回复 #17 周瑜 的帖子
爬山法的常见连续版本就是gradient descent
不过也有很多别的做法，总之就是摸到高处就往上爬
很多时候，可能问题是离散的，可能导数不存在的，或者可能计算导数代价较大
我整天面对的都是这样的问题，脑子有点僵硬了，反而有导数不会用了- -b
作者:
阿尔法孝直 时间: 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);
}
作者:
阿尔法孝直 时间: 2010-5-3 12:22
------网络问题，请删除此帖------
[ 本帖最后由 阿尔法孝直 于 2010-5-3 12:56 编辑 ]
作者:
飞雪连天射 时间: 2010-5-3 20:00
我的头快炸了
| 欢迎光临 轩辕春秋文化论坛 (http://www.xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |