编号南京航空航天大学毕业论文题目启发式搜索算法在N数码问题中的应用学生姓名学号学院专业班级指导教师二〇一三年六月南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。
尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。
作者签名：年月日（学号）：启发式搜索算法在N数码问题中的应用摘要N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。
在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。
与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。
本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。
并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。
在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。
关键词：启发式搜索，数码问题，A*算法，遗传算法The Application of Heuristic Search Algorithmon N-Puzzle ProblemAbstractN-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency.This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data.Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm目录摘要 (i)Abstract (ii)第一章引言 (1)1.1N数码问题 (1)1.2启发式搜索 (2)1.2.1 A*算法简介 (2)1.2.2 模拟退火算法简介 (3)1.2.3 遗传算法简介 (4)第二章系统设计 (6)2.1数据结构设计 (6)2.2UI设计 (7)2.3 算法设计 (8)2.3.1 普通搜索算法 (8)2.3.2 A*算法 (9)2.3.3 遗传算法 (11)第三章系统实现 (13)3.1 数据结构实现 (13)3.1.1 状态存储结构 (13)3.1.2 优先级队列的实现 (14)3.2 算法实现 (14)3.2.1 A*算法 (14)3.2.2 遗传算法 (15)第四章运行结果与讨论 (18)4.1 8数码实验结果分析 (18)4.2 15数码实验结果分析 (19)4.3 24数码实验结果分析 (21)第五章总结 (23)参考文献 (24)致谢 (25)第一章引言1.1N数码问题N数码问题在当前基本可分为8数码问题，15数码问题和24数码问题。
以15数码为例，就是在一个4×4的16宫格棋盘上，摆放有15个数码，即每一个放个中放有1至15中的一个数码。
棋盘中留有一个空格，允许其周围的某一个格子向空格移动，这样通过移动放个就可以使得数码排布得到改变。
这种求解的问题是：给定一种初始的数码布局或结构(称为初始状态)和一个目标布局(称为目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如图1所示。
在本文中目标状态默认为顺序状态，即如图1(b)所示。
简单来说，问题的实质就是寻找一个合法的动作序列，使得初始排列按照动作序列操作后得到一个顺序序列。
图1.1 15数码问题与15数码类似，8数码和24数码只是在放个规模上有所区别，其他的移动规则与目标都是相同的。
15数码的起源可以追溯到1878年，美国魔术大师Sam Loyd对8数码问题进行了拓展[1][2]，推出了一种4×4智力玩具，这种游戏风靡一时。
后来这种游戏渐渐的演化成为了15数码问题。
虽然只是简单的将3×3的规模扩大成4×4，但是其规模却从8数码的9！（即362880）扩大至15数码的16！（约2.09×1013），使得原本很容易解决的问题变为了一个很具有挑战性的问题。
在一段时间内，15数码被作为一种评判搜索算法优秀程度的重要衡量指标。
然而近年来随着人工智能算法水平的提高15数码问题也得到了良好的解决，随之而来的便是问题规模更大的24数码问题。
另外，人们已经找到了判断N数码的可解性的方法：(1)对奇数阶棋盘，只有当初始状态所得序列的逆序数为偶数时有解。
[4](2)对偶数阶棋盘，只有当初始状态所得序列的逆序数加其空格所在行数所得结果为偶数时。
[4]1.2启发式搜索启发式算法是一种基于深度优先搜索（Depth First Search 简称为DFS）的算法，即在每一个节点进行拓展时对其拓展所的到的新节点进行估价，从所有新节点中选择“最优秀”（由估价函数得到）的节点，再从这个节点位置进行搜索直到目标。
相对于普通的DFS，这样的过程更具有人工选择的感觉，故而被称为启发式搜索。
这样可以省略大量无谓的搜索路径，提高了效率。
显然，在启发式搜索中，对节点位置的估价是十分重要的，采用了不同的估价会对程序的效率、正确性都产生巨大的影响。
目前比较流行的启发算法有：A*算法，遗传算法、模拟退火算法等。
1.2.1 A*算法简介小型的搜索问题我们可以通过遍历所有可行解来得到问题的最优解，这种方式最直观、最容易被人想到。
在搜索中，例如深度优先搜索，我们可以把整个遍历的过程看做是一棵树生成的过程，树上的每一个节点我们称为一个状态。
那么，搜索问题就是从根节点遍历出整棵树，从而得到一个最优解。
A*算法则是在生成整个树的过程中有选择性的去拓展树的节点。
通常我们对每个树结点（即问题状态）的代价进行估计，继而对预估代价最小的节点进行拓展。
在A*算法中，每个状态结点的估价函数是：f'(n) = g'(n) + h'(n)这里，n表示某个结点，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值，若能准确的计算出g'(n)与h'(n)即得到准确的预估代价f'(n)，那么我们就可以确定正确搜索顺序，从而完美的解决整个搜索问题。
但是，通常情况下这个f'(n)其实是无法预先知道的，所以我们用一个近似的估价函数f(n)。
我们使用从起点到终点的较短路径值g(n)代替g'(n)，满足g(n)≥g'(n)即可（这个条件一般默认满足，可以不用特加关注），从n到目标状态代价的估计h(n)代替h'(n)，满足h(n)≤h'(n)即可（显然在满足条件的情况下，h越大启发函数越优秀，故而这是启发函数的关键）。
于是我们可以得到以下的估价函数：f(n) = g(n) + h(n)可以使用反证法这样的估价函数是可以找到最短路径的，也就是可采纳的。
若取h(n)=0，显然h(n)肯定小于h'(n),即f(n)=g(n)表示节点所在层数,则A*算法就退化为了广度优先算法，我们可以将广度优先算法看做是A*算法的一个实例。
这种最小化h函数的方法是很容易想到和实现的，但是这种算法的效率也是很低的，其完全没有体现出算法的启发性。
通常h(n)是拥有实际意义的，例如在迷宫问题中通常使用当前节点到目标点的欧几里得距离作为h(n)。
h(n)可以看作是对节点n的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数的准确性就越高。
然而并不能说估价函数越精确它的效果就越好，因为本身计算h(n)也是需要付出代价的，极端情况下我们可以用遍历方法计算出精确的h(n)，即h(n)=h'(n)，然而这样做很显然使得整个算法退化成为了宽搜或者更糟。
所以，对于A*算法来说如何选取适当的h(n)将决定整个程序效率的关键。
1.2.2 模拟退火算法简介模拟退火算法来自于冶金学中的专有名词退火。
退火是指将材料加热足够高的温度后按照特定的速率冷却，其作用是使其晶粒最终变得有序，使得内能变小，从而减小材料缺陷。