写在前面
- 最近在学习NLP的课程，下面的代码，基本来自我的NLP课程作业，当然大部分都是模仿老师写的，使用Python完成，感兴趣的可以去我的github上面查看：https://github.com/LiuPineapple/Learning-NLP/tree/master/Assignments/lesson-02
- 作者水平有限，如果有文章中有错误的地方，欢迎指正！如有侵权，请联系作者删除。
Search Based Model（基于搜索的模型）
广度优先搜索(BFS)与深度优先搜索(DFS)
广度优先搜索(Breadth First Search)与深度优先搜索(Depth First Search)是两种常用的搜索方法。两者之间的区别和算法网上有很多详细介绍，这里不再详述。
北京地铁路线搜索
使用爬虫，我们可以得到北京地铁的各个站点连接情况，由于作者现在还不能熟练使用爬虫，所以使用了班里同学的爬虫代码——欧同学的代码链接 在此表示感谢，这里不再展示，只展示爬虫的结果的一部分。我们可以看到，结果是一个字典，key是北京地铁所有的站点，value 是一个列表，列表中的元素是与key所代表的站点有一站距离的站点，也就是可以从key所代表的站点直接通往list中的站点。
图片1
接下来我们创建
search()函数，希望输入起点和终点，就能输出乘坐地铁的路线。
from collections import defaultdict
station_net = defaultdict(list)
station_net.update(station_connection)
def search(start,destination,graph):
routes = [[start]]
seen = set()
while routes:
route = routes.pop(0)
frontier = route[-1]
if frontier in seen: continue
for station in graph[frontier]:
if station in seen: continue
new_route= route + [station]
routes.append(new_route)
if station == destination: return new_route
seen.add(frontier)
上段代码中需要注意的地方有：
- Python defaultdict 的使用。https://www.jianshu.com/p/bbd258f99fd3
- Python3 set（集合）的使用。 https://www.runoob.com/python3/python3-set.html
- Python List pop()方法。https://www.runoob.com/python/att-list-pop.html
- Python 字典(Dictionary) update()方法。https://www.runoob.com/python/att-dictionary-update.html
- 这里使用了广度优先搜索(BFS)，如果要使用深度优先搜索(DFS)的话有两种方法，（1）
route = routes.pop(0)换成route = routes.pop(0)（2）new_route= route + [station]换成new_route= [station] + route，结果也可能会有所不同。
search()函数最后输出一个列表，里面的元素按顺序包括起点、终点以及其中所有的经过站。为了让结果更加美观，我们把列表合成一个字符串，站点之间用->连接。
def pretty_print(route):
return '->'.join(route)
pretty_print(search('天安门西','奥体中心',station_net))
'天安门西->西单->复兴门->阜成门->车公庄->西直门->积水潭->鼓楼大街->安德里北街->安华桥->北土城->奥体中心'
注意到，上端代码其实是默认了选取换乘最少的路线，如果我们增加一个选项，给routes排个序，就可能实现其他功能（比如选取换乘最少的路线，选取距离最短的路线等），这时候的搜索，既不是BFS也不是DFS。如下所示选取换乘最少的路线，其实跟上一个代码得到的结果相同。
def search(start,destination,graph,sort_candidate):
routes = [[start]]
seen = set()
while routes:
route = routes.pop(0)
frontier = route[-1]
if frontier in seen: continue
for station in graph[frontier]:
if station in seen: continue
new_route= route + [station]
routes.append(new_route)
if station == destination: return new_route
routes = sort_candidate(routes)
seen.add(frontier)
def transfer_stations_first(pathes):
return sorted(pathes, key=len)
pretty_print(search('西单','南锣鼓巷',station_net,transfer_stations_first))
'西单->灵境胡同->西四->平安里->北海北->南锣鼓巷'
最后，欢迎大家访问我的GitHub查看更多代码：https://github.com/LiuPineapple
欢迎大家访问我的简书主页查看更多文章：https://www.jianshu.com/u/31e8349bd083
