一、遗传算法简介

1、概念

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

2、思想

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体 (chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

3、过程

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授19xx年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：式中x为决策变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。

遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些

现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。

遗传算法的基本运算过程如下：

a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

b)个体评价：计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。 f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

二、遗传算法在图像处理方面的应用

1、 基于遗传算法的图像增强

遗传算法( genetic algorithm, GA)是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的进化原则。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国

Michigan大学的Holland教授提出,其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用中越来越展示出优越性。

图像处理是计算机视觉中的一个重要研究领域,在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求, GA 在这些图像处理中的优化计算方面找到了用武之地,目前已在图像分割、图像恢复、图像重建、图像检索和图像匹配等方面得到了广泛的应用[ 1～3 ] 。

图像增强就是将原来不清楚的图像变得清晰或把某些特征强调出来,以改善图像的视觉效果或便于对图像进行其他处理[ 1 ] 。图像增强技术主要有频域法、空域法。频域法是把原图像进行某种变换如傅里叶变换,小波变换) ,在变换域中进行处理以达到增强的目的,空域法直接对原始图像进行处理,主要包括直接灰度变换、直方图均衡、平滑滤波等。基于GA的图像增强技术的实现过程实际上是 一个寻找控制参数的最优或次优解的过程,因此,首先要选择一个参数模型。卢丽

[ 5 ]敏等人采用如下的参数模型:设错误！未找到引用源。是图像在x行y列的像素值,

错误！未找到引用源。为增强后的图像在对应点的像素值,则有

其中,错误！未找到引用源。是一个对比扩展函数,错误！未找到引用源。为x行y列处像素点在它的某个领域内的局部均值,错误！未找到引用源。是一个控制参数, 其大小影响到图像的处理质量, 因此图像增强过程转化为寻求最优参数k 的过程。文献[6]则把问题转化为另外的模型, 确定不同的参数来达到同样的目的。文献[7]对图像进行模糊增强处理,给出一种新的模型,使用GA对图像模糊增强的灰度阈值进行优化选择,同时改进了GA。文献[ 8 ]采用GA来确定Beta函数错误！未找到引用源。中α,β值,实现图1中所示的4类变换曲线的自动拟合。提出了自适应多位变异算子,很好地把二进制与十进制编码的优点相结合,使GA搜索性能更加优良,提高了种群的稳定性。实验证明该方法不仅具备较强的自适应能力,在获得最优或近似最优解时,极大节约处理时间,明显优于穷举法,适合对大图像库的自动化处理。

图 1 变换曲线

GA 用于图像增强能得到更好的增强效果 , 但从时间上考虑 , 对图像进行寻优速度较慢 , 可考虑用并行 GA, 是一个值得研究的课题。

2、基于遗传算法的图像恢复

图像恢复就是把一个退化 ( 或劣化 ) 图像尽量恢复到它的原始面目 , 是数字图像处理中的一个重要分支。目前已提出许多有效的图像恢复方法 , 如逆滤波法、 维纳滤波法、 奇异值分解伪逆法、 最大熵恢复法等[10] 。由于引起图像退化的原因未知或不能用函数表达 , 使得上述方法面临较多的约束问题或是计算量过大问题 , 由于难以确定退化函数 h , 限制了其实际应用的效果。GA 用于灰度图像的恢复 , 一般将染色体编码成以各像素的灰度值为元素的 2 维矩阵 , 即一个染色体就代表一幅图像 , 每个基因对应一个像素 , 采用自然数编码。每个个体的适应度函数为

其中 , f i 为个体 i 代表的推测恢复图像 , g 为观测到的退化图像 , h 为退化过程 , 函数值越大表示个体越好。在交叉操作时一般采用窗口交叉 , 即在父代染色体矩阵中选择相同大小的窗口 , 进行交换。变异操作采用临近小范围内的平均值替换需要变异的某一基因值。

文献 [11] 以图像中像素的灰度相对等级作为模糊特征 , 把图像模糊特征矩阵中的元素 ( 隶属度) ,转换成遗传空间上的基因 ; 即基因为 P i j /X i j 表示图像中第 ( i, j) 点像素具有某种特征的程度 , 相应的适应度函数为 G(y(fi))?Gg?h*fi~def~~F(fi)?g?h*fi2

