您的位置：程序门 -> ms-sql server -> 疑难问题

有趣可能也超难的问题：求最短步行距离

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

有趣可能也超难的问题：求最短步行距离[已结贴,结贴人:fckadxz]

发表于：2007-06-25 19:40:30 楼主

a地小刚要到z地朋友家去。假设az之间等距离25段，这些中间点是b c d...y，但是有些中点没有车站，并且公车不中途停车，比如af间的车只有ad cf，那么至少有3种选择：1全走路步行距离5；2坐车选ad步行距离2；3乘车选ad cf，然后倒着走cd段步行1的距离。

小刚最讨厌走路，我们需要替他选走路最短（方向不限)的乘车方式，那么如果a到f第3种方法步行距离最短为1，所以选第3种方式：乘车ad cf 并且倒着走完cd是正解。

扩大来看，az之间距离更长，车路线更多，什么算法能做到步行距离最短呢？也即是说，选出乘车路线是步行最短。

发表于：2007-06-25 21:09:451楼得分:30

用图算法吧，构造一个图，乘车能到的地方直接两点相连，走路去的地方一个顶点一个顶点的连接，计算路径最短就行了

发表于：2007-06-25 21:23:312楼得分:0

不太明白。能说详细点吗，和图论中的例子不同的。

发表于：2007-06-25 23:15:253楼得分:0

明天再看看...

发表于：2007-06-26 09:48:194楼得分:50

存储每段的信息,并且记录每段的衔接段
比如:
a-b段

id 路段上行衔接段上行衔接段路段长
1 ab段 3 4 60
2 ab段 3 5 60
3 oa段 ..................................
4 bc段 ..................................
5 bd段 ..................................
.
.
然后,把所有可能的路线求出来,找出最短的.

发表于：2007-06-26 09:49:515楼得分:0

更正下,第2个 "上行衔接段 "应该为 "下行衔接段 ".

发表于：2007-06-26 09:52:106楼得分:10

这个就是图论,求最短路经

发表于：2007-07-15 15:32:317楼得分:10

关注

下一篇：比较两个查询的效率（希望得到肯定的答复）
上一篇：数据库问题

其他资讯