纽约中央火车站
这是第二周学习笔记的第一部分:路线搜索。
理论学习问题:假如我们有若干个地点,现在想从地点 A 经过上述地点到地点 B,应该怎么走?
比如我们有如下地点:沈阳,北京,太原,郑州,兰州,西安,长沙,南宁,福州。现在我想从北京经过上述若干个城市到长沙,应该经过哪些城市?这是一个搜索路线的问题。我们首先做一些数据上的准备:- connections = {
- '北京': ['太原', '沈阳'],
- '太原': ['北京', '西安', '郑州'],
- '兰州': ['西安'],
- '郑州': ['太原'],
- '西安': ['兰州', '长沙'],
- '长沙': ['福州', '南宁'],
- '沈阳': ['北京'],
- '福州': ['长沙'],
- '南宁': ['长沙']
- }
复制代码 上面的意思是北京与太原、沈阳相连,以此类推。对于搜索问题,一个办法是遍历所有可能的路线。比如我们可以画出类似的网络图:
最上面的圆圈代表了第一站,下面的两个圆圈代表了可能的下一站,…我们的任务就是找到与下面目的地连接的一条的路线。
对于这样越往下分叉越多的情况,我们有两个策略进行遍历:
- 广度优先 broad first search
- 深度优先 depth first search
如何实现呢?老师给出了代码:- def broad_first_search(graph, start):
- """
- breath first search
- """
- visited = [start]
- seen = set()
- while visited:
- frontier = visited.pop()
- if frontier in seen: continue
- for successor in connections[frontier]:
- if successor in seen: continue
- print(successor)
- # visited = visited + [successor] # 我们每次扩展都扩展最新发现的点 -> depth first
- visited = [successor] + visited # 我们每次扩展都先考虑已经发现的老的点 -> breath first
- # 所以说,这个扩展顺序其实是决定了我们的深度优先还是广度优先
- seen.add(frontier)
- return seen
复制代码 试一下:- >>> broad_first_search('北京','福州')
- 长沙
- 南宁
- {'南宁', '福州', '长沙'}
复制代码 这是基于广度优先的搜索。深度优先只需要把- visited = [successor] + visited
复制代码 替换成- visited = visited + [successor]
复制代码 即可。因为这个网络太简单,深度优先和广度优先没有区别。
|
|