其中, G(*) 表示模糊集 *的重心 ; fi 是第 i 个个体代表的推测图像模糊集 , g 是观测到的退化图像模糊集。文献 [ 12 ] 针对上述问题提出一种基于多种群遗传算法的图像恢复方法 , 低层遗传保证了搜索的充分性和收敛结果的全局最优性 ; 高层遗传使各子群能共享低层遗传所得的优良基因模式 , 以防止向局部最优收敛。此外 , GA 也用于彩色图像的恢复[13], 取得了很好的效果。

基于 GA 的图像恢复方式 , 突破了原有的理论 ,而且其开放的结构易于与其他方式融合 , 如与模糊逻辑相结合的模糊 GA 等。利用 GA 恢复图像不仅较好的克服了噪声的影响 , 而且使图像更平滑 , 边缘没有条纹效应 , 视觉效果好。强大的全局搜索能力是遗传算法图像恢复方法行之有效的主要原因。值得指出的是 , 用 GA 进行图像恢复的计算量很大 , 而且图像恢复属于不良设定问题 , 解又不是唯一的 , 因此应改进编码技术 , 解决通常 GA “ 早熟 ” 问题 , 以及使用大的群体规模 , 依赖于选择和交叉算子来提高图像恢复的质量。

3、遗传算法在图像重建中的应用

图像重建是由在某种观测方式下得到的携带图像信息的数据恢复出原图像的过程。获得目标投影数据的不同方法 , 决定了图像重建问题求解的方法学。由这种方法学所产生的重建方法主要有代数法、 迭代法和傅里叶变换法等。 GA 应用于图像重建主要解决从带有噪声的投影数据恢复图像。 Knoll 等人

[14] 提出一种遗传重建算法 ( GRA) 。 GRA 主要用来最小化被测像素值Zijk0 和计算的射线总和Sijk0之间的差。染色体定义为体素 ( voxel ) 值 , 初始种群的

nxnynz?染色体随机取 [1 ,255] 区间的值 , 适应度函数为

ERay

i,j,k?1? 其中 , i, j, k 分别表示被测目标的 x, y 和 z 坐标 , 成像设备的角度1?nxnynz??位置表示为θ ;

下面条件计算 : nx,ny,nz表示被测 3 维目标的矩阵尺寸 ; 射线总和

corrSijk0 按

IfvoxelVijk?Ray?Sijk0?Sijk??vijk?Vijk

elseSijk??Sijk?

为了提高搜索速度 , 采用并行的遗传算法来实现 , 对有噪声的数据集进行实验 , 效果特别好。Susumu 等人[15 ] 提出了一种遗传松弛迭代傅里叶变换算法 (GRIFTA) , 解决图像重建时产生停滞现象的问题 , 即重建图像的效果受初始集合选择的影响。染色体直接采用图像的 2 维遗传编码 ; 适应度函数定义为 J(fn)?P2fn?fn ; 选择合适的种群规模、 交叉率和变异率。仿真实验结果证明 , 上述方法可以正确重建图像而不依赖初始集合的选择 , 另外该算法比常

规的迭代傅里叶变换算法速度更快。Yu 等人[16]在假设组成目标的点是分散情况下, 用线性模型拟合方式来重建高分辨率雷达图像。利用GA 的全局寻优特性来最小化拟合的误差 , 实验结果证实能得到非常精确的结果。将 GA 应用于图像的重建还是一个正在探索的课题 , 目前给出的方法都是有益的尝试 , 存在一些问题 , 比如速度一般较慢、 重建出的图像边缘不清等 ,还需要进一步改进。

【参考文献】

[1] 章毓晋著 . 图像处理和分析 ( 第1 版 ) [M ]. 北京 : 清华大学出版 社 , 1999.

[2] 林磊 , 王晓龙 , 刘家锋 . 基于遗传算法的手写体汉字识别系统优化方法的研究 [ J ]. 计算机研究与发展 ,2001, 38 (6) : 658 ～ 661.

