人工智能实验算法分析文档

人工智能各算法实验分析

及指导

撰写时间：2012年6月15日

实验一 A*算法实验

一、实验目的：

熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。 二、实验原理：

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。 三、实验环境：

Windows 操作系统，C语言 或 Prolog语言。

四、实验内容：

1． 分别以8数码和15数码为例实际求解A*算法。 2． 画出A*算法求解框图。

3． 分析估价函数对搜索算法的影响。 4．分析A*算法的特点。

六、实验报告要求：

1 A*算法流程图和算法框图。

2 试分析估价函数的值对搜索算法速度的影响。 3

根据A*算法分析启发式搜索的特点。

提交程序清单。

1 知识点归纳

搜索策略的知识点主要可以分为六块内容来进行讲解： ? 搜索的基本概念

? 状态空间的盲目搜索 ? 状态空间的启发式搜索 ? 与/或树的盲目搜索 ? 与/或树的启发式搜索 ? 博弈树的启发式搜索 ? α-β剪枝技术

很多问题都可以用到人工智能中的搜索策略来进行问题求解，比如迷宫问题、博弈问题、8皇后问题、旅行商问题、排课问题、背包问题等等。

对于本实验所要求解的8数码问题，需要掌握的知识点主要有几下这些： ? 一般图搜索算法流程

? 广度优先和深度优先搜索 ? 代价树搜索

? 启发信息和评估函数 ? A算法 ? A*算法

2 算法流程

1) 2) 3) 4) 5) 6) 7) 8)

初始化Open表和Closed表。

把图搜索初始化节点放入Open表中。 Open若非空，取出表头的节点x。 若x就是目标节点，返回搜索成功。

将该节点x从Open表中删除并放入Closed表中。 根据图信息产生x的孩子节点y1、y2、??yn。 标记x为yi的父节点。

若yi从未在Open表和Closed表中出现过，根据评估函数计算yi的评估值并放入Open表中。

9) 若yi在Open表中出现过且当前yi的评估值较小，更新Open表中该节点的

评估值并重置该节点的父节点为x。

10) 若yi在Closed表中出现过且当前yi的评估值较小，更新Closed表中该节点

的评估值并重置该节点的父节点未x，同时将其从Closed表中删除并重新移入Open表。

11) 若x还有子节点yi+1，重复循环8、9、10三个步骤。 12) 若x没有子节点了，将Open表中已有的节点根据相应的搜索策略进行排序，

然后回到步骤3。

13) 若Open表已空，也没有搜索成功，则返回搜索失败，不存在该路径。

3 算法伪代码

A*算法搜索过程中设置两个表：Open和Closed。Open表保存了所有已生成而未考察的节点，Closed表中记录已访问过的节点。算法中有一步是根据估价函数重排Open表。这样循环中的每一步只考虑Open表中状态最好的节点。

4 算法分析

1) 对于步骤1，Open表和Closed表只是数据结构上的一种形式，至于在写代

码时到底是使用栈式存储结构还是队列式存储结构没有严格要求，需要根据具体问题具体分析用哪一种数据结构，最好是能够选择算法效率更高的。

2) 对于步骤2，一般而言，这里的初始节点代表的是一个状态，也就是说，需

要根据实际问题来设计一种能表示任何一种确定状态的类，而该节点显然就是该类的一个实例或对象，将该节点放入Open表中，需要Open表能够设计的足够空间用来存放许许多多这样的实例，因为在状态空间搜索的过程中，状态经常是以几何数量级增长的。

3) 对于步骤3，在写代码的过程中，取出表头的节点x可以有很多种方式实现，

未必一定要从该数据结构的头部进行取节点的操作，因为如何从Open表中取节点是关系到算法搜索效率的关键，显然，我们都希望从Open表中众多的节点中选取到最有希望通向目标节点的过渡节点来，当然直接选出目标节点是最好的（虽然几乎是做不到的）。

4) 对选出的状态节点进行是否是目标节点的判断，显然需要一个高效的判断方

式，针对不同问题状态空间中的每一状态，也许会有截然不同的状态比较方式，对于8数码问题，可以通过逐个比较每一位置的数码来进行是否是目标状态的判断，但效率显然不高，后面会介绍一种更加高效的方式，它是设计一种哈希函数，使得根据这种函数能计算出一个哈希码来唯一确定整个状态空间中任何一个状态，这样就能做到比较一个问题状态空间中任何两种状态只需判断这两个哈希数码是否相等即可。

5) 这步的意义在于，凡是Open表中的节点都是未被扩展过的节点（也就是没

