题意:
给一个正八面体,有只蚂蚁要从面上一点走到另一点,只能沿表面走,求最短距离。
为了讨论方便,首先给所有顶点标号,如图所示.



分四类讨论:
1)共面情况( 两点都在面ABC上 )
两点之间直线最短, 这时直接计算两点之间距离

2)相邻面情况(一点在面ABC上, 一点在面ACD上 )
最短路径只可能是两个相邻面摊开的直线距离,如图所示:


其他路径可以反射到这两个面上证明他们不是最优的.例如:

红线路径和黄线路径是等价的,而红线路径显然没有前一幅图的蓝线路径优.


3)同在上侧的“对立面”情况( 一点在面ABC上, 一点在面ADE上 ).
最优情况有两种:
  • 从 面ABC 到 面ACD 到 面ADE
  • 从 面ABC 到 面ABE 到 面ADE
同2)一样利用反射的方法可以证明其他走法不是最优的.

4)严格“对面”情况(一点在面ABC上, 一点在面DEF上 )。

枚举所有可能的六种情况.


其他的情况都可以通过坐标变换转化成这四种情况

Feedback

# re: The Return of Carl 正八面体上的最短路  回复  更多评论   

2011-01-04 10:47 by 左手右手
同学你有这道题的源程序吗??同学我急用啊~Q我,289185858,左手右手,谢啦~~~

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