NLP第二课(搜索)

  最近压力太大了,持续性修改0注释的代码,变量为阿拉伯数字的代码,压力山大,摆正心态,没有那些bug,还需要我们来做些什么呢?如果一个特别出色的项目,也体现不出来你个人的出色。几句牢骚,我们今天来继续说下NLP。

  我们先来抛出一个问题,我们要坐地跌,从西直门站到苏州街站,我们在北京的小伙伴都知道,坐4号线,然后在海淀黄庄换成10号线就到了,或者我们直接打开导航,搜一下就可以了。说起来很简单,想起来也很简单,但是做起来不是那么简单了。我们现有所有线路的站点,以及换成车站的数据(爬取过程略去)。我们现有的数据是这样的:

1号线:

苹果园-古城-八角游乐园-八宝山-玉泉路-五棵松-万寿路-公主坟-军事博物馆-木樨地-南礼士路-复兴门-西单-天安门西-天安门东-王府井-东单-建国门-永安里-国贸-大望路-四惠-四惠东

2号线:

西直门-积水潭-鼓楼大街-安定门-雍和宫-东直门-东四十条-朝阳门-建国门-北京站-崇文门-前门-和平门-宣武门-长椿街-复兴门-阜成门-车公庄-(西直门)

4号线:

国家图书馆-动物园-西直门-新街口-平安里-西四-灵境胡同-西单-宣武门-菜市口-陶然亭-北京南站-马家堡-角门西-公益西桥

5号线:

宋家庄-刘家窑-蒲黄榆-天坛东门-磁器口-崇文门-东单-灯市口-东四-张自忠路-北新桥-雍和宫-和平里北街-和平西桥-惠新西街南口-惠新西街北口-大屯路东-北苑路北-立水桥南-立水桥-天通苑南-天通苑-天通苑北

6号线:

金安桥-苹果园-杨庄-西黄村-廖公庄-田村-海淀五路居-慈寿寺-花园桥-白石桥南-车公庄西-车公庄-平安里-北海北-南锣鼓巷-东四-朝阳门-东大桥-呼家楼-金台路-十里堡-青年路-褡裢坡-黄渠-常营-草房-物资学院-通州北关-通运门-北运河西-北运河东-郝家府-东夏园-潞城

7号线:

北京西站-湾子-达官营-广安门内-菜市口-虎坊桥-珠市口-桥湾-磁器口-广渠门内-广渠门外-双井-九龙山-大郊亭-百子湾-化工-南楼梓庄-欢乐谷景区-垡头-双合-焦化厂

8号线北:

朱辛庄-育知路-平西府-回龙观东大街-霍营-育新-西小口-永泰庄-林萃桥-森林公园南门-奥林匹克公园-奥体中心-北土城-安华桥-安德里北街-鼓楼大街-什刹海-南锣鼓巷-中国美术馆

8号线南:

珠市口-天桥-永定门外-木樨园-海户屯-大红门-大红门南-和义-东高地-火箭万源-五福堂-德茂-瀛海

9号线:

郭公庄-丰台科技园-科怡路-丰台南路-丰台东大街-七里庄-六里桥-六里桥东-北京西站-军事博物馆-白堆子-白石桥南-国家图书馆

10号线:

巴沟-苏州街-海淀黄庄-知春里-知春路-西土城-牡丹园-健德门-北土城-安贞门-惠新西街南口-芍药居-太阳宫-三元桥-亮马桥-农业展览馆-团结湖-呼家楼-金台夕照-国贸-双井-劲松-潘家园-十里河-分钟寺-成寿寺-宋家庄-石榴庄-大红

门-角门东-角门西-草桥-纪家庙-首经贸-丰台站-泥洼-西局-六里桥-莲花桥-公主坟-西钓鱼台-慈寿寺-车道沟-长春桥-火器营-(巴沟)

13号线:

西直门-大钟寺-知春路-五道口-上地-西二旗-龙泽-回龙观-霍营-立水桥-北苑-望京西-芍药居-光熙门-柳芳-东直门

14号线西:

张郭庄-园博园-大瓦窑-郭庄子-大井-七里庄-西局

14号线东:

北京南站-陶然桥-永定门外-景泰-蒲黄榆-方庄-十里河-北工大西门-平乐园-九龙山-大望路-金台路-朝阳公园-枣营-东风北桥-将台-高家园-望京南-阜通-望京-东湖渠-来广营-善各庄

15号线:

俸伯-顺义-石门-南法信-后沙峪-花梨坎-国展-孙河-马泉营-崔各庄-望京东-望京-望京西-关庄-大屯路东-安立路-奥林匹克公园-北沙滩-六道口-清华东路西口

16号线:

西苑-农大南路-马连洼-西北旺-永丰南-永丰-屯佃-稻香湖路-温阳路-北安河

八通线:

四惠-四惠东-高碑店-传媒大学-双桥-管庄-八里桥-通州北苑-果园-九棵树-梨园-临河里-土桥

昌平线

