A*搜索算法

A*搜索算法(以下简称 A*算法)是戴克斯特拉算法的扩展算法。A*算法用于寻找加权有向图中指定两点之间的最短路线,并且要求图中权重不为负。

戴克斯特拉算法中每一个节点只对应一个距离值,也就是起点到当前节点的路线距离。然而, A*算法中每一个节点对应两个距离值,第一个距离值和戴克斯特拉算法中的距离值相同,第二个距离值是当前节点到终点的预估距离。预估值的存在令 A*算法减少遍历的节点数量,从而使得结果输出更加快速。

但是预估值有一个条件限制,想要保证 A*算法输出正确的最短路线,节点的预估值必须小于或等于从节点到终点的真实距离。常见的预估值包括直线距离、曼哈顿距离和切比雪夫距离。预估值越接近真实值,算法越快速,因此 A*算法的时间复杂度在很大程度上取决于预估值。

预估值代表什么取决于算法当前解决什么问题。例如,如果我们在计算城市之间的最短路线,城市与城市之间的直线距离就是一个很好的预估值选择,因为直线距离只能小于或等于真实距离。

A*算法有三个条件限制:
  • 一是权重不能为负;
  • 二是预估值不能比实际值低;
  • 三是以下原则:

令 m,n 为任何节点,设 d(m,n) 为从 m 到 n 的最短距离,设 h(n),h(m) 为 n,m 的预估值,则

d(m,n)+h(n)≥h(m)


如图 1 所示,条件 3 的意思是,任何节点 m,n 之间的距离加上 n 的预估值必须大于或等于 m 的预估值。虽然这个条件不是很容易直观地理解,但是它是证明算法正确性时很重要的一个条件。
条件3
图 1:条件 3

1. 算法介绍

1) 第一步:设 A 为起点,F 为终点,并且视图中所有边为双向边。每一个节点对应着一个预估值,这个数值代表节点到终点的直线距离。比如,A 的预估值是 22,B 的预估值是 20。节点下面有两个框,实线的框记录着从起点到节点的当前距离,虚线的框记录着从起点经过节点再到终点,这条完整路线的预估值,虚线的框的值等于实线框里的值加上节点本身的预估值。

我们称实线框中的数值为节点的距离值,虚线框中的数值为节点的完整路线预估值,如图 2 所示。
A*例图(1)
图 2:A*例图(1)

初始时,除起点 A 的距离值与完整路线的预估值是 0 与 22,其余节点的两个值都是最大值,因为目前为止它们还没有找到任何路线。接下来,固定 A。固定代表A的距离值不会再改变。这里距离值仍然表示实线框里的值。因为 A 到自己的距离肯定是 0,所以 A 的距离值肯定不会变。

例表记录节点的整条路线的预估距离(浅色框里的数值)。已经固定的节点用加深色标记,如图 3 所示。
A*例表(1)
图 3:A*例表(1)

2) 第二步:松弛从 A 出发的边:AB、AC。A*算法中的松弛与戴克斯特拉算法中的松弛完全一样。在对比的过程中我们无视预估值与完整路线预估值,只关注节点的距离值。

首先松弛 AB,因为 0+4(A 的距离值+AB 权重)<MAX(B 的距离值),所以更新 B 的距离值为 4。接着,更新 B 的完整路线预估值为 B 的新距离值+B 本身的预估值,4+20。之前 B 的完整路线预估距离是 MAX,现在是 24。接下来松弛 AC,对比 MAX 和 0+7,更新 C 的距离值为 7,更新 C 的完整路线预估值为 23。

更新后我们得到例图,如图 4 所示。
A*例图(2)
图 4:A*例图(2)

在表中同样更新 B、C 的完整路线预估值,并且标记它们的前任节点,这样方便我们最后倒导出 AF 的最短路线,如图 5 所示。
A*例表(2)
图 5:A*例表(2)

3) 第三步:选择表中完整路线预估值最小的非固定节点:C。固定 C,和戴克斯特拉算法一样,我们可以确保 C 的距离值不会再改变,因为如果 C 改变路线,它的距离值只会增加,毕竟所有其他节点的距离值都大于它的距离值。从 C 出发的边有 CA、CB、CD、CE。

但是因为 A 已经被固定,所以松弛 CA 不再有任何意义,我们只需松弛 CB、CD、CE。
  • 松弛 CB:因为 7+4>4,所以不更新 B 的距离值。
  • 松弛 CD:因为 7+13<MAX,所以更新 D 的距离值为 21,更新 D 的完整路线预估值为 34。
  • 松弛 CD:因为 7+13<MAX,所以更新 D 的距离值为 21,更新 D 的完整路线预估值为 34。
  • 松弛 CE:因为 7+10<MAX,所以更新 E 的距离值为 17,更新 E 的完整路线预估值为 23。