[3] 刘智明 , 周激流 .

基于遗传算法的有效人脸检测法 [J ]. 计算机辅助设计与图形学学报 , 2002, 14(10) : 940 ～ 944.

[4]陈国良 , 王熙法 , 庄镇泉等著 . 遗传算法及其应用 [M ]. 北京 : 人民邮电出版社 ,1996.

[5] 卢丽敏 , 周海银 . 一种基于遗传算法的图像增强方法 [J ]. 数学理论与应用 , 2003, 23(1) : 82 ～ 88.

[6]李宏贵 , 李兴国 , 李国桢等 . 一种基于遗传算法的红外图像增强方法 [J]. 系统工程于电子技术 , 1999, 21(7) : 44 ～ 46.

[7] 陈佳娟 , 陈晓光 , 纪寿文等 . 基于遗传算法的图像模糊增强处理 方法 的 研 究 [ J ]. 计 算 机 工 程 与 应 用 , 2001, 37 ( 21 ) : 109 ～ 111.

[8] 周激流 , 吕航 . 一种基于新型遗传算法的图像自适应增强算法的研究 [J ]. 计算机学报 , 2001, 24(9) : 959 ～ 964

第二篇：人工智能关于八数码问题论文

人工智能关于八数码问题论文

摘要：

八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A算法的可采纳性等及系统的特点。关键词九宫重排，状态空间，启发式搜索，A算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有４个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。

一、 问题描述

1.1 待解决问题的解释

八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

1.2 问题的搜索形式描述（4要素）

初始状态：

8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。

后继函数：

通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状

态。

目标测试：

比较当前状态和目标状态的格局是否一致。

路径消耗：

每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。

1.3 解决方案介绍（原理）

对于八数码问题的解决，首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵？由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。

如果初始状态可以到达目标状态，那么采取什么样的方法呢？

常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)

其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中，

显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。

二、 算法介绍

2.1 搜索算法一般介绍

不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。

搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。

为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相

当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，

考虑到八数码问题的特点，在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。

2.2 算法伪代码

算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）

输入：初始状态，目标状态

输出：从初始状态到目标状态的一系列过程

算法描述：

Begin：

读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； If(问题可解) 把初始状态假如open表中； While（未找到解&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点；

②判断当前结点状态和目标状态是否一致，若一致，跳出循环；

否则跳转到③；

③对当前结点，分别按照上、下、左、右方向移动空格位置来扩

展新的状态结点，并计算新扩展结点的评价值f并记录其父节

点；

④对于新扩展的状态结点，判断其是否重复，若不重复，把其加

入到open表中；

⑤把当前结点从open表中移除；

End while

End if

输出结果；

End

算法流程如下：

三、 算法实现

3.1 实验环境与问题规模

实验环境：硬件环境：PC机。

软件环境：Windows XP ;VC++ 6.0。

问题规模：对于任一给定可解初始状态，状态空间有9!/2=181440个状态；当采用不在位棋子数作为启发函数时，深度超过20时，算法求解速度缓慢；

3.2 数据结构

static int target[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态 class eight_num

{

private:

int num[9]; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数 int deapth; 定义了搜索的深度 int eva_function; 评价函数的值，每次选取最小的进行扩展

public:

eight_num* parent; 指向节点的父节点 eight_num* leaf_next; 指向open表的下一个节点 eight_num* leaf_pre; 指向open 表的前一个节点

初始状态的构造函数

eight_num(int init_num[9]);

eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){}

eight_num(void){ }

计算启发函数g(n)的值

void eight_num::cul_para(void){}

显示当前节点的状态

void eight_num::show(){}

复制当前节点状态到一个另数组中

void eight_num::get_numbers_to(int other_num[9]){}

设置当前节点状态(欲设置的状态记录的other数组中)

void eight_num::set_num(int other_num[9]){}

eight_num& eight_num::operator=(eight_num& another_8num){} eight_num& eight_num::operator=(int other_num[9]){} int eight_num::operator==(eight_num& another_8num){} int eight_num::operator==(int other_num[9]){}

空格向上移

int move_up(int num[9]){}

空格向下移

int move_down(int num[9]){}

空格向左移

int move_left(int num[9]){}

空格向右移

int move_right(int num[9]){}

判断可否解出

int icansolve(int num[9],int target[9]){}

判断有无重复

int existed(int num[9],eight_num *where){}

寻找估价函数最小的叶子节点

eight_num* find_OK_leaf(eight_num* start){}

}

