启发式搜索算法在N数码问题中的应用.docx
《启发式搜索算法在N数码问题中的应用.docx》由会员分享，可在线阅读，更多相关《启发式搜索算法在N数码问题中的应用.docx（27页珍藏版）》请在冰点文库上搜索。
启发式搜索算法在N数码问题中的应用
编号
南京航空航天大学
毕业论文
题目
启发式搜索算法在N数码问题中的应用
学生姓名
学号
学院
专业
班级
指导教师
二〇一三年六月
南京航空航天大学
本科毕业设计（论文）诚信承诺书
本人郑重声明：
所呈交的毕业设计（论文）（题目：
启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。
尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。
作者签名：
年月日
（学号）：
启发式搜索算法在N数码问题中的应用
摘要
N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。
在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。
与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。
本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。
并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。
在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。
关键词：
启发式搜索，数码问题，A*算法，遗传算法
TheApplicationofHeuristicSearchAlgorithmonN-PuzzleProblem
Abstract
N-puzzleproblemisaclassicprobleminartificialintelligence.N-puzzleproblemcaneffectivelyjudgethemeritsofasearchalgorithm.Intheloworderpuzzleproblem,usingaDepth-First-SearchorBreadth-First-Searchcansolvetheproblem,butinthehigherorderdigital,becauseofthehugesearchspacearea,wemustadoptamoreintelligentalgorithm.Comparedwiththetraditionalsearchmethod,heuristicsearchusestheinformationinthesearchprocess,anditwillchoosethemostfeasiblestate,thusgreatlyimprovesthesearchqualityandefficiency.
ThispaperdesignsthestoragemechanismandmovementrulesofN-puzzleproblem,makingtheN-puzzleproblemtransformstoastandardsearchproblem.ThispaperfocusesontheapplicationofA*algorithmandgeneticalgorithminN-puzzleproblem,andtwodifferentevaluationfunctionusedinA*algorithm.TheobjectiveistocomparetheperformanceofdifferentvaluationfunctioninNdigitalproblem.Intheend,thispapercarriesoutalargenumberofexperiments,acomprehensiveanalysisoftheA*algorithmandgeneticalgorithmindifferentscaleofdata.
KeyWords：
HeuristicSearch;N-puzzleProblem;A*algorithm;Geneticalgorithm
目录
摘要i
Abstractii
第一章引言1
1.1N数码问题1
1.2启发式搜索2
1.2.1A*算法简介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.2A*算法9
2.3.3遗传算法11
第三章系统实现13
3.1数据结构实现13
3.1.1状态存储结构13
3.1.2优先级队列的实现14
3.2算法实现14
3.2.1A*算法14
3.2.2遗传算法15
第四章运行结果与讨论18
4.18数码实验结果分析18
4.215数码实验结果分析19
4.324数码实验结果分析21
第五章总结23
参考文献24
致谢25
第一章引言
1.1N数码问题
N数码问题在当前基本可分为8数码问题，15数码问题和24数码问题。
以15数码为例，就是在一个4×4的16宫格棋盘上，摆放有15个数码，即每一个放个中放有1至15中的一个数码。
棋盘中留有一个空格，允许其周围的某一个格子向空格移动，这样通过移动放个就可以使得数码排布得到改变。
这种求解的问题是：
给定一种初始的数码布局或结构（称为初始状态）和一个目标布局（称为目标状态），问如何移动数码，实现从初始状态到目标状态的转变，如图1所示。
在本文中目标状态默认为顺序状态，即如图1（b）所示。
简单来说，问题的实质就是寻找一个合法的动作序列，使得初始排列按照动作序列操作后得到一个顺序序列。
图1.115数码问题
与15数码类似，8数码和24数码只是在放个规模上有所区别，其他的移动规则与目标都是相同的。
15数码的起源可以追溯到1878年，美国魔术大师SamLoyd对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启发式搜索
启发式算法是一种基于深度优先搜索（DepthFirstSearch简称为DFS）的算法，即在每一个节点进行拓展时对其拓展所的到的新节点进行估价，从所有新节点中选择“最优秀”（由估价函数得到）的节点，再从这个节点位置进行搜索直到目标。
相对于普通的DFS，这样的过程更具有人工选择的感觉，故而被称为启发式搜索。
这样可以省略大量无谓的搜索路径，提高了效率。
显然，在启发式搜索中，对节点位置的估价是十分重要的，采用了不同的估价会对程序的效率、正确性都产生巨大的影响。
目前比较流行的启发算法有：
A*算法，遗传算法、模拟退火算法等。
1.2.1A*算法简介
小型的搜索问题我们可以通过遍历所有可行解来得到问题的最优解，这种方式最直观、最容易被人想到。
在搜索中，例如深度优先搜索，我们可以把整个遍历的过程看做是一棵树生成的过程，树上的每一个节点我们称为一个状态。
那么，搜索问题就是从根节点遍历出整棵树，从而得到一个最优解。
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模拟退火算法简介
模拟退火算法来自于冶金学中的专有名词退火。
退火是指将材料加热足够高的温度后按照特定的速率冷却，其作用是使其晶粒最终变得有序，使得内能变小，从而减小材料缺陷。
根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。
模拟退火便是根据金属退火理论加以延伸得到的：
我们将上述材料学的原理和统计学相结合，将搜索空间内的每一个状态看作是材料中的晶粒；而搜索空间内的每一个状态的适合度看作是，晶粒“能量”（内能）。
算法先以搜索空间内一个任意状态作起始：
每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
可以证明，模拟退火算法所得解依概率收敛到全局最优解。
模拟退火算法的基本步骤如下所示：
1随机生成一个初始解best＝x0，并计算目标函数值E（x0）;
2设置初始温度T（0）=T0，迭代次数i=1;
3whileT（i）>Tmindo
4forj=1tokdo
5根据当前最优解best生成一个新杰new
6ΔE=E（new）-E（best）
6ifΔE＜0thenbest=new；
7ifΔE＞0thenp=exp（-ΔE/T（i））;
8ifc=random[0,1]elsebest=best;
10i=i＋1；
11输出best
1.2.3遗传算法简介
被人们广泛接受的生物进化学说是达尔文的自然选择说。
我们将这种学说的进化过程变为一种计算模型，变产生了遗传算法。
自然选择说的核心在于，物种的进化来源于彼此的竞争，这些竞争对应于遗传算法中的选择操作（Selection），在生存竞争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多；这种变异行为对应于遗传操作中的交叉操作（Crossover）和变异操作（Mutation）。
遗传算法通过模拟整个种群的进化过程，最终可以得到最为优秀的个体，这个最优秀的个体即为问题的解。
由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：
染色体（Chromosome）：
染色体又可以叫做基因型个体（individuals）,一定数量的个体组成了群体（population）,群体中个体的数量叫做群体大小。
基因（Gene）：
基因是串中的元素，基因用于表示个体的特征。
例如有一个串S=1011，则其中的1，0，1，1这4个元素分别称为基因。
它们的值称为等位基因（Alleles）。
适应度（Fitness）：
各个个体对环境的适应程度叫做适应度（fitness）。
为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。
这个函数是计算个体在群体中被使用的概率。
下面具体描述一下遗传算法中的三种常见操作：
1．选择操作
通过估价函数来确定每个个体的适应度，选择适应度最好的个体保留。
2．交叉操作
在进化过程中，选择两个个体相同的位置进行交换，从而产生两个新的个体。
3．变异操作
在进化过程中，选择一个个体的某些部位进行变异。
第二章系统设计
在这一章中，将对N数码问题进行更具体的定义，并对其操作进行程序化的限制和定义，我们还论述了N数码问题的可解性。
2.1数据结构设计
直观上来讲N数码问题可以用二维结构来进行存储，但是为了表述和存储的方便，本文采用线性结构进行存储。
以15数码为例,有两种不同的线性存储方式：
（1）按从左向右、从上到下的顺序，任意棋局可惟一对应一序列P=ala2n3…a15a16。
其中ai（i=1～16）为0，1,…，15，十六个数中的一个，0表示空格，该序列P可采用一维数组S[1..n×n]存放，例如，图1.1（a）中初始棋局可存储为：
S
（1）=1，S
（2）=2，S（3）=3，S（4）=4，S（5）=5，S（6）=0，S（7）=6，S（8）=8，S（9）=9,S（10）=10,S（11）=7,S（12）=11,S（13）=13,S（14）=14,S（15）=15,S（16）=12
（2）棋局还能以S型顺序来存放。
即对第一行元素按从左到右的顺序依次存放，然后对第二行以从右向左顺序存放，第三行又与第一行存放方式相同，依此类推。
本文中采用
（1）中存储方式。
在以上数据结构的基础上，我们将用程序形式来定义N数码问题中所有的移动规则和移动操作，以便在算法中能够简单的表达所有可行的操作。
在N数码问题中，存在上移、下移、左移和右移四个操作，这四个操作可以看作是空格与上、下、左、右四个数码进行交换操作。
我们用i表示上述一维数组中元素0的下标，则s[i]就表示棋盘的空格。
当空格处于N数码上N-1行时，我们可以使用上移操作，即当且仅当
时，我们才可以使用上移操作。
同理，N数码的下移、左移、右移规则分别为N+1≤i≤N×N、imodN≠0、imodN≠1。
综上可构造出，N数码问题的移动规则，以及对应移动操作的程序表述：
上移操作：
if1≤i≤N×（N-1）thenswap（S[i],S[i+n]）;
下移操作：
ifn+1≤i≤（N×N）thenswap（S[i],S[i-n]）;
左移操作：
ifimod≠0，thenswap（S[i],S[i+1]）；
右移操作：
ifimodn≠1，thenswap（S[i],S[i-1]）;
（其中swap函数表示交换两个数的操作）
2.2UI设计
UI（UserInterface用户界面）设计的几个基本原则是：
简易性，一致性，清楚等。
本篇文章中所需要的系统UI应能够选择N数码的规模，即N的大小，并根据输入的N的大小规定所能输入数码的个数。
本文将提出A*算法的两种启发函数，一种遗传算法，我们的UI需要能够选择测试的算法，并且能够提供算法间的比较。
UI的输出相对比较简单，只需输出对应算法的搜索步数以及所搜得的结果。
于是我们设计出了以下界面如图2.1所示。
图2.1N数码问题UI
2.3算法设计
N数码问题是一种很常见的搜索问题，可以使用很多成熟的算法来解决，例如宽搜、深搜等，当然也可以使用人工智能中的启发式算法来进行求解，例如A*算法、模拟退火算法、遗传算法等，在这一节中我们将着重对启发式算法进行讨论。
2.3.1普通搜索算法
对于所有的搜索算法我们都可以使用树形结构来描述其搜索过程，如图3所示，从初始状态经过一步合法移动所能得到的所有状态形成了树的第二层，经过两步合法移动所得到的状态形成了树的第三层（图2.2中第三层并不完整），图三只是初始状态搜索出来的一种情况，不是所有的搜索方式都会产生这样的一棵搜索树。
图2,28数码问题搜索树
普通搜索算法主要可以分为宽度优先搜索（BreadthFirstSearch）和深度优先搜索（DepthFirstSearch）两种，深搜在搜索树上表现为先往层数深的地方搜索，而宽搜是一层层的搜索下去，由于搜索过程中会记录已到达过的状态，防止重复搜索，所以深搜和宽搜所得到的搜索树会有所不同。
2.3.2A*算法
对于15数码和8数码问题而言，A*算法可以有效地解决问题。
8数码问题规模相对较小，用任意的搜索算法都能很快的得出结果，当然如果要得到最优解，最方便的就是使用宽度优先搜索（BreadthFirstSearch简称为BFS），因为一旦宽度优先搜索搜到了结果，那么那个结果必然是最优秀的。
但如果我们想要对时间进行优化就双向宽搜，或者我们下面主要论述的A*算法。
然而对于15数码问题而言，数据规模扩大了许多倍，无论是BFS和DFS都没有办法胜任这一工作。
因为DFS的搜索深度可能会很深，会远远超过某个可行解的深度，然而DFS依然会孜孜不倦的深入下去；而BFS则会消耗大量的系统资源（内存或其他存储介质），这种消耗是目前我们无法接受的。
如果我们输出使用BFS和DFS解决15数码问题的整个移动过程，我们会发现，这两种搜索方法都会搜索到许多看起来更加错误的解，这种错误节点会对于DFS来讲会使得其进入一个很深的“死胡同”，对于BFS来讲会使得其浪费大量空间。
所以我们需要对搜索算法进行优化，在DFS中我们对扩展的节点进行评估，从而使得下一个搜索的节点尽可能的优秀，这样就能有效预防进入死胡同的情况。
很显然，估价函数的好坏将直接影响启发式算法的运行效率与结果，在八数码问题中我们可以使用f（n）=g（n）+h（n），其中g（n）表示当前层数，h（n）表示当前数码不在位置的个数，使用f（n）能够很好的解决8数码问题，其实若直接设置h（n）=0，即将A*算法退化为宽搜，也能解决该问题。
在解决15数码的问题中，本文结合8数码问题提出了一些新的估价函数：
f（n）=g（n）+q（n）公式1
其中g（n）表示结点n的深度，即从初始节点到当前节点n所用的最少步数，根结点深度为0；记当前不在正确位置的数码集合为M，取任意点k属于M，q（n）表示空格到点k的欧几里得距离加上点k到右下角的欧几里得距离和的最大值。
如图2.3所示情况，数码10、9、13不在位置分别计算其到空格位置的欧几里得距离加上其右下角的欧几里得距离的和，得到的结果为5、5、3，故而结果q（n）=5。
f（n）=g（n）+d（n）公式2
其中g（n）表示结点n的深度，根结点深度为0；d（n）表示结点n中的每一数码与其目标位置之间的欧几里得距离的总和。
图2.3d（n）函数计算示例
下面证明上述两个公式符合1.2.1节中的A*启发函数条件，简单来说即g（n）≥g'（n）且h（n）≤h'（n）（详细情况请参考1.2.1节）。
我们可以将式1写成f（n）=g（n）+h（n）的形式，其中h（n）=q（n），g（n）≥g'（n）显然成立，下面证明h（n）≤h'（n）:
我们可以很容易的看出，整个解N数码问题的过程就是空格移动到各个位置，最后回到右下角的过程，在这一过程中不是每一个位置空格都会到达，但是那些不在其位置上的数码空格必须到达，到达这些数码后空格必须返回右下角，考虑最优情况，显然使用h（n）步空格才能到达“最远的”点再回到右下角，至于其他的点是否还原我们还不能保证。
例如，图2.3所示，h（n）=5表示可以进行URRRD步操作是的空格到达10（或9）后回到右下角，这仅仅能够保证其可能产生了解。
所以综上所述h（n）≤h'（n），故而公式1满足A*启发式函数条件，可以被采用。
在式2中，g（n）≥g'（n）不用多家赘述。
我们使用d（n）作为启发函数，在最优情况下，每移动一次空格变会将一个数码到其目标位置的欧几里得距离减一，所以很显然d（n）≤h'（n）,所以式2符合作为A*启发式函数的条件，可采用。
2.3.3遗传算法
24数码的规模为25!
，通过测试，如用A*算法来解决需要2小时左右的时间，这显然是不能接受的，而遗传算法则可以有效的解决24数码问题。
遗传算法具有简单、通用、鲁棒性强等特点，适合在大规模复杂的搜索空间中寻找最优解。
对于数码问题，数码的移动可以看成等效的空格移动，空格周围的某个数码移动到空格中，相当于空格移动到了该数码中，通过空格的一系列连续的移动最终使得初始排列变换成目标排列，根据问题要求的规则，空格最多只能向上、下、左、右4个方向移动，这样空格从最初位置开始（初始排列中的空格的位置）经过合法的移动，最终形成目标排列时，其中所形成的方向序列即是该问题解空间中的一个解。
所以求解过程即是这样的一个方向序列，按照该序列，初始排列中的空格进行一系列的移动，若能到达目标排列则该方向序列就是要求的解。
用字母U,D,L,R表示4个方向，则染色体可编码为固定长度的由这4个数字组成的字符串。
本算法采用固定长度的染色体编码，其长度为算法的一个参数。
由于不是所有位置都能进行4个方向的移动，所以为了加强染色体的健壮性我们认为该染色体的某些基因位可能是不起作用的，即当按照某个基因位的方向，空格将产生非法的移动，则认为这个基因位不起作用，空格将选择下一个基因位表述的方向走。
我们还需要定义一个个体的适应值，从而起到启发式搜索的目的，在本文的遗传算法中，我们定义其适应值f为max{f1,f2,f3,…,fm}（m为染色体长度），其中fi可以描述为经过染色体上钱i次移动后，所形成的状态中已经在正确位置上的数码（含空格）个数。
下面我们介绍适用于N数码问题的几种遗传操作：
杂交算子：
采用传统的一点交叉算子。
例如：
个体A=RUDRLDLURDLRLDUL，个体B=LDDRLULRLDLLDRUD
随机取一位如第二位为交叉点，杂交后所得的个体A’为RUDRLDLRLDLLDRUD，个体B’为LDDRLULURDLRLDUL。
变异算子：
随机选取染色体中的某些位，进行随机产生{U,D,L,R}去替换这些位。
在遗传算法中我们首先要设定一些初始参
升级会员 