生过孩子的节点），而Closed表中的节点都是以被扩展过的节点（同时当然肯定不是目标节点）。

6) 这步要根据具体问题来确定，比如8数码问题中，如果当前状态x的空位出

现在四个角落，显然它只有两个孩子节点，而且其中一个一定是它的父亲节点，而如果x的空位出现在8数码棋盘的中心，它的孩子节点就有4个，同理其中有一个一定是它的孩子，所以在生成孩子节点的时候一定得标注它们的父亲节点，这样可以避免重复计算回路而对算法造成不必要的时间浪费。

7) 任何一个新生成的节点一定要标注其父亲节点是谁,以减少在对它进行扩展

的时候对父亲进行重复计算的算法复杂度，因为父亲节点一定也会被当做它的孩子节点再被扩展一次，除非它本身就是初始节点。

8) 这步的意义在于该新生成的节点第一次被发现，理所当然要将其放入Open

表中以待被判断是否是目标节点或被扩展。

9) 这步的意义在于该节点曾被发现过并被放入过Open表中，但还从未被从

Open表中取出进行扩展的时候，图搜索状态空间中的其它节点又一次发现了该节点，如果发现存在这样的节点，即能证明该搜索空间图存在“环路”，搜索能通过两种截然不同的路径发现同一个状态节点，并且本次发现该节点时发现了一条从初始节点通往该节点的更短的路径，从而必须更新Open表中该节点的评估值并重置其父节点。

10) 这步的意义不仅说明该搜索空间图存在“环路”，而且发现之前的搜索已经

走了一些冤枉路，本次新生成的节点在之前不仅已被发现过，还被扩展过，如果本次生成的评估值更小，说明之前从该节点之后所有被扩展的节点的评估值都有问题，全部都需要重新评估和计算，因此不仅需要将该节点的评估值更新、重置父亲节点的标示，还要将其从Closed表中重新移回Open表中待再次被扩展。

11) 重复以上3个步骤直到x的孩子节点评估值已被全部计算并做了相应处理。

12) 在8数码问题算法中，这步是根据Open表中各节点的评估值大小来进行排

序的，评估值小的说明通过它前往目标节点的可能路径是最短的，因此排在前面，下次优先被选择出进行扩展。

13) 若Open表已空，但没有发现目标节点，只能说明该图中的所有连通节点都

已被处理，不存在该目标节点。

5 关键代码

6 实验分析

6.1 数据结构准备

为了表示n数码问题中的任何一个状态，需要设计一个状态类stateNode：

该状态类具有以下方法：

其中，它们的作用如下： 1) stateNode：构造函数

2) isTarget：用于将该状态和目标状态进行比较，如果相同则返回true,不相

同则返回false

3) isSame：用于将该状态和另一状态进行比较，如果相同返回true,不相同返

回false

4) getChild：用于生成该状态的孩子节点，根据index来决定，是生成上、下、

左还是右的移动方式

5) dealUp-dealRight：被getChild方法所调用，用于具体细节处理，如计算

新孩子节点评估值以及标记父节点等操作

6) hashValue：用于计算该状态自身的哈希码，用于唯一标示自身状态 7) printState：用于在Console中打印出自身状态各数码

同时为了使得算法能够有更高的效率，特别设计了链表类，也就是Open表和Closed表的模板，用于存放大量状态节点：

6.2 算法指导

在完成实验的过程中，首先要思考的就是如何设计界面，界面往往能直观得反应出实验作品的好坏，界面的设计也非常重要。

界面主要控件代码（包括文本框、按钮、复选框、图片面板、菜单及下拉框等）：

界面主要布局代码（包括各控件之间的对齐方式、排版等）：

界面逻辑代码（主要是各控件的点击事件）：

事件响应监听器的制作：

主算法代码：

这段代码是前面伪代码的实例化版，其中调用了很多方法，这些方法都是之前在stateNode类以及stateNodeList类里定义的，这样的一个好处就是，从这个角度浏览整个调用过程，依然显得算法很简介、优美。

实验二 BP网络识别0-9

1 实验描述

将已处理好的理想状态下（白底黑字）的图片上的文本信息提取出来。先将图片分割成小块每块具体显示一个字符，将每个小块的内容按照点矩阵的算法将其转换成二进制。将该二进制值与以知的字符（0—9、a—z、A—Z）做匹配，最后将相应的字符信息转换成字符窜拼合输出。

2 功能实现说明

特征提取算法识别：

（1）颜色直方图

其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。

最常用的颜色空间：RGB颜色空间、HSV颜色空间。

颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。

（2）颜色集