3.3 实验结果

h: 启发函数（不在位将牌数）

3.4 系统中间及最终输出结果（要求有屏幕显示）

目标状态默认为1 2 3 8 0 4 7 6 5 .

a) 初始状态是3 2 1 8 0 4 7 6 5，用h作为启发函数结果都如下：

b)初始状态是1 04 2 7 3 8 5 6，用h作为启发函数结果都如下：

中间略

b)初始状态是1 0 3 8 2 4 7 6 5，用h作为启发函数结果都如下：

四、参考文献

[1] Artificial Intelligence——A Modern Approach. Stuart Russell, Peter Norvig. 人民邮电出版社,2004

[2] Artificial Intelligence, Rob Callan. 电子工业出版社,2004

附录—源代码及其注释

#include "stdafx.h"

#include "iostream.h"

#include <time.h>

#include <stdio.h>

#include <dos.h>

#include <conio.h>

static int target[9]={1,2,3,8,0,4,7,6,5};

//class definition

class eight_num

{

private:

int num[9]; int not_in_position_num; int deapth; int eva_function;

public:

eight_num* parent; eight_num* leaf_next; eight_num* leaf_pre;

eight_num(int init_num[9]);

eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)

{ } num[0]=num1; num[1]=num2; num[2]=num3; num[3]=num4; num[4]=num5; num[5]=num6; num[6]=num7; num[7]=num8; num[8]=num9;

eight_num(void) { } for (int i=0;i<9;i++) num[i]=i;

void cul_para(void);

void get_numbers_to(int other_num[9]);

int get_nipn(void) {return not_in_position_num;} int get_deapth(void) {return deapth;} int get_evafun(void) {return eva_function;} void set_num(int other_num[9]); void show(void);

};

//计算启发函数g(n)的值

void eight_num::cul_para(void)

{

eight_num& operator=(eight_num&); eight_num& operator=(int other_num[9]); int operator==(eight_num&); int operator==(int other_num[9]); int i; int temp_nipn=0; for (i=0;i<9;i++) if (num[i]!=target[i]) temp_nipn++; not_in_position_num=temp_nipn; if (this->parent==NULL)

} deapth=0; else deapth=this->parent->deapth+1; eva_function=not_in_position_num+deapth;

//构造函数1

eight_num::eight_num(int init_num[9]) {

}

//显示当前节点的状态

void eight_num::show()

{

for (int i=0;i<9;i++) num[i]=init_num[i]; cout<<num[0]; cout<<" "; cout<<num[1]; cout<<" "; cout<<num[2]; cout<<"\n"; cout<<num[3]; cout<<" "; cout<<num[4]; cout<<" "; cout<<num[5]; cout<<"\n"; cout<<num[6]; cout<<" "; cout<<num[7];

} cout<<" "; cout<<num[8]; cout<<"\n";

//复制当前节点状态到一个另数组中

void eight_num::get_numbers_to(int other_num[9])

{

}

//设置当前节点状态(欲设置的状态记录的other数组中) void eight_num::set_num(int other_num[9])

{

}

eight_num& eight_num::operator=(eight_num& another_8num) {

}

eight_num& eight_num::operator=(int other_num[9])

{

for (int i=0;i<9;i++) other_num[i]=num[i]; for (int i=0;i<9;i++) num[i]=other_num[i]; for (int i=0;i<9;i++) num[i]=another_8num.num[i]; not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1; eva_function=not_in_position_num+deapth; return *this; for (int i=0;i<9;i++) num[i]=other_num[i];

} return *this;

int eight_num::operator==(eight_num& another_8num) {

}

int eight_num::operator==(int other_num[9])

{

}

