浅议GPS算法

Published on 2018 - 06 - 22

GPS中可以计算出点A到点B的最短路径,最近在研究算法,突然得到灵感,大胆的猜测了一下GPS中用到的算法。从广度优先搜索算法开始,逐步推论到狄克斯特拉算法
转载请带上作者姓名与网站小停雨的博客

广度优先搜索

首先说说什么是图:

它们不涉及x轴y轴,广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!

比如:

  1. 耗时最少
  2. 距离最短
  3. 路线最少

再说收广度优先搜索的作用:

  1. 编写国际跳棋AI,计算最少走多少步就可以获胜
  2. 编写拼写检查器,计算最少编辑多少个地方就可以将拼错的单词改成正确的单词,如将READED改为READER,总共需要编辑一个地方就是字母D改为字母R
  3. 根据你的人际关系网络找到关系最近的医生(作家,律师,无论什么职业)

假设你居住在双子峰,要从双子峰前往金门大桥。你想乘公交车前往,并希望换成最少。可乘坐的公交车如下。

Image

为了找出最少的换成路线,你将使用什么样的算法?

要确定如何从双子峰前往金门大桥,需要两个步骤
  1. 使用来建立问题模型
  2. 使用广度优先搜索解决问题

我们都知道,二分查找是一种针对有序数据的查找算法。

广度优先搜索是一种用于图的查找算法,可帮助回答两类问题:

  1. 从节点A出发,有前往节点B的路径吗?
  2. 从节点A出发,前往节点B的哪条路径最短?

下面假设,你现在需要在朋友圈中寻找一位律师,为此,我们可以在朋友中查找。这种查找很简单,首先创建一个朋友名单。然后一次检查名单中的每个人,看看他是否是芒果销售商。但是你没有朋友是律师,那么久必须在朋友的朋友中去查找。所以在检查每个人时,都需要将其朋友加入名单。

Image

这样一来,不仅可以在朋友中查找,还可以在朋友的朋友中查找。

队列

因为我们认为一度人脉,也就是你的朋友才是最近最好的选择,可是因为你没有朋友是律师,所以迫不得已才在二度人脉中去查找,也就是朋友的朋友。所以我们的需求就是,按顺序查找,在查找完一度人脉之后,再来继续查找二度人脉。

在继续向下说之前,必须要先说一下队列,队列顾名思义就像我们先生生活中的排序一样,先加入队列的元素要比后加入队列的元素之前出队。因此,我们可以使用队列来表示查找名单。这样先加入的人将先出队并先被检查。顺便提一句,是一种后进先出的数据结构,所以无法满足我们的要求。

代码实现

人际关系图:

Image

代码如下:

# -*- 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)

图例:

下面来看看如何对下面的图使用这种算法:

Image

其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用狄克斯特拉算法。

如果我们使用之前的广度优先搜索算法,将得到下面这条段数最少的路径:

Image

这是段数最少的路径,但却不是耗时最短的路径,按照广度优先搜索计算得到的这条路径总耗时要7分钟。下面我们来看看能否找到耗时更短的路径!

狄克斯特拉算法包含4个步骤:

  1. 找出成本最低(low cost)的节点,即:可在最短时间内到达的节点。
  2. 更新该节点的邻居的开销
  3. 重复这么过程,直到对图中的每个节点都这样做了。
  4. 计算最终路径。

代码实现

# -*- 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()

再次解释一下代码的逻辑思路

  1. 你站在起点,不知道该前往点A还是前往点B。前往这两个节点都要多长时间呢?
    • 前往节点A要6分钟,而前往节点B需要2分钟。至于前往其他节点,你还不知道需要多长时间。
    • 由于你还不知道前往终点需要多长时间,因此你假设为无穷大。节点B是最近的—— 2分钟就能到达。
  2. 计算经节点B前往其各个邻居所需的时间。
    • 你刚找到了一条前往节点A的更短路径,直接前往节点A需要6分钟
    • 但经由节点B前往A节点只需要5分钟
    • 对于节点B的邻居,如果找到前往它更短路径,就更新其开销,所以我们找到了:
      • 前往节点A的更短路径(时间从6分钟缩短到5分钟)
      • 前往终点的更短路径(时间从无穷大缩短到7分钟)
  3. 重复
    • 重复第一步,找出可在最短时间内前往的节点。
      • 找出可在最短时间前往的节点。你对节点B执行了第二步,除节点B外,可在最短时间内前往的节点是节点A
    • 重复第二步,更新节点A的所有邻居的开销。
      • 你发现前往终点的时间为6分钟
      • 你对每个节点都运行了狄克斯特拉算法(无需对终点这样做)。现在,你知道:
      • 前往节点B需要2分钟
      • 前往节点A需要5分钟
      • 前往终点需要6分钟
  4. 最后一步,计算最终路径。

小结

  • 广度优先搜索用于在非加权图中查找最短路径。
  • 狄克斯特拉算法用于在加权图中查找最短路径。
  • 仅当权重为正时狄克斯特拉算法才管用。
  • 如果图中路线包含负值,不可以使用狄克斯特拉算法。需要使用贝尔曼-福德算法。

参考资料《算法图解》第七章
转载请带上作者姓名与网站小停雨的博客