当前在线人数15694
首页 - 分类讨论区 - 学术学科 - 数学版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: 请教一个路径搜索策略
[同主题阅读] [版面: 数学] [作者:beyond] , 2002年05月31日09:15:38
beyond
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: beyond (爱徒生), 信区: Mathematics
标  题: Re: 请教一个路径搜索策略
发信站: The unknown SPACE (Fri May 31 09:53:20 2002), 站内信件

【 在 nanfang (~~~) 的大作中提到: 】
: 已知某城市若干条公交线路,每条线路包括若干站名,现已知起点和终点,求查
: 询线路查询方法
: 条件1,不用转车,某线路含起点终点 (方法略)
: 条件2,转车一次,即某条线路含起点,某线路含终点,两条线路有相同站,得出
: 两条线路名和转车点
: 条件3,转车两次以上,……
: 请问如何设计数据库结构和查询方法,才能最优地找到转车线线路?

数据结构课里学过最短路径的求法。把所有地点看作一个个点。两点间若有线路连结,
则以线段相连,线段长度为两点之距离。设起点S,终点D。除S外,每个和S相连的点
都对应一个数字和一个点,具体做法是:
设A0=B0={S},首先,把和B0中相邻的点P对应上(d(P),S),d(P)是P到S的距离。
如果我们已经有A(k-1)和B(k-1),令Ak是和B(k-1)相邻的所有点。Bk是Ak中去除B1,
B2,...,B(k-1)的点。对Ak中的每个点Q,寻找B(k-1)中和Ak相邻的点R,使得R和Q的
距离加上d(R)的值最小,以此值作为d(Q), Q点对应上(d(Q),R)。如此类推直到某个
B(n)为空集为止。

--
  操吴戈兮被犀甲,车错毂兮短兵接。旌蔽日兮敌若云,矢交坠兮士争先。 
  凌余阵兮躐余行,左骖殪兮右刃伤。霾两轮兮絷四马,援玉桴兮絷鸣鼓。 
                  天时坠兮威灵怒,严杀尽兮弃原野。                 
  出不入兮往不反,平原忽兮路超远。带长剑兮挟秦弓,首身离兮心不惩。 
  成既勇兮又以武,终钢强兮不可凌。身既死兮神以灵,魂魄毅兮为鬼雄。 


※ 修改:.beyond 于 May 31 11:12:20 修改本文.[FROM: 68.63.88.74]
※ 来源:.The unknown SPACE bbs.mit.edu.[FROM: 68.63.88.74]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996