注册 登录
编程论坛 VFP论坛

全国公交线路查询的算法:如何迅速确定乘客的最优公交线路?

cssnet 发布于 2022-04-19 08:17, 1364 次点击
假设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编辑过]

6 回复
#2
cssnet2022-04-19 09:19
啰哩啰嗦了一大通,其实这个问题可归结为:

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

只不过,小数据集(乘客途经站点)是确定的,而大数据集(公交线路)则不确定,是算法的目标,需最终推求出来的数据集而已。
#3
laowan0012022-04-19 13:46
如果是DBF的话,建立适当的索引,会大大提高效率
#4
schtg2022-04-20 05:08
这是一个有意思的话题
#5
sam_jiang2022-04-21 19:26
这个算法解决了,你可以去百度或者高德去上班了,年薪50万起!
#6
huasinstamps2022-04-22 16:54
这个算法对在座几位大佬可能不难,但问题是这个功能可能并不实用
#7
cssnet2022-04-22 18:22
以下是引用laowan001在2022-4-19 13:46:49的发言:
如果是DBF的话,建立适当的索引,会大大提高效率


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

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


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

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


其实不必那么实在,非得要“就事论事”。
不妨将问题抽象归结为二楼的论述:
“求两个数据集的最大公共子集”
——那么,这个算法的实用性就很强了,绝对不容置疑!
1