机器学习之A*算法

admin管理员组

文章数量:1444620

机器学习之A*算法

本文将对比A*和Dijkstra算法的区别，并用和A*算法解决八数码问题

A*算法是一种能快速找出两点之间较短路线的算法。和Dijkstra算法相比，虽然它找到的路径可能不是最短的，但是它要高效很多，使得它的应用十分广泛（因为大多数时候我们对路径是否最短的要求不是很严格，只要较短就行）。

Dijkstra算法的思想是每次都找到起点到一个点的最短路径并更新起点到其他点的最短路径长度，这样就可以找到起点到其他所有点的最短路径。而A*算法只要搜索到了目标点，就结束算法。

简单理解：

代码语言：txt复制

    C

 4/ |

A   |1

 2\ |

    B

Dijkstra算法搜索到的A->C的最短路径长度是3，而A*搜索A->C的路径长度是4。

实验过程

1. 首先复习A*算法。使用网格图中寻找两点之间的一条路径为例。（这种情况下找到的应该是最短路径）
2. 然后思考八数码问题的A*算法解法，并将其推广到N数码。

复习A*算法

使用寻找最短路径比较经典的例子：网格图。如下图所示：

代码语言：txt复制

1  1  0  1

1  1  0  1

1  1  0  1

1  1  1  1

0表示障碍物，不能通行。寻找(0, 0)到(0, 3)的一条最短路径。

算法流程：

1. 创建两个表openSet和closeSet。openSet是一个优先队列，每次从中取出权值最小的元素。
2. 图中每个结点表示一个状态，**创建**一个4*4的矩阵记录对应的父节点，便于最后搜索到终点后一步步回溯父节点找到这条路径。
3. 将起点放入openSet中，开始循环，当openSet为空时，结束循环，表示问题无解。
4. 每次循环中取出openSet中优先级最高的元素，搜索它上下左右四个方向的结点。
5. 如果在closeSet中，忽略
6. 如果不在openSet中，加入openSet
7. 如果在openSet中，比较新的权值和以前的权值，选择权值最小的那一个更新权值和父节点。
8. 从终点回溯，使用栈来存储，最后再出栈，这样获得的顺序就是从起点到终点。

输出：

代码语言：txt复制

[(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (0, 3)]

解决N数码问题

刚复习完A*算法还真不好将它和八数码问题联系起来。不过想到八数码问题也是一个搜索问题，就能迎刃而解了。

八数码问题对应 $9!=362880$ 种棋子状态，要搜索的状态空间比上面的网格图要多很多（之前是一个网格一个状态，八数码问题是棋子的一种排列就是一个状态），如果使用BFS或DFS这种盲目的搜索算法，要搜索很久，效率极低。这时候就可以使用启发式搜索来进行有目的的搜索。

思想大同小异，依然创建openList和closeList两个表。只是状态太多，不可能像网格图那样创建矩阵来记录父状态，所以需要定义状态的数据结构：

代码语言：python代码运行次数：0运行复制

class State():

    def __init__(self, cur: list, pre = None):

        self.cur = cur

        self.pre = pre  # 如果是C语言的话，这里应该使用State的指针形成链表

    def __repr__(self):

        return f"{self.cur}"

需要注意这里的pre属性应该存储父状态的指针，即pre也应该是State类型，便于回溯。Python对于比较复杂的类型默认传的就是地址，一旦没有变量指向这个地址，对应的空间就会被自动回收。所以还需要专门将它们存储起来，用类中的path属性完成：

代码语言：python代码运行次数：0运行复制

class Solution(object):

    # 初始化问题的参数

    def __init__(self, d: int, g: list, t: list, m = 1):

        # @dimension: 3代表八数码，4代表15数码，依次类推

        # @graph: 初始状态，用一维数组表示

        # @target: 目标状态，用一维数组表示

        # @method: 计算价值函数时选择的方法

        self.dimension = d

        self.graph = g

        self.target = t

        self.method = m

        self.path = []  # 记录搜索过的状态

另外15数码的状态空间为 $15!=20922789888000$ 已经十分大了，所以维度为4基本上已经是极限了。维度为5及以上可能得跑大半天，所以脚本中只给了八数码和十五数码各两个例子。其他就没有什么好说的了，详见代码：

本文标签： 机器学习之A*算法