更新后,如图 6 所示。
A*例图(3)
图 6:A*例图(3)

更新表中 D、E 的完整路线预估值,并且用深色标记节点 C,表示 C 已被固定,如图 7 所示。
A*例表(3)
图 7:A*例表(3)

4) 第四步:选择表中完整路线预估值最小的非固定节点:E。固定 E。从 E 出发的边有 EC、EB、ED、EF。但是因为 C 已经被固定,所以只松弛 EB、ED、EF。
  • 松弛 EB:因为 17+14>4,所以不更新 B 的距离值。
  • 松弛 ED:因为 17+9<21,所以不更新 D 的距离值。
  • 松弛 EF:因为 17+6<MAX,所以更新 F 的距离值为 23,更新 F 的完整路线预估值为 23。

更新后,如图 8 所示。
A*例图(4)
图 8:A*例图(4)

更新表中F的完整路线预估值并且用深色固定E,如图 9 所示。
A*例表(4)
图 9:A*例表(4)

5) 第五步:选择表中完整路线预估值最小的非固定节点:D。固定 D。从 D 出发的边有 DB,DC, DE,DF。但是因为 C 和 E 已经被固定,所以只松弛 DB,DF。
  • 松弛 DB:因为 21+11>4,所以不更新 B 的距离值。
  • 松弛 DF:因为 21+13<23,所以不更新 F 的距离值。

更新后的图和上一步一样,如图 10 所示。
A*例图(5)
图 10:A*例图(5)

6) 第六步:选择表中数值最小的非固定节点:F。固定 F。当我们知道 F 的距离值不会再改变时,可知 AF 的最短路线不会再更新。因此,虽然还有一个未固定节点 B,但我们仍然在此时结束算法,如图 11 所示。
A*例表(5)
图 11:A*例表(5)

通过图 11,我们可以倒导出 AF 的最短路线。在最后一行,我们首先查看 F 对应的格子 E-23,从而得知 F 的前任节点是 E。再看 E 对应的格子,得知E的前任节点是 C。同理可循,C 的前任节点是 A。因此,AF 的最短路线是 A→C→E→F。

2. 算法证明

我们通过数学归纳法来证明 A*算法的正确性。A*算法的正确性证明与戴克斯特拉算法的正确性证明几乎完全一样。我们需要证明的是:当节点 v 被固定时,v 已经找到了最短路线。因为在算法结束后终点被固定,所以如果我们证明成功,起点到终点的路线肯定是正确的最短路线。

1) 证明第一步:初始时只有起点被固定,起点的最短路线就是原地不动。这就是正确的路线。

2) 证明第二步:假定在第 k 次循环后,已被固定的 k 个节点已经找到了正确的最短路线。换句话说,一直到第 k 次循环,算法做的每一个决定都是正确的。

3) 证明第三步:在第 k+1 次循环中,算法固定距离值最小的非固定节点,称这个节点为 v*。

用 P(v*) 表示 v* 的当前路线,C(v*) 表示 v* 的正确最短路线。我们需要证明 P(v*)=C(v*)。也就是说,我们需要证明任何其他从 s 到 v* 的路线都比 P(v*)长。

假设路线 P(v*)=s→某些节点→v→v*。v 是 v* 的前任节点。我们知道 P(v*) 中只有 v* 是非固定节点。用 |P(v*)| 表示 P(v*) 的长度。|P(v*)|=|P(v)|+|(v,v*)|,又因为 v 在 v* 之前被固定,所以根据第二步的假定,P(v)=C(v)。因此 |P(v*)|=|C(v)|+|(v,v*)|。

接下来证明任何路线 P 都比 P(v*) 长。

令 P 为 s→某些固定节点→u→w→某些节点→v*,u 是固定节点,w 是非固定节点,而用“某些节点”代替的节点则没有条件限制。在指定情况下,“某些节点”与“某些固定节点”可以为空, s 可以等于 u,w 可以等于 v*。尝试在图中选择任何路线,P 肯定能够代表它。

P 的长度是 |P|=|P(u)|+|(u,w)|+|w→(…)→v*|。又因为 u 是固定节点,所以 |P|=|C(u)|+|(u,w)|+|w→(…)→v*|。

到目前为止我们有两个重要的结果:

|P|=|C(u)|+|(u,w)|+|w→(…)→v*|
|P(v*)|=|C(v)|+|(v,v*)|

因为 w 是未固定节点,所以在第 k+1 次循环时,它也是固定节点的候选之一。然而,v* 被选中固定而 w 没有,说明 w 的完整路线预估值大于或等于 v* 的完整路线预估值。

用 h(w) 代表 w 的预估值,h(v*) 代表 v* 的预估值。于是我们得到了第三个不等式:

|C(u)|+|(u,w)|+h(w)≥|C(v)|+|(v,v*)|+h(v*)


