浅议GPS算法
GPS中可以计算出点A到点B的最短路径,最近在研究算法,突然得到灵感,大胆的猜测了一下GPS中用到的算法。从
广度优先搜索
算法开始,逐步推论到狄克斯特拉
算法
转载请带上作者姓名与网站小停雨的博客
广度优先搜索
首先说说什么是图:
它们不涉及x轴y轴,广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!
比如:
- 耗时最少
- 距离最短
- 路线最少
再说收广度优先搜索的作用:
- 编写国际跳棋AI,计算最少走多少步就可以获胜
- 编写拼写检查器,计算最少编辑多少个地方就可以将拼错的单词改成正确的单词,如将READED改为READER,总共需要编辑一个地方就是字母
D
改为字母R
- 根据你的人际关系网络找到关系最近的医生(作家,律师,无论什么职业)
假设你居住在双子峰,要从双子峰前往金门大桥。你想乘公交车前往,并希望换成最少。可乘坐的公交车如下。
为了找出最少的换成路线,你将使用什么样的算法?
要确定如何从双子峰前往金门大桥,需要两个步骤
- 使用
图
来建立问题模型 - 使用广度优先搜索解决问题
我们都知道,二分查找是一种针对有序数据的查找算法。
广度优先搜索是一种用于图的查找算法,可帮助回答两类问题:
- 从节点A出发,有前往节点B的路径吗?
- 从节点A出发,前往节点B的哪条路径最短?
下面假设,你现在需要在朋友圈中寻找一位律师,为此,我们可以在朋友中查找。这种查找很简单,首先创建一个朋友名单。然后一次检查名单中的每个人,看看他是否是芒果销售商。但是你没有朋友是律师,那么久必须在朋友的朋友中去查找。所以在检查每个人时,都需要将其朋友加入名单。
这样一来,不仅可以在朋友中查找,还可以在朋友的朋友中查找。
队列
因为我们认为一度人脉,也就是你的朋友才是最近最好的选择,可是因为你没有朋友是律师,所以迫不得已才在二度人脉中去查找,也就是朋友的朋友。所以我们的需求就是,按顺序查找,在查找完一度人脉之后,再来继续查找二度人脉。
在继续向下说之前,必须要先说一下队列,队列顾名思义就像我们先生生活中的排序一样,先加入队列的元素要比后加入队列的元素之前出队。因此,我们可以使用队列来表示查找名单。这样先加入的人将先出队并先被检查。顺便提一句,栈
是一种后进先出的数据结构,所以无法满足我们的要求。
代码实现
人际关系图:
代码如下:
# -*- coding:utf-8 -*-
from collections import deque
# 创建视图内容
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
search_queue = deque()
search_queue += graph["you"]
def person_is_lawyer(name):
"""
模拟一位律师,假设名字最后一位是m的人,就是律师
:param name:传入的每一个名字
:return:
"""
return name[-1] == 'm'
def fn_search(search_queue):
"""
寻找律师主函数, 为了防止视图死循环,加入了判断.
:param search_queue:创建一个双端队列(此处为左出右进)
:param person 从队列中取出的每一个人名
:return:
"""
searched = [] # 这个数组用于记录检查过的人
while search_queue: # 只要队列不为空,
person = search_queue.popleft() # 就取出其中第一个人
if person not in searched: # 仅当这个人没检查过时才检查
if person_is_lawyer(person): # 检查这个人是否是律师
print(person + " is a lawyer!") # 是律师
return True
else:
search_queue += graph[person] # 不是律师。将这个人的朋友都加入到搜索队列
searched.append(person) # 将这个人标记为检查过
return False # 如果到达了这里,就说明队列中没有人是律师。
fn_search(search_queue)
研究好广度优先索索
算法之后,我们发现它只能找出从A点到B点的最短路径,
这是最短路径,因为段数最少-----只有三段,但不一定是最快的路径。如果给这些路段加上时间,你讲发现有更快的路径。
就像我们平时用百度寻路,有少换成,少步行,时间最短灯选项一样。 我们出行还是偏向于选择耗时最少
的路线。
小结
广度优先搜索
指出是否有从A到B的路径- 如果有,
广度优先搜索
将找出最短路径 - 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用
广度优先搜索
来解决问题 - 有向图中的边为箭头,箭头的方向指定了关系方向,例如,rma ---> adit 表示rama欠adit钱。
- 无向图中的边不带箭头,其中的关系是双向的,例如,ross --- rachel表示 ross与rachel约会,而rachel也与ross约会。
- 队列是先进先出(FIFO)的
- 栈是后进先出(LIFO)的
- 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列。
- 对于检查过的人,务必不要再去检查,否则可能导致无限循环
狄克斯特拉算法
上一小节说了我们真正需要的是,耗时最短的路径,而不是线段最少的,那么如何能找到耗时最短的路径呢? ——狄克斯特拉算法。(Dijkstra's algorithm)
图例:
下面来看看如何对下面的图使用这种算法:
其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用狄克斯特拉算法。
如果我们使用之前的广度优先搜索
算法,将得到下面这条段数最少的路径:
这是段数最少的路径,但却不是耗时最短的路径,按照广度优先搜索
计算得到的这条路径总耗时要7分钟。下面我们来看看能否找到耗时更短的路径!
狄克斯特拉
算法包含4个步骤:
- 找出
成本最低(low cost)
的节点,即:可在最短时间内到达的节点。 - 更新该节点的邻居的开销
- 重复这么过程,直到对图中的每个节点都这样做了。
- 计算最终路径。
代码实现
# -*- coding:utf-8 -*-
# 创建graph视图表
graph = dict()
graph["you"] = ["alice", "bob", "claire"]
graph["start"] = dict()
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = dict()
graph["a"]["fin"] = 1
graph["b"] = dict()
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = dict()
# 创建节点开销表
infinity = float("inf")
costs = dict()
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 创建父节点散列表
parents = dict()
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 创建一个数组,用来记录已经处理过的节点.
processed = list()
def find_lowest_cost_node(_costs):
"""
找出开销最低的节点
:param _costs:
:return:
"""
lowest_cost = float("inf") # 定义默认开销无穷大
lowest_cost_node = None
for node in _costs: # 遍历所有的节点
cost = _costs[node]
if cost < lowest_cost and node not in processed: # 如果当前节点的开销更低且未处理过,
lowest_cost = cost # 就将其视为开销最低的节点.
lowest_cost_node = node
return lowest_cost_node
def dijkstra():
"""
迪克斯特拉算法
:param node: 获取的一个节点
:return:
"""
node = find_lowest_cost_node(costs) # 在未处理的节点中找出开销最小的节点
while node is not None: # 这个while循环在所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): # 遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: # 如果经当前节点前往该邻居更近
costs[n] = new_cost # 就更新邻居的开销
parents[n] = node # 同时将该邻居的父节点设置为当前节点
processed.append(node) # 将当前节点标记为处理过
node = find_lowest_cost_node(costs) # 找出接下来要处理的节点,并循环
dijkstra()
再次解释一下代码的逻辑思路
- 你站在起点,不知道该前往点A还是前往点B。前往这两个节点都要多长时间呢?
- 前往节点A要6分钟,而前往节点B需要2分钟。至于前往其他节点,你还不知道需要多长时间。
- 由于你还不知道前往终点需要多长时间,因此你假设为无穷大。节点B是最近的—— 2分钟就能到达。
- 计算经节点B前往其各个邻居所需的时间。
- 你刚找到了一条前往节点A的更短路径,直接前往节点A需要6分钟
- 但经由节点B前往A节点只需要5分钟
- 对于节点B的邻居,如果找到前往它更短路径,就更新其开销,所以我们找到了:
- 前往节点A的更短路径(时间从6分钟缩短到5分钟)
- 前往终点的更短路径(时间从无穷大缩短到7分钟)
- 重复
- 重复第一步,找出可在最短时间内前往的节点。
- 找出可在最短时间前往的节点。你对节点B执行了第二步,除节点B外,可在最短时间内前往的节点是节点A
- 重复第二步,更新节点A的所有邻居的开销。
- 你发现前往终点的时间为6分钟
- 你对每个节点都运行了狄克斯特拉算法(无需对终点这样做)。现在,你知道:
- 前往节点B需要2分钟
- 前往节点A需要5分钟
- 前往终点需要6分钟
- 重复第一步,找出可在最短时间内前往的节点。
- 最后一步,计算最终路径。
小结
广度优先搜索
用于在非加权图中查找最短路径。狄克斯特拉
算法用于在加权图中查找最短路径。- 仅当权重为正时
狄克斯特拉
算法才管用。 - 如果图中路线包含负值,不可以使用
狄克斯特拉
算法。需要使用贝尔曼-福德
算法。
参考资料《算法图解》第七章
转载请带上作者姓名与网站小停雨的博客