颜色直方图法是一种全局颜色体征提取与匹配方法，无法区分局部颜色信息。颜色集是对颜色直方图的一种近似首先将图像从 RGB颜色空间转化成视觉均衡的颜色空间（如 HSV 空间），并将颜色空间量化成若干个柄。然后，用色彩自动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而将图像表达为一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之间的距离和色彩区域的空间关系

（3）颜色矩

这种方法的数学基础在于：图像中任何的颜色分布均可以用它的矩来表示。

此外，由于颜色分布信息主要集中在低阶矩中，因此，仅采用颜色的一阶矩（mean）、二阶矩（variance）和三阶矩（skewness）就足以表达图像的颜色分布。

（4） 颜色聚合向量

其核心思想是：将属于直方图每一个柄的像素分成两部分，如果该柄内的某些像素所占据的连续区域的面积大于给定的阈值，则该区域内的像素作为聚合像素，否则作为非聚合像素。

几种典型的形状特征描述方法：

通常情况下，形状特征有两类表示方法，一类是轮廓特征，另一类是区域特征。图像的轮廓特征主要针对物体的外边界，而图像的区域特征则关系到整个形状区域。

几种典型的形状特征描述方法：

（1）边界特征法该方法通过对边界特征的描述来获取图像的形状参数。其中Hough 变换检测平行直线方法和边界方向直方图方法是经典方法。Hough 变换是利用图像全局特性而将边缘像素连接起来组成区域封闭边界的一种方法，其基本思想是点—线的对偶性；边界方向直方图法首先微分图像求得图像边缘，然后，做出关于边缘大小和方向的直方图，通常的方法是构造图像灰度梯度方向矩阵。

（2）傅里叶形状描述符法

傅里叶形状描述符(Fourier shape descriptors)基本思想是用物体边界的傅里叶变换作为形状描述，利用区域边界的封闭性和周期性，将二维问题转化为一维问题。

由边界点导出三种形状表达，分别是曲率函数、质心距离、复坐标函数。 （3）几何参数法

形状的表达和匹配采用更为简单的区域特征描述方法，例如采用有关形状定量测度（如矩、面积、周长等）的形状参数法（shape factor）。在 QBIC 系统中，便是利用圆度、偏心率、主轴方向和代数不变矩等几何参数，进行基于形状特征的图像检索。

需要说明的是，形状参数的提取，必须以图像处理及图像分割为前提，参数

的准确性必然受到分割效果的影响，对分割效果很差的图像，形状参数甚至无法提取。

（4）形状不变矩法

利用目标所占区域的矩作为形状描述参数。 （5）其它方法

近年来，在形状的表示和匹配方面的工作还包括有限元法（Finite Element Method 或 FEM）、旋转函数（Turning Function）和小波描述符（Wavelet Descriptor）等方法。

基于小波和相对矩的形状体征提取与匹配：

该方法先用小波变换模极大值得到多尺度边缘图像，然后计算每一尺度的 7个不变矩，再转化为 10 个相对矩，将所有尺度上的相对矩作为图像特征向量，从而统一了区域和封闭、不封闭结构。

3 BP神经网络算法流程

BP网络的一个重要的用途就是用于模式识别。任务是要设计并训练出一个可行、高效的BP网络，以实现对0到9共10个数字和识别。

经图像预处理过程之后，可以将最终提取到的字符的特征送入BP网络进行训练及识别了。这里，假设设定的字符标准归一化的宽度为8，高度为16，那么对于每个字符就有128维的特征。

设计BP网络的关键之处在于高效的体征提取方法、大量有代表性的训练样本、高效稳定速收敛的学习方法。

BP网络应用过程如下图所示：

BP网络结构示意图如下所示：

4 BP学习过程

第一步 设置变量和参数，其中包括训练样本，权值矩阵，学习速率。 第二步 初始化，给各个权值矩阵一个较小的随机非零向量。 第三步 输入随机样本。

第四步 对输入样本，前向计算BP网络每层神经元的输入信号和输出信号。 第五步 由实际输出和期望输出求得误差。判断是否满足要求，若满足转第八步；步满足转第六步。

第六步 判断是否已经到了最大迭代次数，若到，转第八步，否则反向计算每层神经元的局部梯度。

第七步 根据局部梯度修正各个矩阵的权值。

第八步 判断是否学习完所有的样本，是则结束，否则转第三步。 需要注意的是以下几点：

A. 权值的初始化。权值的初始值应该选择均匀分布的小数经验值。初始值过大或者过小都会影响学习速度。为了避免权值的调整是同向的，应该将初始值设为随机数。

