寫(xiě)在前面
- 最近在學(xué)習(xí)NLP的課程，下面的代碼稻据，基本來(lái)自我的NLP課程作業(yè)，當(dāng)然大部分都是模仿老師寫(xiě)的灶体，使用Python完成，感興趣的可以去我的github上面查看：https://github.com/LiuPineapple/Learning-NLP/tree/master/Assignments/lesson-02
- 作者水平有限策泣，如果有文章中有錯(cuò)誤的地方器罐，歡迎指正犹褒！如有侵權(quán)抵窒，請(qǐng)聯(lián)系作者刪除。
Search Based Model（基于搜索的模型）
廣度優(yōu)先搜索(BFS)與深度優(yōu)先搜索(DFS)
??廣度優(yōu)先搜索(Breadth First Search)與深度優(yōu)先搜索(Depth First Search)是兩種常用的搜索方法叠骑。兩者之間的區(qū)別和算法網(wǎng)上有很多詳細(xì)介紹李皇，這里不再詳述。
北京地鐵路線(xiàn)搜索
??使用爬蟲(chóng)宙枷，我們可以得到北京地鐵的各個(gè)站點(diǎn)連接情況掉房，由于作者現(xiàn)在還不能熟練使用爬蟲(chóng)，所以使用了班里同學(xué)的爬蟲(chóng)代碼——歐同學(xué)的代碼鏈接 在此表示感謝慰丛，這里不再展示卓囚，只展示爬蟲(chóng)的結(jié)果的一部分。我們可以看到璧帝，結(jié)果是一個(gè)字典捍岳，key是北京地鐵所有的站點(diǎn)富寿，value 是一個(gè)列表睬隶，列表中的元素是與key所代表的站點(diǎn)有一站距離的站點(diǎn)，也就是可以從key所代表的站點(diǎn)直接通往list中的站點(diǎn)页徐。
??接下來(lái)我們創(chuàng)建
search()函數(shù)苏潜，希望輸入起點(diǎn)和終點(diǎn)，就能輸出乘坐地鐵的路線(xiàn)变勇。
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 的使用恤左。http://www.reibang.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
- 這里使用了廣度優(yōu)先搜索(BFS)，如果要使用深度優(yōu)先搜索(DFS)的話(huà)有兩種方法链患，（1）
route = routes.pop(0)換成route = routes.pop(0)（2）new_route= route + [station]換成new_route= [station] + route巧鸭，結(jié)果也可能會(huì)有所不同。
search()函數(shù)最后輸出一個(gè)列表麻捻，里面的元素按順序包括起點(diǎn)纲仍、終點(diǎn)以及其中所有的經(jīng)過(guò)站。為了讓結(jié)果更加美觀贸毕，我們把列表合成一個(gè)字符串郑叠，站點(diǎn)之間用->連接。
def pretty_print(route):
return '->'.join(route)
pretty_print(search('天安門(mén)西','奧體中心',station_net))
'天安門(mén)西->西單->復(fù)興門(mén)->阜成門(mén)->車(chē)公莊->西直門(mén)->積水潭->鼓樓大街->安德里北街->安華橋->北土城->奧體中心'
??注意到明棍，上端代碼其實(shí)是默認(rèn)了選取換乘最少的路線(xiàn)乡革，如果我們?cè)黾右粋€(gè)選項(xiàng)，給routes排個(gè)序，就可能實(shí)現(xiàn)其他功能（比如選取換乘最少的路線(xiàn)署拟，選取距離最短的路線(xiàn)等）婉宰，這時(shí)候的搜索，既不是BFS也不是DFS推穷。如下所示選取換乘最少的路線(xiàn)心包，其實(shí)跟上一個(gè)代碼得到的結(jié)果相同。
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))
'西單->靈境胡同->西四->平安里->北海北->南鑼鼓巷'
最后馒铃，歡迎大家訪(fǎng)問(wèn)我的GitHub查看更多代碼：https://github.com/LiuPineapple
歡迎大家訪(fǎng)問(wèn)我的簡(jiǎn)書(shū)主頁(yè)查看更多文章：http://www.reibang.com/u/31e8349bd083