昌平西山口-十三陵景区-昌平-昌平东关-北邵洼-南邵-沙河高教园-沙河-巩华城-朱辛庄-生命科学园-西二旗

亦庄线:

宋家庄-肖村-小红门-旧宫-亦庄桥-亦庄文化园-万源街-荣京东街-荣昌东街-同济南路-经海路-次渠南-次渠-亦庄火车站

房山线:

郭公庄-大葆台-稻田-长阳-篱笆房-广阳城-良乡大学城北-良乡大学城-良乡大学城西-良乡南关-苏庄-阎村东

机场线

东直门-三元桥-3号航站楼-2号航站楼

大兴线

公益西桥-新宫-西红门-高米店北-高米店南-枣园-清源路-黄村西大街-黄村火车站-义和庄-生物医药基地-天宫院

S1线

石厂-小园-栗园庄-上岸-桥户营-四道桥-金安桥

西郊线

巴沟-颐和园西门-茶棚-万安-植物园-香山

数据大概就这些,那么我们怎么来搜索我们想要的数据呢?我们还是先分析一下我们的问题。我们要从西直门出发,到达苏州街,很容易我们就知道了我们要做4号线,然后呢?然后我们去哪?

我们在西直门上车以后,有积水潭,新街口,动物园,大钟寺,车公庄。这5个方向可以选择。我们先(随便)写一个程序,不管是哪,先走着。

我们现将数据清洗一下,变成我们想要的样子:{'苹果园': ['古城', '金安桥', '杨庄'], '古城': ['苹果园', '八角游乐园'], '八角游乐园': ['古城', '八宝山'], '八宝山': ['八角游乐园', '玉泉路'], '玉泉路': ['八宝山', '五棵松'], '五棵松': ['玉泉路', '万寿路'], '万寿路': ['五棵松', '公主坟'], '公主坟': ['万寿路', '军事博物馆', '莲花桥', '西钓鱼台'], '军事博物馆': ['公主坟', '木樨地', '北京西站', '白堆子'], '木樨地': ['军事博物馆', '南礼士路'], '南礼士路': ['木樨地', '复兴门'], '复兴门': ['南礼士路', '西单', '长椿街', '阜成门'], '西单': ['复兴门', '天安门西', '宣武门', '灵境胡同'], '天安门西': ['西单', '天安门东'], '天安门东': ['天安门西', '王府井'], ...},也就是这样的。我们用每一个站当作key,可以到达的车站我们设置为value列表。

然后我们先来看一下我们的代码吧

def breadth_first_search(start, arrive, connrction_grpah):
    pathes = [[start]]
    visitied = set()

    while pathes:
        path = pathes.pop(0)
        froninter = path[-1]

        if froninter in visitied:
            continue
        successors = connrction_grpah[froninter]

        for city in successors:
            new_path = path + [city]
            pathes.append(new_path)

            if city == arrive:
                return new_path
        visitied.add(froninter)

我们可以看得出来,我们拿到我们的始发站,然后去我们刚才清洗的字典里遍历,可以得到我们由始发站可以到达的第一站,然后我们在依次遍历这些站。我们可以看到,我们先遍历一站就到的车站,然后再依次遍历两站可以到达的车站,依次类推,我们可以看到,我们遍历了所以我们到达的车站,是一层层遍历的,这里引出我们今天想说的,也就是广度优先遍历。举一个栗子,就是我们遍历一个大树,我们先优先获得主干,先看主干有没有我们想要的,没有,好,我们继续,在看枝干,然后再看叶子,也就是说我们的每一层是几乎同时遍历的搜索遍历的,与此相反,我们还有一个深度优先搜索,我们来看一下代码

def depth_first_search(start, arrive, connrction_grpah):
    pathes = [[start]]
    visitied = set()

    while pathes:
        path = pathes.pop(0)
        froninter = path[-1]

        if froninter in visitied:
            continue
        successors = connrction_grpah[froninter]

        for city in successors:
            if city in path:
                continue
            new_path = path + [city]
            pathes.append(new_path)

            if city == arrive:
                return new_path
        visitied.add(froninter)
        pathes = sorted(pathes, key=len, reverse=True)

和上一个代码几乎一样的,只不过加了一个排序,也是说,我们拿到了新的线路,我们还是会继续搜索该线路,直到该条路走不通了,我们才会继续走另外的路,也就是上面说的,我们先看大树的主干,然后看枝干,看叶子,再回过头来,再看另一个枝干,另一个叶子,这也就是我们说的深度优先搜索。

这篇博客写的比较仓促,时间比较紧,工作压力大,而且我也是第一次接触算法,很多知识还有待学习,开始的时候我认为我的python基础还可以,实操起来却不是那样了。

我们下篇博客回来说说导数和梯度下降,来得及就再说一下基于导数来作拟合的操作。

最近搞了一个个人公众号,会每天更新一篇原创博文,java,python,自然语言处理相关的知识有兴趣的小伙伴可以关注一下。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券