B. 初始权值不要太大。否则可能会处于误差平面较平坦的区域，从而导致算法无法收敛，训练失败。

C. 神经元的激励函数是s型函数。所以如果函数的渐近值是0，1的话，期望输出只能是小于1大于0的数，而不能是1或者0，否则可能会导致算法不收敛。在程序中建议读者用0.1来代表0，0.9代表1。

5 重要参数

6 特征提取方法 6.1 逐像素特征提取法

这是一种最简单的特征提取方法，对图像进行逐行逐列的扫描当遇到黑色象素时取其特征值为1，遇到白色象素时取其特征值为0，这样当扫描结束以后就形成了一个维数与图像中象素点的个数相同的特征向量矩阵。

这种算法可以由函数code实现：

/********************************** * 函数名称 code() *

* 参量：

* BYTE* lpDIBBits －指向输入图像的象素其实位置的指针 * int num －图片中样本的个数

* LONG lLineByte －输入图片每行的字节数 * LONG lSwidth －预处理时归一化的宽度 * LONG lSheight －预处理时归一化的长度 *

* 返回值：

* double** －特征向量矩阵（二维的）

*

* 函数功能 ：

* 对于输入样本提取特征向量，在这里把归一化样本的 * 每一个象素都作为特征提取出来

**************************************/

double** code (BYTE* lpDIBBits,int num, LONG lLineByte,LONG lSwidth,LONG lSheight)

