编号
南京航空航天大学毕业论文
题目启发式搜索算法在N数码问
题中的应用
学生姓名
学号
学院
专业
班级
指导教师
二〇一三年六月
南京航空航天大学
本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。
作者签名：年月日
（学号）：
启发式搜索算法在N数码问题中的应用
摘要
N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。
本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。
关键词：启发式搜索，数码问题，A*算法，遗传算法
The Application of Heuristic Search Algorithm
on N-Puzzle Problem
Abstract
N-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 https://www.doczj.com/doc/0c17959241.html,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 模拟退火算法简介
模拟退火算法来自于冶金学中的专有名词退火。退火是指将材料加热足够高的温度后按照特定的速率冷却，其作用是使其晶粒最终变得有序，使得内能变小，从而减小材料缺陷。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。
模拟退火便是根据金属退火理论加以延伸得到的：我们将上述材料学的原理和统计学相结合，将搜索空间内的每一个状态看作是材料中的晶粒；而搜索空间内的每一个状态的适合度看作是，晶粒“能量”（内能）。算法先以搜索空间内一个任意状态作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
可以证明，模拟退火算法所得解依概率收敛到全局最优解。
模拟退火算法的基本步骤如下所示：
1 随机生成一个初始解best＝x0，并计算目标函数值E(x0);
2 设置初始温度T(0)=T0，迭代次数i = 1;
3 while T(i) > T min do
4 for j = 1 to k do
5 根据当前最优解best生成一个新杰new
6ΔE = E(new) - E(best)
6 if ΔE ＜0 then best = new；
7 if ΔE ＞0 then p = exp(- ΔE /T(i));
8 if c = random[0,1] < p then best = new
else best = best ;
10 i = 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=a l a 2n 3…
a 15a 16。其中a i (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行时，我们可以使用上移操作，即当且仅当1≤i ≤N ×(N ?1)时，我们才可以使用上移操作。
同理，N 数码的下移、左移、右移规则分别为N+1≤i ≤N ×N 、i mod N ≠ 0、
i mod N ≠ 1。
综上可构造出，N数码问题的移动规则，以及对应移动操作的程序表述：上移操作：if 1≤i≤ N×(N-1) then swap(S[i],S[i+n]);
下移操作：if n+1≤i≤ (N×N) then swap(S[i],S[i-n]);
左移操作：if i mod ≠0，then swap(S[i],S[i+1])；
右移操作：if i mod n≠1，then swap(S[i],S[i-1]);
（其中swap函数表示交换两个数的操作）
2.2UI设计
UI（User Interface用户界面）设计的几个基本原则是：简易性，一致性，清楚等。本篇文章中所需要的系统UI应能够选择N数码的规模，即N的大小，并根据输入的N的大小规定所能输入数码的个数。本文将提出A*算法的两种启发函数，一种遗传算法，我们的UI需要能够选择测试的算法，并且能够提供算法间的比较。UI的输出相对比较简单，只需输出对应算法的搜索步数以及所搜得的结果。于是我们设计出了以下界面如图2.1所示。
图2.1 N数码问题UI
2.3 算法设计
N数码问题是一种很常见的搜索问题，可以使用很多成熟的算法来解决，例如宽搜、深搜等，当然也可以使用人工智能中的启发式算法来进行求解，例如A*算法、模拟退火算法、遗传算法等，在这一节中我们将着重对启发式算法进行讨论。
2.3.1 普通搜索算法
对于所有的搜索算法我们都可以使用树形结构来描述其搜索过程，如图3所示，从初始状态经过一步合法移动所能得到的所有状态形成了树的第二层，经过两步合法移动所得到的状态形成了树的第三层（图2.2中第三层并不完整），图三只是初始状态搜索出来的一种情况，不是所有的搜索方式都会产生这样的一棵搜索树。
图2,2 8数码问题搜索树
普通搜索算法主要可以分为宽度优先搜索（Breadth First Search）和深度优先搜索（Depth First Search）两种，深搜在搜索树上表现为先往层数深的地
方搜索，而宽搜是一层层的搜索下去，由于搜索过程中会记录已到达过的状态，防止重复搜索，所以深搜和宽搜所得到的搜索树会有所不同。
2.3.2 A*算法
对于15数码和8数码问题而言，A*算法可以有效地解决问题。
8数码问题规模相对较小，用任意的搜索算法都能很快的得出结果，当然如果要得到最优解，最方便的就是使用宽度优先搜索（Breadth First Search简称为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.3 d(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{f
1, f
2
, f
3
,…, f
m
}（m为染色体长度），
其中f
i
可以描述为经过染色体上钱i次移动后，所形成的状态中已经在正确位置上的数码（含空格）个数。
下面我们介绍适用于N数码问题的几种遗传操作：
杂交算子：采用传统的一点交叉算子。例如：
个体A=RUDRLDLURDLRLDUL，个体B=LDDRLULRLDLLDRUD
随机取一位如第二位为交叉点，杂交后所得的个体A’为RUDRLDLRLDLLDRUD，个体B’为LDDRLULURDLRLDUL。
变异算子：随机选取染色体中的某些位，进行随机产生{U,D,L,R}去替换这些
位。
在遗传算法中我们首先要设定一些初始参数，在本文中我们涉及到的参数有种群规模K，染色体长度len，继续保留最优个体的进化代数gen，其具体数值如表1所示：
表1 遗传算法参数表
K gen len
8数码101050
15数码3010100
24数码5010500
第三章系统实现
在这一章中我们将描述整个系统的实现方式，着重介绍了A*算法和启发式算法的实现。
3.1 数据结构实现
3.1.1 状态存储结构
本文的系统中，对于状态我们单独的将其分装成为一个独立的Node类，其拥有的属性和方法如图3.1所示。
属性介绍：
father属性存放搜索过程中当前节点的父亲节点；level属性记录当前节点所在搜索树的层数；mode属性记录当前的操作；N属性记录数码问题规模；score 属性记录当前状态的估价值；S属性记录当前状态。
方法介绍：
getScore方法用于计算当前状态的估价值；getZero方法用于得到空格的位置；getHashCode和compareTo两个方法则是作为下面讲述的优先级队列和哈希表的辅助函数。
图3.1 Node类图
3.1.2 优先级队列的实现
本文中的系统是现实时将优先级队列封装为PriorityQueue类，其有三个主要方法，分别为GetFirst、Dequeue和Add。GetFirst方法表示取出队列中的第一个值（即最优值），但这个值仍保留在队列中；Dequeue方法表示取出队列中的第一个值（即最优值）并将其从队列中移除；Add方法表示向队列中加入一个值，加入后保证优先级队列依然正确。
PriorityQueue类内部使用小根堆维护优先级队列，具体实现在此不加赘述假设当前队列长度为n，则其空间复杂度为O(n)；GetFirst操作的时间复杂度为O(1)；Dequeue操作的时间复杂度为O(n Log2n)；Add操作的时间复杂度为O(n Log2n)。
3.2 算法实现
3.2.1 A*算法
A*算法是一种具有普遍适用性的算法，其基本搜索步骤如下所示：
1）输入初始节状态点n
0，若其有解则把n
存放入优先级队列OPEN（按照估
价值的优先队列），否则输出无解
2）构造一个Hash表CLOSED，它的初始值为空，存放所有已经被搜索过的节点。
3）如果OPEN表为空，则失败退出。
4）选择OPEN上的第一个节点（估价最小的一个节点），把它从OPEN中移入CLPSED，记为节点n。
5）如果n是目标节点，表示已经找到合法的移动序列，则从n到n
的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立），否则
6）扩展节点n，生成其后继结点集L（按照移动规则移动，最多有4个元素）
7）对于每一个在L中元素m，若m已存在于CLOSED或OPEN中则忽略，否则记
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。
实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解8数码问题 （1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n） 其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。 （2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。 实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路 八数码问题的求解算法 （1）盲目搜索 宽度优先搜索算法、深度优先搜索算法 （2）启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)
实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰
一、实验内容： 使用启发式搜索算法求解8数码问题。 1、编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个
1、程序源代码 #include
编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月
南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）：
启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法
The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-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 https://www.doczj.com/doc/0c17959241.html,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
启发式搜索——初识A*算法
A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
启发式图搜索算法 摘要：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。进行搜索技术一般需要某些有关具体问题领域的特性的信息。 关键词：启发式搜索；估价函数；有序搜索；A*算法； 正文： 启发式图搜索的意义因为无信息图搜索算法的效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。所以引入了启发式图搜索算法。 启发式图搜索算法就是进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。关于图搜索的启发式搜索算法就叫做启发式图搜索算法。 启发式图搜索策略：假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。 启发信息按其用途可分为下列3种： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。 (3) 用于决定某些应该从搜索树中抛弃或修剪的节点。 启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。所谓的估价函数就是为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 有序搜索应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索 (best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 有序状态空间搜索算法 (1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。
启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，
以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型
人工智能基础实验报告 实验名称：八数码问题 姓名：张俊 学号：2220092333 指导老师：邓安生
启发式搜索算法 1. 实验内容： 使用启发式搜索算法求解8数码问题。 ⑴ 编制程序实现求解8数码问题A *算法，采用估价函数 ()()()() w n f n d n p n ??=+???， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 ⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 2. 实验目的 熟练掌握启发式搜索A *算法及其可采纳性。 3. 实验原理 八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。 4.源代码 #include
实验二：A*算法 一、实验目的 了解启发式搜索算法的基本思想，掌握A*算法的基本原理和步骤。学会对于算法的正确应用，解决实际生活中的问题。学会区分与盲目搜索算法的不同之处。 二、实验环境 PC机一台，VC++6.0 三、实验原理 A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC （Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS 一样，进行启发式的搜索。 A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 A*算法的公式为：f(n)=g(n)+h(n)，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。 对于函数h(n)，估算距离常用的方法有： 曼哈顿距离：定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|。
人工智能技术报告 启发式搜索 产生背景： 何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 定义： 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径， 可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)
是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了。 算法举例 启发算法有：蚁群算法，遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。 分析：蚁群算法 蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，指的是一种源于自然现象的算法，也是一种meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。 蚂蚁觅食原理： 自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后， 它们仍然能很快重新找到新的最佳路线。
启发式搜索A和A*搜索算法 首先什么是启发式搜索？启发式搜索就是利用当前问题有关的信息作为启发式信息，这些信息是能够提升查找效率、减少搜索时间和减少查询次数的。为了利用这些信息，我们定义了一个估价函数h(x)，h(x)是对当前状态x的一个估计，它表示x状态到目标点的距离。那么由它表示的意义我们可以知道，当h(x)等于0时，说明到达了目标点。 一、A和A*搜搜算法介绍 A搜索算法就是使用了估价函数的搜索算法，估价函数的一般形式是f(x)=g(x)+h(x)。其任务就是估计待搜索有希望程度，赢一次给它们排定次序。其中g(x)代表从初始结点到x结点的实际代价，h(x)是从当前结点到目标结点的代价，这个代价是估计出来的。 A*搜索算法是估价函数满足一定条件的算法，其限制条件是f(x)=g(x)+h(x)，代价函数g(x)大于0，h(x)的值不大于x到目标结点的实际代价h*(x)。 二、A和A*搜索算法运用 搜索算法如下： ①将初始节点S0放入Open表中。 ②如Open表为空，则搜索失败，退出。 ③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n。 ④如果节点n是目标节点，则搜索成功，求得一个解，退出。 ⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出相应的估价函数值。 ⑥把节点n的子节点放到Open表中。 ⑦对Open表中的各节点按估价函数值从小到大排列；。 ⑧转到②。 启发式通常用于资讯充份的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定
Heuristic Search 启发式搜索 译 by 陈雪(QQ:53352894) 必要条件 ?递归算法 主要概念 启发式搜索的主要目标是使用一个估价函数去判断所有状态的“好坏”，以提高搜索找到解的效率。 通常，估价函数表示成一个函数或是一个状态，这个函数叫做“估价函数”例如：?迷宫寻找出路的时候，到出口的欧几里德距离 D=[(xI-xj)^2+(yI-yj)^2]1/2。式中，D是点i和点j之间的距离； xI xj 是第i个点的坐标；yI yj是第j个点的坐标。（译者注） ?当尝试在一场跳棋比赛中获胜时，能吃掉对手的最多棋子子 设计估价函数 直观地看，估价函数越优秀，搜索就更好（快）。问题是：怎么评价估价函数的好坏呢？ 估价函数的好坏，取决于它评估一个状态好坏的能力。例如，迷宫的例子，怎么计算到出口的距离？欧几里德距离也许非常的坏，甚至是非常小的迷宫，它也可能绕很多的路： 一般来说，估价函数越好，搜索就越快。一般来说，搜索时间和估价函数的准确性如下图： 注意！一个似乎很“傻”的估价函数可以大大地提高程序的效率！（如果它非常完美地被使用）
另一个重要概念是“可接受”，一个可接受的估价函数表示对于每个点都不存在“低估”的情况。例如，迷宫的欧几里德距离启发函数是“低估”的，刚才的图例很清楚地说明了这一点。 方法1：启发式剪枝 最简单也是最常用的启发式搜索是利用估价函数来剪枝。假设我们的问题是要求找最小总花费。对于一个可接受的估价函数，当前花费是A，启发函数返回了B，当前子问的最优解是A+B。如果找到的一个解一个花费是C，C 随机启发式搜索算法的性能分析 随机启发式搜索算法如演化算法、蚁群算法及人工免疫算法等是通过模拟大自然现象、过程及一些生物特性等提出的一类通用算法。实践证明,这类随机启发式搜索算法在科学研究及工程实际问题中获得了极大的成功,尤其是针对一些结构不清晰的复杂优化问题,以及在计算资源有限的情况下表现出了卓越的性能。 为了更好的理解随机启发式搜索算法的工作机制,进一步指导算法设计及应用,研究人员迫切希望为这类算法建立严密的理论基础。然而,由于随机启发式搜索算法的随机性、群体性等特点,使得算法在运行过程中表现出非常复杂的动态随机行为,增加了理论研究的难度。 当前,理论研究成果相对偏少。本文从随机启发式搜索算法的理论研究角度出发,关注随机启发式搜索算法求解优化问题的时间复杂性,以及在NP-完全(难)优化问题上的近似性能;研究问题类型与算法特征之间的关系;进一步探索随机 启发式搜索算法求解典型优化问题的有效性,以期完善和增强随机启发式搜索算法的理论基础。 本文的主要工作如下:(1)研究了演化算法求解最多叶子生成树问题(MLST) 的性能。最多叶子生成树问题是NP完全理论中一个经典的组合优化问题,在网络设计及电路布局等实际问题上有较强的应用背景。 该问题是在一个无向连通图中找出一棵生成树,使得生成树中所含叶子节点最多。许多启发式算法如演化算法用于求解该问题。 然而,对于演化算法在NP难问题的求解性能方面我们仍知之甚少。本文从理论上研究了演化算法求解MLST问题的近似性能。 指出对于MLST问题,算法(1+1)EA能够分别在期望多项式时间2O(nm)和 4O(nm)内获得5近似比和3近似比,其中n为无向连通图中的节点数,m为边数。同时,我们研究了(1+1)EA算法在两个MLST问题实例上的性能,并且指出局部搜索算法在该实例上容易陷入局部最优,而(1+1)EA算法能够逃脱局部最优并最终获得最优解。 (2)研究了蚁群算法在二次指派问题(QAP)上的性能。二次指派问题是最具挑战性的组合优化问题之一。 该问题在物流运输和选址等许多实际问题中有着广泛的应用。理论上研究了ACO算法在极其难的QAP问题上的性能。 给出了一个简单的(1+1)MMAA算法在QAP问题上的最坏情况界。并指出对于QAP问题,(1+1)MMAA算法能够获得一定的近似保证。 最后,通过构建一个QAP实例,表明蚁群优化算法在该实例上要优于 2-exchange局部搜索算法,进一步证实了蚁群算法的有效性。(3)分析比较了基于免疫的超变异算子与标准位变异算子在优化问题上的性能。 人工免疫系统在许多复杂的真实优化问题中获得了广泛的应用并取得了极大成功。然而,人工免疫算法的理论研究远远滞后于其在许多领域的应用研究。 对于人工免疫算法的运行机制以及其有效性研究还处于探索的初级阶段,当前也迫切需要为这类算法建立坚实的理论基础。本文从理论上分析了一种被用于免疫算法中的连续高频变异算子在优化问题上的性能,并在两个拟布尔函数及两个真实组合优化问题的实例上分析比较了连续高频变异算子与标准位变异算子、局部变异算子的性能,证明了连续高频变异算子在这些实例上要优于标准位变异算子及局部变异算子。 也进一步揭示了问题类型与算法特征之间的关系,从理论上证实了连续高频 人工智能导论 启发式图搜索 院系名称：地球物理与信息工程学院 专业名称：计算机科学与技术 学号： 姓名： 完成日期2015年 6月 16 日 一、过程A描述： ①OPEN := (s), f(s) := g(s) + h(s); ②LOOP : IF OPEN=() THEN EXIT(FAIL); ③n := FIRST(OPEN); ④IF GOAL(n) THEN EXIT(SUCCESS); ⑤REMOVE(n, OPEN) , ADD(n, CLOSED); ⑥EXPAND(n) {} , 计算f(n,) = g(n, ) + h(); g(n, )是从s通过n到的耗散值，f(n,)是从s通过n、到目标节点耗散值的估计； ·ADD( , OPEN), 标记到n的指针。 ·IF f(n,) 第23卷 第3期华侨大学学报(自然科学版)Vo l.23 N o.3 2002年7月Journal of Huaqiao U niver sity(N atural Science)Jul.2002 文章编号 1000-5013(2002)03-0313-04 启发搜索算法在运筹学中的应用 汤永清 张银明 (华侨大学信息科学与工程学院,泉州362011) 摘要 运筹学中的运输、指派问题具有广泛的应用性.启发式的搜索算法的核心问题是构造启发 函数,用启发函数的思想去解决传统的运筹学问题,可以提高求解的效率.文中从启发式的搜索 算法角度出发,介绍了如何构造启发函数,并用其解决运筹学中的运输与指派问题. 关键词 人工智能,启发函数,运筹学 中图分类号 T P18∶O22文献标识码 A 运筹学是一门系统科学.运筹学是运用科学方法,尤其是用数学方法去研究各种系统,优化途径及方案,为决策者提供科学决策的依据.运筹学中有一类问题具有特殊性,如运输问题、调运问题,且有很多解决的方法.其本质,就是通过多次迭代获得一个最优分配解.如对于运输问题,解决方法较多地使用表上作业法的最小元素法.分配问题多采用整数规划的匈牙利法.分配问题可以认为是供需为1的运输问题的特例来处理. 1 启发式搜索算法 启发式的搜索算法广泛应用于人工智能,是用来寻找最优解的一种方法.它的本质是部分的放弃了算法“一般化、通用化”的概念,把所要解的问题的具体领域内的知识加入到算法中去,以提高算法的效率.其基本原理是在搜索的过程中对遇到的新状态,先利用估值函数得到1个估计值.然后,根据估计值的大小来,确定下一步的状态将从哪一步开始继续前进,以此来实行最佳优先搜索.每一步的搜索都是根据估计值来判断下一步的搜索方向,因此如何设计估值函数就成为问题求解的核心.用数学公式描述,f(x)=(1- (x))g(x)+ (x)h(x).其中f(x)代表估值函数,g(x)为从初始结点到n个结点的最小代价, (x)为权函数(可以是一个动态值,也可以为常数,一般情况下可以取值为1或0),h(x)表示从n结点到目标结点的最小代价,也称之为启发函数. 目前比较流行的有两种方法.(1)令h(x)≡0,即仅以已经花费的代价g(x)来进行估计,这有点接近于广度优先法.它虽说能找到完备解,但花费的工作量不一定是最小的.这是因为它不利用任何启发式信息.(2)与上一种完全相反,不是舍弃h(x)而是舍弃g(x),即令f(x) =h(x).这种方法的实质,在于把解的最优性置于次要地位,首先考虑的是如何尽快地求得一 收稿日期 2001-12-09 作者简介 汤永清(1974-),男,助教 1、程序源代码 #include <> #include<> struct node{ i nt a[3][3];//用二维数组存放8数码 int hx;//函数h（x）的值，表示与目标状态的差距 s truct node *parent;//指向父结点的指针 s truct node *next;//指向链表中下一个结点的指针 }; //------------------hx函数-------------------// int hx(int s[3][3]) {//函数说明：计算s与目标状态的差距值 i nt i,j; i nt hx=0; i nt sg[3][3]={1,2,3,8,0,4,7,6,5}; f or(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++; return hx; } //-------------hx函数end----------------------// //-------------extend扩展函数----------------// struct node *extend(node *ex) { //函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值 i nt i,j,m,n; //循环变量 i nt t; //临时替换变量 i nt flag=0; i nt x[3][3];//临时存放二维数组 s truct node *p,*q,*head; head=(node *)malloc(sizeof(node));//head p=head; q=head; h ead->next=NULL;//初始化 f or(i=0;i<3;i++)//找到二维数组中0的位置 { for(j=0;j<3;j++)随机启发式搜索算法的性能分析
人工智能导论 启发式图搜索
人工智能中的启发搜索算法在运筹学中的应用
启发式搜索算法解决八数码问题(C语言)
相关主题
文本预览