全国公交线路查询的算法:如何迅速确定乘客的最优公交线路?
假设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编辑过]