1 绪论

 1。1 引言

人工智能作为一门前沿和交叉项目，伴随着世界社会进步和科技发展的步伐，正在飞速的发展。由于人工智能的迅速发展与传播，促进了其他学科的发展，并在很多领域上都得到非常大的应用，具有非常大的意义。而图论作为人工智能的其中一个项目，它是计算机科学中的一个重要研究工具，它产生于欧拉（Euler）对图的连通性的研究，但直到本世纪才得最迅猛的发展。图论中的最短路径问题在计算机中有着广泛的应用，例如网络通信中最短路由的选择，人工智能中搜索算法的研究等。论文网

本文主要对在1968年发展起来的图论中的A*算法做一个介绍，并使用A*算法针对八数码问题进行了优化，使得用每次解决问题所花的步数是最少的。

1。2 八数码问题

八数码问题也被称为数独问题。如图1所示，在3×3的板上，放了八个数字，每个位置都标有1到8的一个数字，不同的位置的数字是不一样的。在板上有一个空格0，和空格相邻的数字可以移动到0的位置上去，最后需要在把图1的状态转化到图2的状态。要解决的问题是给一个初始状态和目标状态，找到一个最小数量的步骤，将数字顺序从初始状态改变到目标状态。所谓的问题是一个摆在棋盘上的棋子，棋子移动后，状态就会改变。解决八个数字问题实际上是找出初始状态到达目标状态的一系列中间过渡态。

    八数码问题一般使用搜索法来解。其中常用的搜索法有广度优先搜索法、深度优先搜索法、A*算法等。本文就从A*算法出发来解决八数码问题。

图1 初始状态                图2 目标状态文献综述

 1。3问题的搜索形式描述

状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：初始状态可以是任意一个状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的消耗是1，因此整个路径的消耗是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

1。4程序设计思路

图3  程序设计思路图

2 A*算法 2。1 A*算法背景介绍

提到了A*算法，我们首先需要知道的Dijkstra算法和最佳优先搜索（BFS）算法。

Dijkstra算法从对象的初始点开始，对图中的节点进行访问。它反复地检查节点中的节点，主要对最接近的节点进行检查并加入节点集。节点集从初始节点向外延伸，直到到达目的节点。Dijkstra算法可以从初始点到目标点的最短路径，找到一条路径，只要所有的边缘有一个非负的代价值。在下面的图片中，粉红色的节点初始节点，蓝色的是目标点，和类金刚石的颜色区域是Dijkstra算法扫描区域。最淡的区域是那些最远离初始点的，它们形成了检测过程的边界：来`自+优-尔^论:文,网www.youerw.com +QQ752018766-

图4   Dijkstra算法寻径原理

最佳优先搜索（BFS）算法运行在一个类似的过程中，不同点在于，它能够评估任意节点到目标点的代价。不同于从初始节点选择的最近的节点，它从目标选择最近的节点。BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快得多，因为它使用一个启发式函数（函数的启发式）迅速指引目标节点。例如，如果目标是位于南部的起点，他会倾向于引导路径南。在图中，更多的节点代表较高的值的启发式（移动到目标的高成本），而较暗的节点代表较低的启发式值（移动到目标的成本较低）。这表明，Dijkstra算法相比，算法运行速度更快。