北京距离最短的地铁线路_北京地铁几号线最挤

北京距离最短的地铁线路_北京地铁几号线最挤用Python计算北京地铁的两站间最短换乘路线地铁数据地铁数据用字典表示:{station:{neighbor1:linenumber,neighbor2:linenumber,…},station2:{…},…}现在我们有地铁的站名,下面就是如何将地铁站名转化为上面所需要的标准字典格式。从网上找到的地铁站名为字符串:line1=u”’苹果园古城路八角游乐园八宝山玉泉路五

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

用Python计算北京地铁的两站间最短换乘路线

地铁数据

地铁数据用字典表示:
{station:{neighbor1:line number,neighbor2:line number,…},station2:{…},…}
现在我们有地铁的站名,下面就是如何将地铁站名转化为上面所需要的标准字典格式。
从网上找到的地铁站名为字符串:

line1=u'''苹果园 古城路 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨地 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东'''
line2=u'''西直门 车公庄 阜成门 复兴门 长椿街 宣武门 和平门 前门 崇文门 北京站 建国门 朝阳门 东四十条 东直门 雍和宫 安定门 鼓楼大街 积水潭'''
line5=u'''宋家庄 刘家窑 蒲黄榆 天坛东门 磁器口 崇文门 东单 灯市口 东四 张自忠路 北新桥 雍和宫 和平里北街 和平西桥 惠新西街南口 惠新西街北口 大屯桥东 北苑路北 立水桥南 立水桥 天通苑南 天通苑 天通苑北'''
line4=u'''天宫院 生物医药基地 义和庄 黄村火车站 黄村西大街 清源路 枣园 高米店南 高米店北 西红门 新宫 公益西桥 角门西 马家堡 北京南站 陶然亭 菜市口 宣武门 西单 灵境胡同 西四 平安里 新街口 西直门 动物园 国家图书馆 魏公村 人民大学 海淀黄庄 中关村 北京大学东门 圆明园 西苑 北宫门 安河桥北'''
line6=u'''海淀五路居 慈寿寺 白石桥南 车公庄西 车公庄 平安里 北海北 南锣鼓巷 东四 朝阳门 东大桥 呼家楼 金台路 十里堡 青年路 褡裢坡 黄渠 常营 草房 物资学院路 通州北关 通运门 北运河西 北运河东 郝家府 东夏园 潞城'''
line8=u'''朱辛庄 育知路 平西府 回龙观东大街 霍营 育新 西小口 永泰庄 林萃桥 森林公园南门 奥林匹克公园 奥体中心 北土城 安华桥 鼓楼大街 什刹海 南锣鼓巷'''
line9=u'''国家图书馆 白石桥南 白堆子 军事博物馆 北京西站 六里桥东 六里桥 七里庄 丰台东大街 丰台南路 科怡路 丰台科技园 郭公庄'''
line10=u'''劲松 双井 国贸 金台夕照 呼家楼 团结湖 农业展览馆 亮马桥 三元桥 太阳宫 芍药居 惠新西街南口 安贞门 北土城 健德门 牡丹园 西土城 知春路 知春里 海淀黄庄 苏州街 巴沟 火器营 长春桥 车道沟 慈寿寺 西钓鱼台 公主坟 莲花桥 六里桥 西局 泥洼 丰台站 首经贸 纪家庙 草桥 角门西 角门东 大红门 石榴庄 宋家庄 成寿寺 分钟寺 十里河 潘家园'''
line13=u'''西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门'''
line14=u'''张郭庄 园博园 大瓦窑 郭庄子 打井 七里庄 西局'''
line15=u'''俸伯 顺义 石门 南法信 后沙峪 花梨坎 国展 孙河 马泉营 崔各庄望京 望京西'''
YiZhuangLine=u'''宋家庄 肖村 小红门 旧宫 亦庄桥 亦庄文化园 万源街 荣京东街 荣昌东街 同济南路 经海路 次渠南 次渠'''
FangShanLine=u'''郭公庄 大葆台 稻田 长阳 篱笆房 广阳城 良乡大学城北 良乡大学城 良乡大学城西 良乡南关 苏庄'''
ChangPingLine=u'西二旗 生命科学园 朱辛庄 巩华城 沙河 沙河高教园 南邵'
BaTongLine=u'''四惠 四惠东 高碑店 中国传媒大学 双桥 管庄 八里桥 通州北苑 果园 九棵树 梨园 临河里 土桥'''

Jetbrains全家桶1年46,售后保障稳定