{ //循环变量 int i,j,k; BYTE* lpSrc; // 建立保存特征向量的二维数组 double **data; // 为这个数组申请二维存储空间 data = alloc_2d_dbl(num,lSwidth*lSheight); // 将归一化的样本的每个象素作为一个特征点提取出来 //逐个数据扫描 for(k=0;k

方法分析：这种特征提取方法的特点是算法简单，运算速度快，可以使BP网络很快的收敛，训练效果好，缺点是适应性不强。但可以通过加大训练样本数

目的方法来增强其适应性。

6.2 骨架特征提取法

两副图像由于它们的线条的粗细不同，使得两幅图像差别很大，但是将它们的线条进行细化以后，统一到相同的宽度，如一个象素宽时，这时两幅图像的差距就不那么明显。利用图形的骨架作为特征来进行数码识别，就使得识别有了一定的适应性。我们一般使用细化的方法来提取骨架，细化的算法又很多如Hilditch算法，Rosenfeld算法等下面我们就来提供这两种算法的代码。 Hilditch细化算法：

/************************************************** * 函数名称：

* ThinnerHilditch *

* 参数：

* void* image －二值化图像矩阵前景色为1背景色为0 * unsigned longlx －图像的宽度 * unsigned longly －图像的高度 *

* 返回值 * 无 *

*函数功能：

* 对输入的图像进行细化，输出细化后的图像

***********************************************************

void ThinnerHilditch(void *image, unsigned long lx, unsigned long ly) {

char *f, *g; char n[10];

unsigned int counter; short k, shori, xx, nrn; unsigned long i, j;

long kk, kk11, kk12, kk13, kk21, kk22, kk23, kk31, kk32, kk33, size; size = (long)lx * (long)ly; g = (char *)malloc(size);

if(g == NULL) {

// printf(\ return; }

f = (char *)image; for(i=0; i

for(j=0; j

kk=i*ly+j; if(f[kk]!=0) {

f[kk]=1;

g[kk]=f[kk]; } } }

counter = 1;

do {

//printf(\ counter++; shori = 0;

for(i=0; i

for(j=0; j

kk = i*ly+j; if(f[kk]<0) f[kk] = 0; g[kk]= f[kk]; } }

for(i=1; i

for(j=1; j

kk=i*ly+j;

if(f[kk]!=1) continue;

kk11 = (i-1)*ly+j-1; kk12 = kk11 + 1; kk13 = kk12 + 1; kk21 = i*ly+j-1; kk22 = kk21 + 1; kk23 = kk22 + 1;

kk31 = (i+1)*ly+j-1; kk32 = kk31 + 1; kk33 = kk32 + 1;

if((g[kk12]&&g[kk21]&&g[kk23]&&g[kk32])!=0) continue;

nrn = g[kk11] + g[kk12] + g[kk13] + g[kk21] + g[kk23] + g[kk31] + g[kk32] + g[kk33];

if(nrn <= 1) {

f[kk22] = 2; continue; }

n[4] = f[kk11]; n[3] = f[kk12]; n[2] = f[kk13]; n[5] = f[kk21]; n[1] = f[kk23]; n[6] = f[kk31]; n[7] = f[kk32]; n[8] = f[kk33]; n[9] = n[1]; xx = 0;

for(k=1; k<8; k=k+2) {

if((!n[k])&&(n[k+1]||n[k+2])) xx++; }

if(xx!=1) {

f[kk22] = 2; continue; }

if(f[kk12] == -1) {

f[kk12] = 0; n[3] = 0; xx = 0;

for(k=1; k<8; k=k+2) {

if((!n[k])&&(n[k+1]||n[k+2])) xx++; }

if(xx != 1) {

f[kk12] = -1; continue; }

f[kk12] = -1; n[3] = -1; }

if(f[kk21]!=-1) {

f[kk22] = -1; shori = 1; continue; }

f[kk21] = 0; n[5] = 0; xx = 0;

for(k=1; k<8; k=k+2)

{

if((!n[k])&&(n[k+1]||n[k+2])) {

xx++; } }

if(xx == 1) {

f[kk21] = -1; f[kk22] = -1; shori =1; } else

f[kk21] = -1; } }

}while(shori);

free(g); }

ThinnerRosenfeld细化算法，代码如下：

/************************************************** * 函数名称：

* ThinnerRosenfeld *

* 参数：

* void* image －二值化图像矩阵前景色为1背景色为0 * unsigned longlx －图像的宽度 * unsigned longly －图像的高度 *

* 返回值 * 无 *

*函数功能：

* 对输入的图像进行细化，输出细化后的图像

***********************************************************

void ThinnerRosenfeld(void *image, unsigned long lx, unsigned long ly) {

char *f, *g; char n[10];

char a[5] = {0, -1, 1, 0, 0}; char b[5] = {0, 0, 0, 1, -1};

char nrnd, cond, n48, n26, n24, n46, n68, n82, n123, n345, n567, n781; short k, shori;

unsigned long i, j;

long ii, jj, kk, kk1, kk2, kk3, size; size = (long)lx * (long)ly;

g = (char *)malloc(size); if(g==NULL) {

printf(\ return; }

f = (char *)image;

for(kk=0l; kk

g[kk] = f[kk]; }

do {

shori = 0;

for(k=1; k<=4; k++) {

for(i=1; i

ii = i + a[k];

for(j=1; j

kk = i*ly + j;

if(!f[kk]) continue;

jj = j + b[k]; kk1 = ii*ly + jj;

if(f[kk1]) continue;

kk1 = kk - ly -1; kk2 = kk1 + 1; kk3 = kk2 + 1; n[3] = f[kk1]; n[2] = f[kk2]; n[1] = f[kk3]; kk1 = kk - 1; kk3 = kk + 1; n[4] = f[kk1]; n[8] = f[kk3];

kk1 = kk + ly - 1; kk2 = kk1 + 1; kk3 = kk2 + 1; n[5] = f[kk1]; n[6] = f[kk2]; n[7] = f[kk3];

nrnd = n[1] + n[2] + n[3] + n[4] +n[5] + n[6] + n[7] + n[8]; if(nrnd<=1) continue;

cond = 0;

n48 = n[4] + n[8]; n26 = n[2] + n[6]; n24 = n[2] + n[4]; n46 = n[4] + n[6]; n68 = n[6] + n[8]; n82 = n[8] + n[2];

n123 = n[1] + n[2] + n[3]; n345 = n[3] + n[4] + n[5];

n567 = n[5] + n[6] + n[7]; n781 = n[7] + n[8] + n[1];

if(n[2]==1 && n48==0 && n567>0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[6]==1 && n48==0 && n123>0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[8]==1 && n26==0 && n345>0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[4]==1 && n26==0 && n781>0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[5]==1 && n46==0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[7]==1 && n68==0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[1]==1 && n82==0)

{

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

if(n[3]==1 && n24==0) {

if(!cond) continue; g[kk] = 0; shori = 1; continue; }

cond = 1; if(!cond)

continue; g[kk] = 0; shori = 1; } }

for(i=0; i

for(j=0; j

kk = i*ly + j; f[kk] = g[kk]; } } }

}while(shori);

free(g); }

7 实验运行效果

对图像进行骨架提取的效果如下图所示：

对经过细化的图相利用EveryPixel函数进行处理就可以得到细化后图像的特征向量矩阵。

骨架特征提取的方法对于线条粗细不同的数码有一定的适应性，但是图像一旦出现偏移就难以识别。

本实验最终选用的是逐象素提取方法。在完成实验的过程中可以试用其他几种方法，从训练时间和识别率上加以对比。

本文来源：https://www.bwwdw.com/article/5khw.html