int match=1; for (int i=0;i<9;i++) if(num[i]!=another_8num.num[i]) { } match=0; break; if (match==0) return 0; else return 1; int match=1; for (int i=0;i<9;i++) if(num[i]!=other_num[i]) { } match=0; break; if (match==0) return 0; else return 1;

//class definition over //空格向上移

int move_up(int num[9]) {

}

//空格向下移

int move_down(int num[9]) {

for (int i=0;i<9;i++) if (num[i]==0) break; if (i<3) return 0; else { } num[i]=num[i-3]; num[i-3]=0; return 1; for (int i=0;i<9;i++) if (num[i]==0) break; if (i>5) return 0; else { } num[i]=num[i+3]; num[i+3]=0; return 1;

}

//空格向左移

int move_left(int num[9]) {

}

//空格向右移

int move_right(int num[9]) {

for (int i=0;i<9;i++) if (num[i]==0) break; if (i==0||i==3||i==6) return 0; else { } num[i]=num[i-1]; num[i-1]=0; return 1; for (int i=0;i<9;i++) if (num[i]==0) break; if (i==2||i==5||i==8) return 0; else { } num[i]=num[i+1]; num[i+1]=0; return 1;

}

//判断可否解出

int icansolve(int num[9],int target[9]) {

}

//判断有无重复

int existed(int num[9],eight_num *where) {

}

//寻找估价函数最小的叶子节点

eight_num* find_OK_leaf(eight_num* start) int i,j; int count_num,count_target; for (i=0;i<9;i++) for (j=0;j<i;j++) { } if(num[j]<num[i]&&num[j]!=0) count_num++; if(target[j]<target[i]&&target[j]!=0) count_target++; if((count_num+count_target)%2 == 0) return 1; else return 0; eight_num *p; for(p=where;p!=NULL;p=p->parent) if(*p==num) return 1; return 0;

{

}

//主函数开始 int main(void) {

eight_num *p,*OK; p=OK=start; int min=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next) if(min>p->get_evafun()) { } OK=p; min=p->get_evafun(); return OK; double time; clock_t Start,Finish; int memery_used=0,step=0; int num[9]; int flag=0;//是否输入错误标志，1表示输入错误 int bingo=0;//是否查找成功标志，1表示成功 int i,j; cout<<"Please input the number(0 for the blank):\n"; for (i=0;i<9;i++) { flag=0; cin>>num[i]; for(j=0;j<i;j++) if(num[i]==num[j]) flag=1;

} if (num[i]<0||num[i]>8||flag==1) { } i--; cout<<"Illegle number!\tReinput!\n"; eight_num S(num),Target(target); S.parent=S.leaf_next=S.leaf_pre=NULL; S.cul_para(); memery_used++; cout<<"Now the initial numbers are:\n"; S.show(); cout<<"And the Target is:\n"; Target.show(); if(!icansolve(num,target)) { } Start=clock( ); eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1) { OK_leaf=find_OK_leaf(leaf_start); if(*OK_leaf==Target) { } bingo=1; break; cout<<"No one can solve it!\n"; cin>>i; return 1;

p=OK_leaf->leaf_pre; OK_leaf->get_numbers_to(num); if(move_up(num)&&!existed(num,OK_leaf)) { } OK_leaf->get_numbers_to(num); if(move_down(num)&&!existed(num,OK_leaf)) { new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; else p->leaf_next=new_8num; p=new_8num; memery_used++;

} OK_leaf->get_numbers_to(num); if(move_left(num)&&!existed(num,OK_leaf)) { } OK_leaf->get_numbers_to(num); if(move_right(num)&&!existed(num,OK_leaf)) {

new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; new_8num=new eight_num;

new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++;

} } p->leaf_next=OK_leaf->leaf_next; if(OK_leaf->leaf_next!=NULL) OK_leaf->leaf_next->leaf_pre=p; OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;

Finish=clock( );

}

if(bingo==1) { } else cout<<"Fail to find!"; time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC; eight_num *p; for (p=OK_leaf->parent;p!=NULL;p=p->parent) { } cout<<" ^\n"; p->show(); step++; cout<<"Time cost:"; cout<<time; cout<<"ms\n"; cout<<"Totaly covered steps:"; cout<<step; cout<<"\n"; return 0;