将这些字符串导入字典,可以利用python的解包操作。

def build_subway(**lines):
    """ Input is build_subway(linename='station1 station2...'...) Ouput is a dictionary like {station:{neighbor1:line number,neighbor2:line number,...},station2:{...},...} """
    for key in lines.keys():
        value = lines[key]
        lines[key] = value.split()
    stations = set()
    for key in lines.keys():
        stations.update(set(lines[key]))
    system = { 
   }
    for station in stations:
        next_station = { 
   }
        for key in lines:
            if station in lines[key]:
                line = lines[key]
                idx = line.index(station)
                if idx == 0:
                    next_station[line[1]] = key
                elif idx == len(line)-1:
                    next_station[line[idx-1]]=key
                else:
                    next_station[line[idx-1]] = key
                    next_station[line[idx+1]] = key
        system[station] = next_station
    return system

这样,我们可以得到所需的图结构。
但是,仅仅这样就够了吗?
显然不是,仔细观察北京地铁图,并查看上面的代码。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nVKeodfG-1649767823813)(https://img-blog.csdn.net/20150524200159383)]
我们发现,北京地铁线路可以分为两大类:直线线路,环线线路。
直线线路如:4号线,9号线,1号线等
环线线路如:2号线,10号线等
直线线路数量远远大于环线线路数量。
再结合上面的代码,我们发现,上面的代码仅仅适用于直线线路,对环线线路就有瑕疵了。那么,还需要再写一个适用于环线线路的函数吗?
可以不用的,只是增加一个update函数,考虑到环线情况就好了。
环线只不过是首尾相接。

def update_subway(BeiJingSubway):
    """ due to line2 and line10 are circle lines. the BeiJingSubway need to update """
    BeiJingSubway[u'西直门'][u'积水潭'] = 'line2'
    BeiJingSubway[u'积水潭'][u'西直门'] = 'line2'
    BeiJingSubway[u'劲松'][u'潘家园'] = 'line10'
    BeiJingSubway[u'潘家园'][u'劲松'] = 'line10'
    return BeiJingSubway

这样,我们可以得到所需的图结构:


bj_subway = build_subway(line1=u'''苹果园 古城路 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨地 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东''',
                       line2=u'''西直门 车公庄 阜成门 复兴门 长椿街 宣武门 和平门 前门 崇文门 北京站 建国门 朝阳门 东四十条 东直门 雍和宫 安定门 鼓楼大街 积水潭''',
                       line5=u'''宋家庄 刘家窑 蒲黄榆 天坛东门 磁器口 崇文门 东单 灯市口 东四 张自忠路 北新桥 雍和宫 和平里北街 和平西桥 惠新西街南口 惠新西街北口 大屯桥东 北苑路北 立水桥南 立水桥 天通苑南 天通苑 天通苑北''',
                       line4=u'''天宫院 生物医药基地 义和庄 黄村火车站 黄村西大街 清源路 枣园 高米店南 高米店北 西红门 新宫 公益西桥 角门西 马家堡 北京南站 陶然亭 菜市口 宣武门 西单 灵境胡同 西四 平安里 新街口 西直门 动物园 国家图书馆 魏公村 人民大学 海淀黄庄 中关村 北京大学东门 圆明园 西苑 北宫门 安河桥北''',
                       line6=u'''海淀五路居 慈寿寺 白石桥南 车公庄西 车公庄 平安里 北海北 南锣鼓巷 东四 朝阳门 东大桥 呼家楼 金台路 十里堡 青年路 褡裢坡 黄渠 常营 草房 物资学院路 通州北关 通运门 北运河西 北运河东 郝家府 东夏园 潞城''',
                       line8=u'''朱辛庄 育知路 平西府 回龙观东大街 霍营 育新 西小口 永泰庄 林萃桥 森林公园南门 奥林匹克公园 奥体中心 北土城 安华桥 鼓楼大街 什刹海 南锣鼓巷''',
                       line9=u'''国家图书馆 白石桥南 白堆子 军事博物馆 北京西站 六里桥东 六里桥 七里庄 丰台东大街 丰台南路 科怡路 丰台科技园 郭公庄''',
                       line10=u'''劲松 双井 国贸 金台夕照 呼家楼 团结湖 农业展览馆 亮马桥 三元桥 太阳宫 芍药居 惠新西街南口 安贞门 北土城 健德门 牡丹园 西土城 知春路 知春里 海淀黄庄 苏州街 巴沟 火器营 长春桥 车道沟 慈寿寺 西钓鱼台 公主坟 莲花桥 六里桥 西局 泥洼 丰台站 首经贸 纪家庙 草桥 角门西 角门东 大红门 石榴庄 宋家庄 成寿寺 分钟寺 十里河 潘家园''',
                       line13=u'''西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门''',
                       line14=u'''张郭庄 园博园 大瓦窑 郭庄子 打井 七里庄 西局''',
                       line15=u'''俸伯 顺义 石门 南法信 后沙峪 花梨坎 国展 孙河 马泉营 崔各庄望京 望京西''',
                       YiZhuangLine=u'''宋家庄 肖村 小红门 旧宫 亦庄桥 亦庄文化园 万源街 荣京东街 荣昌东街 同济南路 经海路 次渠南 次渠''',
                       FangShanLine=u'''郭公庄 大葆台 稻田 长阳 篱笆房 广阳城 良乡大学城北 良乡大学城 良乡大学城西 良乡南关 苏庄''',
                       ChangPingLine=u'西二旗 生命科学园 朱辛庄 巩华城 沙河 沙河高教园 南邵',
                       BaTongLine=u'''四惠 四惠东 高碑店 中国传媒大学 双桥 管庄 八里桥 通州北苑 果园 九棵树 梨园 临河里 土桥''')
bj_subway = update_subway(bj_subway)

最短路径

有了图结构之后,可以利用队列进行BFS,得到所需要的路径。
这里的队列暂时先使用list替代,更高性能的队列可以使用collections库中的deque(双端队列)实现,在deque中,popleft()与append()操作都是O(1)的时间复杂度,而list的append()操作虽然是O(1)的时间复杂度,但是pop(0)操作却是O(n)的时间复杂度。
这里,不考虑性能就用list代替queue吧。
另一件事,就是寻找相邻节点,这个很简单,图结构已经给我们准备好了。

def shorter_path(start, goal):
    """ without consideration of the change times fina shortest path """
    if start == goal:
        return [start]
    explored = set() 
    queue = [ [start] ] 
    while queue:
        path = queue.pop(0)
        s = path[-1]
        for state, action in bj_subway[s].items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                if state == goal:
                    return path2
                else:
                    queue.append(path2)
    return []

我们运行一下试试:
比如我们要从“人民大学”到“青年路”吧:
得到的结果是什么呢?

人民大学
line4
魏公村
line4
国家图书馆
line9
白石桥南
line6
车公庄西
line6
车公庄
line6
平安里
line6
北海北
line6
南锣鼓巷
line6
东四
line6
朝阳门
line6
东大桥
line6
呼家楼
line6
金台路
line6
十里堡
line6
青年路

看起来不错哇!成功了吗?
仔细对照地图,又一个问题出现了。在上面的结果中,程序告诉我们:要在4号线国家图书馆换乘9号线,再从9号线白石桥南换乘6号线。
但是,地图告诉我们,没有必要这样做。
人大到青年路

最小换乘次数

问题出在我们的算法上,要加入一个换乘次数的变量,考虑到这一个变量,才能计算出合乎常理的结果。
这时,我们的路径的末节点要做一些变化来迎合算法的变化。
所以我决定在末节点之后,再加入一个元组:(linenum, changetimes)
linenum表示上一次的地铁线路,changetimes表示当前情况下的换乘次数。这时我们要引入优先队列的概念,用最小堆来实现的话比较复杂,不如直接对列表进行排序。这样,对上述算法略微修改,就可以得到新的函数:

def path_search(start, goal):
    """Find the shortest path from start state to a state with min change times such that is_goal(state) is true."""
    if start == goal:
        return [start]
    explored = set() 
    queue = [ [start, ('', 0)] ]
    while queue:
        path = queue.pop(0)
        s = path[-2]
        linenum, changetimes = path[-1]
        if s == goal:
            return path
        for state, action in bj_subway[s].items():
            if state not in explored:
                linechange = changetimes
                explored.add(state)
                if linenum != action:
                    linechange += 1
                path2 = path[:-1] + [action, state, (action, linechange)]
                queue.append(path2)
                queue.sort(key=lambda path:path[-1][-1])
    return []

这时,我们再试试,计算从“人民大学”到“青年路”的路径:

人民大学
line4
魏公村
line4
国家图书馆
line4
动物园
line4
西直门
line4
新街口
line4
平安里
line6
北海北
line6
南锣鼓巷
line6
东四
line6
朝阳门
line6
东大桥
line6
呼家楼
line6
金台路
line6
十里堡
line6
青年路

只有4号线和6号线,结果正确了。

最终取舍

如果计算任意两站的路径时,会不会有以下情况:
站A,B都在环线10号线上,在十号线他们相距20站,
但是A距离10号线与6号线换乘车站C仅仅一站。
B距离10号线与6号线换乘车站D仅仅一站。
假如A是“西钓鱼台”B是“团结湖”
用最小换乘算法的结果就是:

西钓鱼台
line10
慈寿寺
line10
车道沟
line10
长春桥
line10
火器营
line10
巴沟
line10
苏州街
line10
海淀黄庄
line10
知春里
line10
知春路
line10
西土城
line10
牡丹园
line10
健德门
line10
北土城
line10
安贞门
line10
惠新西街南口
line10
芍药居
line10
太阳宫
line10
三元桥
line10
亮马桥
line10
农业展览馆
line10
团结湖

显然,在这种情况下,最小换乘算法并不正确。
所以,在寻找最好的路径时,我们要进行比较,到底哪个更好?

def find_path(here, there, system=bj_subway):
    """ Return a path on the subway system from here to there. find a better path between the change-time-less path and shorter path """

    min_change_path = path_search(here, there)[::2]
    short_path = shorter_path(here, there)[::2]
    if len(min_change_path) <= len(short_path):
        for ele in min_change_path:
            print(ele)
        print(len(min_change_path))
    else:
        for ele in short_path:
            print(ele)
        print(len(short_path))

再拿“西钓鱼台”与“团结湖”做做测试:

西钓鱼台
慈寿寺
白石桥南
车公庄西
车公庄
平安里
北海北
南锣鼓巷
东四
朝阳门
东大桥
呼家楼
团结湖
13

13站还不错。

如果本文对您有帮助,还请赞赏一下嘛!
code

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/209841.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 外链图床-PicGo-Gitee

    外链图床-PicGo-Gitee前言刚开始写建立博客的时候,头疼过图片该如何处理:直接放github的仓库里吧。可是随着图片越来越多,每次pull、clone都需要耗费大量的时间。而且github的仓库加载很慢,影响博客的流畅性。外链图床吧。可是国内基本上没有什么好用的免费图床,七牛云之类的都需要收费的。国外的图床加载速度又是特别的慢。自己搭建。图床搭建所使用的工具为PicGo、Gitee、Typora.在这之前,我一般在VSCode上面写Markdown文档,但是现在开始添加图片到博客中去,转而使用Typora,以便

  • javaWeb学习——servlet、filter、listener、intercept的区别

    javaweb开发有很多技术要学习,首先将简单的概念和基础打好,然后才能更好的成长! 自己整理一遍,记忆深刻一点! 一:概念二:实现方式三:执行逻辑图参考:http://www.cnblogs.com/shangxiaofei/p/5328377.htmlhttp://blog.csdn.net/lzwjavaphp/article/details/13771109

  • 数据结构与算法栈的详解_数据结构怎么判断出栈的顺序

    数据结构与算法栈的详解_数据结构怎么判断出栈的顺序一、什么是栈栈(stack)是一种先进后出的有序列表,其中的元素只能在线性表的同一端进出,允许元素插入和删除的一端被称为栈顶(top),固定的另一端被称为栈底(button)。二、数组简单实现栈

  • ClassCastException。

    ClassCastException。这个错误也很常见,通常在程序中出现强制类型转换时出现这个错误,如下面这段代码所示:publicstaticMapm=newHashMap(){ { put("a","2"); } }; publicstaticvoidmain(String[]args){ IntegerisInt=(Integer)m.get("a"…

  • 网站推荐:11个相似图片搜索网站(以图找图)

    网站推荐:11个相似图片搜索网站(以图找图)你想凭着一张现有图片找出它的原始图片,或者是凭着一张小的缩略图找出原始大图吗?下面的十款搜索引擎可以帮你实现,以图找图,以图搜图,以图片搜索相似的图片。一:http://tineye.com/Tineye是典型的以图找图搜索引擎,输入本地硬盘上的图片或者输入图片网址,即可自动帮你搜索相似图片,搜索准确度相对来说还比较令人满意。TinEye是加拿大Idée公司研发…

  • 2020年下半年总结与计划

    2020年下半年总结与计划0x00前言2020年到如今已经到了十二月中旬,下半年所学的东西还是挺多,我觉得学习的一个效率也是有着飞跃般的提升。主要的原因可能在于我和我的好朋友(基友)住在一个房间

    2021年12月12日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号