[Python] 人工智能与自然语言处理学习笔记(2)之一

论坛 期权论坛 期权     
老宅的数据科学之旅   2019-7-15 08:58   3586   0

纽约中央火车站
这是第二周学习笔记的第一部分:路线搜索。
理论学习
  • Search Based 基于搜索的模型
问题:假如我们有若干个地点,现在想从地点 A 经过上述地点到地点 B,应该怎么走?
比如我们有如下地点:沈阳,北京,太原,郑州,兰州,西安,长沙,南宁,福州。现在我想从北京经过上述若干个城市到长沙,应该经过哪些城市?这是一个搜索路线的问题。我们首先做一些数据上的准备:
  1. connections = {
  2.     '北京': ['太原', '沈阳'],
  3.     '太原': ['北京', '西安', '郑州'],
  4.     '兰州': ['西安'],
  5.     '郑州': ['太原'],
  6.     '西安': ['兰州', '长沙'],
  7.     '长沙': ['福州', '南宁'],
  8.     '沈阳': ['北京'],
  9.     '福州': ['长沙'],
  10.     '南宁': ['长沙']
  11. }
复制代码
上面的意思是北京与太原、沈阳相连,以此类推。对于搜索问题,一个办法是遍历所有可能的路线。比如我们可以画出类似的网络图:



最上面的圆圈代表了第一站,下面的两个圆圈代表了可能的下一站,…我们的任务就是找到与下面目的地连接的一条的路线。



对于这样越往下分叉越多的情况,我们有两个策略进行遍历:

  • 广度优先 broad first search


  • 深度优先 depth first search

如何实现呢?老师给出了代码:
  1. def broad_first_search(graph, start):
  2.     """
  3.     breath first search
  4.     """
  5.     visited = [start]
  6.     seen = set()
  7.     while visited:
  8.         frontier = visited.pop()
  9.         if frontier in seen: continue
  10.         for successor in connections[frontier]:
  11.             if successor in seen: continue
  12.             print(successor)
  13.             # visited = visited + [successor] # 我们每次扩展都扩展最新发现的点 -> depth first
  14.             visited = [successor] + visited # 我们每次扩展都先考虑已经发现的老的点 -> breath first
  15.             # 所以说,这个扩展顺序其实是决定了我们的深度优先还是广度优先
  16.         seen.add(frontier)
  17.     return seen
复制代码
试一下:
  1. >>> broad_first_search('北京','福州')
  2. 长沙
  3. 南宁
  4. {'南宁', '福州', '长沙'}
复制代码
这是基于广度优先的搜索。深度优先只需要把
  1. visited = [successor] + visited
复制代码
替换成
  1. visited = visited + [successor]
复制代码
即可。因为这个网络太简单,深度优先和广度优先没有区别。
分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:10
帖子:2
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP