| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1195 人关注过本帖
标题:全国公交线路查询的算法:如何迅速确定乘客的最优公交线路?
只看楼主 加入收藏
cssnet
Rank: 5Rank: 5
等 级:职业侠客
威 望:5
帖 子:351
专家分:335
注 册:2013-10-4
结帖率:100%
收藏
 问题点数:0 回复次数:6 
全国公交线路查询的算法:如何迅速确定乘客的最优公交线路?
假设X旅客到某城市旅游,一天打算游玩4+个景点:
A景点、B景点、C景点、D景点、……
经查询公交线路总数据库后,推荐乘坐某一路公交车,尽可能在不换车的前提下(因旅客在陌生城市换乘公交非常容易出错),途经最接近这4+个景点的若干个公交站点:
惠南地铁、听潮一村、人民西路城西路、人民东路新华路……
可能有36条公交车途经惠南地铁,27条途经听潮一村,21条途经人民西路城西路,18条途经人民东路新华路。
这些公交车线路是彼此交错重叠的,每一趟公交车线路都设有10+至30+个站点不等,其中有的线路覆盖其中4个站点,有的覆盖3个,有的覆盖2个或1个。
如何迅速查询出覆盖旅客目标站点数目最多的线路?

假设途经其中74%以上站点数即为“命中”(大约“4选3”或以上,越多越好),如何迅速定位该“命中”的公交线路?
当“命中”比例相同(比如都是最多命中75%),以线路的站点总数由多到小逆序排列,优先挑选站点总数最多的线路,以方便搭乘(1111路共18站,123路共16站,优先选1111路)。

全国的所有公交线路,均以“6位数城市邮政编码+5位数线路名”来统一命名,存放在庞大的“公交线路.dbf”中。
乘客途经站点,均以“旅客ID”+“站点”,存放在庞大的“旅客.dbf”中,一次查询就自增一个ID,同一旅客途经的数个站点,ID相同,均各占一行记录。

公交线路.dbf:
线路    I
站点    C(30)
站点总数  I
……

旅客.dbf:
旅客ID  I
(途经)站点    C(30)
(最优)线路    I
命中    I(1表示命中)
……

假设需例行处理1000万+至1亿+条记录,那么算法优化节省出每1微秒、每1毫秒,可能都有很大意义。
折腾半天,发觉效率低下!主要是1000万+的记录条数,好像特别费时费力!


[此贴子已经被作者于2022-4-19 12:26编辑过]

搜索更多相关主题的帖子: 站点 线路 算法 查询 dbf 
2022-04-19 08:17
cssnet
Rank: 5Rank: 5
等 级:职业侠客
威 望:5
帖 子:351
专家分:335
注 册:2013-10-4
收藏
得分:0 
啰哩啰嗦了一大通,其实这个问题可归结为:

求两个数据集的最大公共子集

只不过,小数据集(乘客途经站点)是确定的,而大数据集(公交线路)则不确定,是算法的目标,需最终推求出来的数据集而已。
2022-04-19 09:19
laowan001
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:66
帖 子:1094
专家分:2693
注 册:2015-12-30
收藏
得分:0 
如果是DBF的话,建立适当的索引,会大大提高效率
2022-04-19 13:46
schtg
Rank: 12Rank: 12Rank: 12
来 自:Usa
等 级:贵宾
威 望:67
帖 子:1790
专家分:3389
注 册:2012-2-29
收藏
得分:0 
这是一个有意思的话题
2022-04-20 05:08
sam_jiang
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:806
专家分:1231
注 册:2021-10-13
收藏
得分:0 
这个算法解决了,你可以去百度或者高德去上班了,年薪50万起!
2022-04-21 19:26
huasinstamps
Rank: 2
等 级:论坛游民
帖 子:65
专家分:24
注 册:2017-6-1
收藏
得分:0 
这个算法对在座几位大佬可能不难,但问题是这个功能可能并不实用
2022-04-22 16:54
cssnet
Rank: 5Rank: 5
等 级:职业侠客
威 望:5
帖 子:351
专家分:335
注 册:2013-10-4
收藏
得分:0 
以下是引用laowan001在2022-4-19 13:46:49的发言:
如果是DBF的话,建立适当的索引,会大大提高效率


SQL查询涉及的几个字段,都建了索引,尽可能地Rushmore优化。

这个算法解决了,你可以去百度或者高德去上班了,年薪50万起!


算法本身不算复杂,也可能有N种解法:或笨拙,或灵慧,或精妙。
主要还是想模拟挑战一下:当数据量很大时,尽可能地穷尽VFP的DBF表的性能极限。

这个算法对在座几位大佬可能不难,但问题是这个功能可能并不实用


其实不必那么实在,非得要“就事论事”。
不妨将问题抽象归结为二楼的论述:
“求两个数据集的最大公共子集”
——那么,这个算法的实用性就很强了,绝对不容置疑!
2022-04-22 18:22
快速回复:全国公交线路查询的算法:如何迅速确定乘客的最优公交线路?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.048192 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved