纽约中央火车站
这是第二周学习笔记的第一部分：路线搜索。
理论学习问题：假如我们有若干个地点，现在想从地点 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]
|
|
转播