回忆 A*算法的第三个要求并且代入 w 与 v*:

d(w→(…)→v*)+h(v*)≥h(w)


利用以上不等式改写为:

|C(u)|+|(u,w)|+|w→(…)→v*|+h(v*)≥|C(v)|+|(v,v*)|+h(v*)


所以:

|C(u)|+|(u,w)|+|w→(…)→v*|≥|C(v)|+|(v,v*)|


代入 |p|≥|C(u)|+|(u,w)| 和 |p(v*)|=|C(v)|+|(v,v*)|,获得不等式:

|P|≥|P(v*)|

因为 P 可以是任何从 s 到 v* 的路线,所以我们证明了 P(v*) 比任何其他从 s 到 v* 的路线等长或更短。因此,P(v*) 是正确的。我们证明了在第 k+1 次循环中,被固定的节点肯定找到了最短路线。

4) 证明第四步:如果前 k 次循环算法正确,那么第 k+1 次循环算法一定正确。因为第 1 次循环算法正确,所以算法正确。

3. 算法代码

A*算法和戴克斯特拉算法几乎一样。我们需要传入每一个节点的预估值、一个起点和一个终点。
import sys
class Graph():
    def __init__(self):
        self.vertices = {}
        self.edges = []
        self.HValues = {}
    #添加边
    def addEdge(self, start, end, dist, biDirectFlag = True):
        if biDirectFlag:
            self.edges.extend([[start, end, dist],[end, start, dist]])
        else:
            self.edges.append([start, end, dist])
    #设预估值
    def setHValues(self, HValuesDict):
        self.HValues = HValuesDict
    #输出节点集合
    def getVertices(self):
    return set(sum(
        ([edge[0], edge[1]] for edge in self.edges), []
    ))
    #输出结果
    def printSolution(self, dist, predecessor, start, end):
        path = []
        path.append(end)
        pred = predecessor[end]
        while (pred!= None):
            path.append(pred)
            pred = predecessor[pred]
        path.reverse()
        print (start, "to ", end , " - Distance: ", dist[end], " Path :", path)
    #输出vertice节点的相邻节点
    def getNeighbours(self,vertice):
        neighbours = []
        for edge in self.edges:
            if edge[0] == vertice:
                neighbours.append([edge[1],edge[2]])
        return (neighbours)
    #输出tempVertices中距离值最小的节点
    def getCurrentV(self, tempVertices, HTotal):
        if len(tempVertices) == 0: return None
        return (min(tempVertices, key=lambda v: HTotal[v]))
    #检查有无负权重
    def checkForNegativeWeights(self):
        for edge in self.edges:
            if edge[2]<0:
            return True
            return False
    #A*算法,起点,终点
    def aStar(self, start, end):
        self.vertices = self.getVertices()
        if (len(self.vertices)!= len(self.HValues)):
            print("Missing Heuristic Value for some vertices")
            return
        if (self.checkForNegativeWeights()):
            print("Weights cannot be negative")
            return
        dist = {v: sys.maxsize for v in self.vertices}
        HTotal = {v: sys.maxsize for v in self.vertices}
        dist[start] = 0
        predecessor = {
                v: None for v in self.vertices
        }
        tempVertices = self.vertices.copy()
        currentV = start
        while end in tempVertices:
            neighbours = self.getNeighbours(currentV)
            for n in neighbours:
                if n[0] in tempVertices and dist[currentV] + n[1] < dist[n[0]]:
                    dist[n[0]] = dist[currentV] + n[1]
                    HTotal[n[0]] = self.HValues[n[0]]+ dist[n[0]]
                    predecessor[n[0]] = currentV
            tempVertices.remove(currentV)
            currentV = self.getCurrentV(tempVertices, HTotal)
        self.printSolution (dist, predecessor, start, end)
以上为算法代码,以下为实现例图:

graph = Graph()
graph.addEdge("a", "b", 4)
graph.addEdge("a", "c", 7)
graph.addEdge("b", "c", 4)
graph.addEdge("b", "d", 11)
graph.addEdge("b", "e", 14)
graph.addEdge("c", "d", 13)
graph.addEdge("c", "e", 10)
graph.addEdge("d", "e", 9)
graph.addEdge("d", "f", 13)
graph.addEdge("e", "f", 6)
graph.setHValues({"a":22, "b":20, "c":16, "d":13,"e":6,"f":0})
graph.aStar("a","f")

输出:

a to f - Distance: 23 Path : ['a', 'c', 'e', 'f']

如果我们用戴克斯特拉算法实现本小节的例图,并且将其运行速度与 A*算法的运行速度进行对比,我们会发现其实 A*算法并不比戴克斯特拉算法快速。这是因为例图非常简单,如果我们的例图更加庞大复杂,如一个城市的公交车线路图,或一个国家的铁路图,那么 A*算法的优势会更明显。