人工智能导论:状态空间搜索实验—八数码问题求解(6400字)

发表于:2017.11.12来自:www.ttfanwen.com字数:6400 手机看范文

昆明理工大学信息工程与自动化学院学生实验报告

( 2014—— 2015 学年 第 一 学期 )

课程名称:人工智能导论 开课实验室: 年 月 日

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

一、实验内容和要求

八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如:

(a) 初始状态 (b) 目标状态图1 八数码问题示意图

请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。

实验报告内容格式要求:XXXXXXXXXXXX(中文:宋体,小四;英文:Times New Roman)。

二、实验目的

1. 熟悉人工智能系统中的问题求解过程;

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;

3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、实验算法

启发函数设定

由八数码问题的部分状态图可以看出,从初始节点开始,在通向目标节点的路径上,各节点的数码格局同目标节点相比较,其数码不同的位置个数在逐渐减少,最后为零,因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息,利用这个信息来扩展节点的选择,减少搜索范围,提高搜索速度。

2、数据结构与算法设计

数码结构体

typedef struct node //八数码结构体

{

int form[N][N]; //数码组

int evalue; //评估值,差距

int udirec; //所屏蔽方向,防止往回推到上一状态,1上2下3左4右

struct node *parent; //父节点

}Graph;

Graph *Qu[MAX];//队列

Graph *St[MAX];//堆栈

搜索过程:(搜索采用广度搜索方式,利用待处理队列辅助,逐层搜索(跳过劣质节点))

a、把初始数码组压入队列;

b、从队列中取出一个数码组节点;

c、扩展子节点,即从上下左右四个方向移动空格,生成相应子节点:

d、对子节点数码组作评估,是否为优越节点,即其评估值是否小于等于其父节点加一,是则将其压入队,否则抛弃。

e、判断压入队的子节点数码组(优越点)的评估值,为零则表示搜索完成,退出搜索;

f、跳到步骤2;

四、程序框图

五、实验结果及分析

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

采用深度优先搜索方式 并简化搜索

六、结论

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

人工智能导论状态空间搜索实验八数码问题求解

1 2 0

2 3 4 0 1

2 4 5 6 0 1 3 目标完成

七、源程序及注释

#include <stdio.h> } //设计了搜索深度范围,防止队列内存越界

#include <stdlib.h> 6、运行结果

#include <time.h>

#define N 3 //数码组大小

#define Max_Step 50 //最大搜索深度

#define MAX 50

typedef struct node//八数码结构体

{

int form[N][N];//数码组

int evalue;//评估值

int udirect;//所屏蔽方向,防止往回推到上已状态,1上2下3左4右 struct node *parent;//父节点

/////////打印数码组

void Print(Graph *The_graph)

{

int i,j;

if(The_graph==NULL)

printf("图为空\n");

else

{

printf("---------------------\n");

for(i=0;i<N;i++)

{

printf("|\t");

for(j=0;j<N;j++)

{

printf("%d\t",The_graph->form[i][j]);//遍历打印

}

printf("\t|\n");

}

printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示

printf("---------------------\n");

}

}

/////////评价函数

int Evaluate(Graph *The_graph,Graph *End_graph)

{

int valute=0;//差距数

int i,j;

for(i=0;i<N;i++)

{

for(j=0;j<N;j++)

{

if(The_graph->form[i][j]!=End_graph->form[i][j]) {

valute++;

}

}

}

The_graph->evalue=valute;

return valute;

}

/////////移动数码组

Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph) {

Graph *New_graph;//

int HasGetBlank=0;//是否获取空格位置

int AbleMove=1;//是否可移动

int i,j,t_i,t_j,x,y;

for(i=0;i<N;i++)//获取空格坐标i,j

{

for(j=0;j<N;j++)

{

if(The_graph->form[i][j]==0)

{

HasGetBlank=1;

break;

}

}

if(HasGetBlank==1)

break;

}

//printf("空格位置:%d,%d\n",i,j);

t_i=i;

t_j=j;

//移动空格

switch(Direct)

{

case 1://上

t_i--;

if(t_i<0)

AbleMove=0;

break;

case 2://下

t_i++;

if(t_i>=N)

AbleMove=0;

break;

case 3://左

t_j--;

if(t_j<0)

AbleMove=0;

break;

case 4://右

t_j++;

if(t_j>=N)

AbleMove=0;

break;

}

if(AbleMove==0)//不能移动则返回原节点

{

return The_graph;

}

if(CreatNew_graph==1)

{

New_graph=(Graph *)malloc(sizeof(Graph));//生成节点 for(x=0;x<N;x++)

{

for(y=0;y<N;y++)

{

New_graph->form[x][y]=The_graph->form[x][y];//复制数码组

}

}

}

else

{

New_graph=The_graph;

}

//移动后

New_graph->form[i][j]=New_graph->form[t_i][t_j]; New_graph->form[t_i][t_j]=0;

//printf("移动产生的新图:\n");

//Print(New_graph);

return New_graph;

}

/////////搜索函数

Graph *Search(Graph *Begin,Graph *End)

{

Graph *g1,*g2,*g;

int Step=0;//深度

int Direct=0;//方向

int i;

int front,rear;

front=rear=-1;//队列初始化

g=NULL;

rear++;//入队

Qu[rear]=Begin;

while(rear!=front)//队列不空

{

front++;//出队

g1=Qu[front];

//printf("开始第%d个图:\n",front);

//Print(g1);

for(i=1;i<=4;i++)//分别从四个方向推导出新子节点 {

Direct=i;

if(Direct==g1->udirect)//跳过屏蔽方向

continue;

g2=Move(g1, Direct, 1);//移动数码组

if(g2!=g1)//数码组是否可以移动

{

//可以移动

Evaluate(g2, End);//评价新的节点

//printf("开始产生的第%d个图:\n",i); //Print(g2);

if(g2->evalue<=g1->evalue+1)

{

//是优越节点

g2->parent=g1;

//移动空格

switch(Direct)//设置屏蔽方向,防止往回推 {

case 1://上

g2->udirect=2;

break;

case 2://下

g2->udirect=1;

break;

case 3://左

g2->udirect=4;

break;

case 4://右

g2->udirect=3;

break;

}

rear++;

Qu[rear]=g2;//存储节点到待处理队列 if(g2->evalue==0)//为0则搜索完成 {

g=g2;

//i=5;

break;

}

}

else

{

free(g2);//抛弃劣质节点

g2=NULL;

}

}

}

if(g!=NULL)//为0则搜索完成

{

if(g->evalue==0)

{

break;

}

}

Step++;//统计深度

if(Step>Max_Step)

{

break;

}

}

return g;

}

/////////初始化一个八数码结构体

Graph *CR_BeginGraph(Graph *The_graph)

{

srand((unsigned)time(0));

int M=10;//随机移动步数

int Direct;

int i,x,y;

Graph *New_graph;

New_graph=(Graph *)malloc(sizeof(Graph));

for(x=0;x<N;x++)

{

for(y=0;y<N;y++)

{

New_graph->form[x][y]=The_graph->form[x][y]; }

}

for(i=0;i<M;i++)

{

Direct=rand()%4+1;//产生1-4随机数

//printf("Direct:%d\n",Direct);

New_graph=Move(New_graph, Direct, 0);

//Print(New_graph);

}

New_graph->evalue=0;

New_graph->udirect=0;

New_graph->parent=NULL;

return New_graph;

}

int main (int argc, const char * argv[])

{

// insert code here...

/*

Graph Begin_graph={

{{2,8,3},{1,6,4},{0,7,5}},0,0,NULL

};

Graph Begin_graph={

{{2,8,3},{1,0,4},{7,6,5}},0,0,NULL

};

Graph Begin_graph={

{{2,0,1},{4,6,5},{3,7,8}},0,0,NULL

};

*/

//目标数码组

Graph End_graph={

{{1,2,3},{8,0,4},{7,6,5}},0,0,NULL

};

//初始数码组

Graph *Begin_graph;

Begin_graph=CR_BeginGraph(&End_graph);//随机产生初始数码组 Evaluate(Begin_graph, &End_graph);//对初始的数码组评价 printf("初始数码组:\n");

Print(Begin_graph);

printf("目标数码组:\n");

Print(&End_graph);

Graph *G,*P;

int top=-1;

//图搜索

G=Search(Begin_graph, &End_graph);

//打印

if(G)

{

//把路径倒序

P=G;

//压栈

while(P!=NULL)

{

top++;

St[top]=P;

P=P->parent;

}

printf("<<<<<<<<<<<<<<<搜索结果>>>>>>>>>>>>>>>>\n"); //弹栈打印

while(top>-1)

{

P=St[top];

top--;

Print(P);

}

printf("<<<<<<<<<<<<<<<<<完成>>>>>>>>>>>>>>>>>>\n"); }

else

{

printf("搜索不到结果,深度为%d\n",Max_Step);

//设计搜索深度范围主要是防止队列内存越界

}

return 0;

}




第二篇:人工智能导论实验指导书 11400字

实验一 基本的搜索技术

【实验目的】

通过运行演示程序,理解深度优先、广度优先、A*算法的原理和运行过程。

【实验内容】

1. 分别以深度优先、广度优先、A*算法为例演示搜索过程

2. 观察运行过程记录搜索顺序

3. 设置不同属性,观察和记录搜索过程的变化

4. 分析不同算法的特点

【实验原理】

在知识不完全时,一般不存在成熟的求解算法可以利用,只有利用已有的知识摸索前进,从许多可能的解中寻找真正的解这就是搜索。即使对于结构性能较好,理论上有算法可依的问题,由于问题本身的复杂性以及计算机在时间、空间上的局限性,往往也需要通过搜索来进行求解。

总的来说搜索策略分为两大类:盲目搜索和启发式搜索

一、无信息的搜索策略——盲目搜索

在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随即调用操作算子)进行的搜索,它能快速地运用一个操作算子。盲目搜索中,由于没有可参考的信息,因此只要能匹配的操作算子都须运用,这会搜索更多的状态。最重要的宽度优先和深度优先是最重要的盲目搜索方法。

1. 宽度优先搜索:从根结点出发,按从低到高的层次顺序搜索,同一层的结点按固定的顺序(例如从左到右、从右到左)搜索。宽度优先总是先搜索到距离最近的目标结点。宽度优先搜索不适合用于分支较多的情况。

2. 深度优先搜索:用回溯的思想搜索图。深度优先搜索适用于分支较多而层次较浅的情况。

二、利用知识引导搜索——启发式搜索

盲目搜索复杂度很大,为了提高算法效率,应该具体问题具体分析,利用与问题有关的信息,从中得到启发而来引导搜索,以达到减少搜索量的目的,这就 1

是启发式搜索。

启发信息:

(1) 陈述性启发信息:一般被用于更准确、更精炼地描述状态,使问题的状态空间缩小,如待求问题的特定状况等属于此类信息

(2) 过程性启发信息:一般被用于构造操作算子,使操作算子少而精 如一些规律性知识等属于此类信息

(3) 控制性启发信息:如何选择操作算子

控制性启发信息往往被反映在估价函数之中。估价函数的任务就是估计待搜索结点的“有希望”程度(或者说估计操作算子的“性能”),并依此给它们排定次序。

估价一个结点的价值,必须综合考虑两方面的因素:已经付出的代价(实际)和将要付出的代价(估计)

f (n) = g (n) + h (n)

采用这种估价函数的搜索叫A搜索。令h*(n)为n到目的结点的实际最小代价,如果对任意节点n均有h(n)≤h*(n),则此时的A算法为A*算法。

如某一问题有解,那么利用A*搜索算法对该问题进行搜索则一定能搜索到解,并且一定能搜索到最优的解而结束。

这三种搜索算法都使用了两张表来记录状态信息:在open表中保留所有已生成而子状态未扩展的状态;在closed表中记录已扩展过子状态的状态。

广度优先搜索算法中的open表采用的是先进先出的“队列”。

深度优先搜索算法中的open表采用的是后进先出的“栈”。

启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一个表,每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃其它的状态,而把它们保留在open表中。

【实验步骤】

1. 浏览器打开下面网址,单击“Start Applet”按钮进入演示系统

http://cai./jpkc/rengongzhineng/rengongzhineng/search/search.html

2

人工智能导论实验指导书

人工智能导论实验指导书

图1 演示系统 图2 3

2. 单击主菜单中“File”→“Load Sample Graph”,载入一个例子(例如“简单搜索树”),如图2红色椭圆标注,激活左侧“create”卡,鼠标指针指向右侧图中的结点或边,右击弹出菜单,单击“Properties”(即属性),可以查看或修改结点或边的属性。结点的heuristics属性表示结点的启发值,边的Edge cost属性表示边的代价。

(A*算法中结点的估价函数值为从开始结点到该结点所有边的代价和再加上该结点的启发值。

8 5

人工智能导论实验指导书

3

图3

如图3所示B的估价值为13。)

3. 查看并记录所有结点的启发值和边的代价。

4. 激活左侧的“Solved”卡,如图4红色椭圆标注

人工智能导论实验指导书

4 图4

5. 单击主菜单中“Search Algorithms”,分别选定“Depth First”、“Breadth First”、“A*”。重复单击左侧“Step”按钮(图4蓝色椭圆标注),直到右侧图中所有结点访问完毕。记录访问的结点顺序,并与自己预测的深度优先、宽度优先、A*的搜索顺序比较。

(注:运行过程中红色的结点保存于closed表中,绿色的结点保存于open表中,蓝色的结点表示新展开的结点)

6. 单击主菜单中“File”→“Create new Graph”,激活左侧“create”卡,新建一个图。分别选定“Depth First”、“Breadth First”、“A*”,进行搜索,记录搜索顺序,并与自己预测的深度优先、宽度优先、A*的搜索顺序比较。

人工智能导论实验指导书

5

实验二 传教士和野人问题

【实验目的】

通过具体问题的编程求解,了解人工智能的基本解决方法;使用一种搜索策略,以加深理解。

【实验内容】

设在河的一岸有三个野人、三个传教士和一条船,要用这条船把所有的人运到河对岸,但受以下条件的约束:

(1) 传教士和野人都会划船,但每次船上至多可载两个人;

(2) 二是在河的任一岸,如果野人数目超过修道士数,传教士会被野人吃掉。

(3) 如果野人会服从任何一次过河安排

编程实现一个确保传教士和野人都能过河,且没有传教士被野人吃掉的安全过河计划。

【实验原理】

传教士和野人问题是一个经典的智力游戏问题。有N个传教士和N个野人来到河边准备渡河,河岸(甲岸和乙岸)有一条船,每次至多可供k人乘渡。应如何规划摆渡方案,使得任何时刻,在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中,任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。

设N=3,k=2,则给定的问题可用下图表示,图中L和R表示左岸和右岸,B=1或0分别表示有船或无船。约束条件是:两岸上M≥C,船上M+C≤2

图1 M-C问题实例

人工智能导论实验指导书

简单的分析,总共有10种可能的操作:

两个野人过河(从甲到乙,从乙到甲)

两个传教士过河从(从甲到乙,从乙到甲)

6

一个传教士和一个野人过河(从甲到乙,从乙到甲)

一个野人过河(从甲到乙,从乙到甲)

一个传教士过河(从甲到乙,从乙到甲)

但对于一个具体状态,只有5种可能的操作(从甲到乙或从乙到甲)。

先来看看问题的初始状态和目标状态,假设和分为甲岸和乙岸:

初始状态:甲岸,3野人,3牧师;

乙岸,0野人,0牧师;

船停在甲岸,船上有0个人;

目标状态:甲岸,0野人,0牧师;

乙岸,3野人,3牧师;

船停在乙岸,船上有0个人;

整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的,所以合理的渡河操作就成了通常所说的算符,根据题目要求,可以得出以下5个算符(按照渡船方向的不同,也可以理解为10个算符):

渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师

算符知道以后,剩下的核心问题就是搜索方法了,本文以深度优先搜索为基础,通过一个FindNext(?)函数找出下一步可以进行的渡河操作,如果没有找到则返回其父节点,看看是否有其它兄弟节点可以扩展,然后用Process(?)函数递规调用FindNext(?),一级一级的向后扩展。

搜索中的算符采用下面的规则固定排序,合理的排序能更快的搜索到较优的解:

甲岸一次运走的人越多越好(即甲岸运多人优先),同时野人优先运走;乙岸一次运走的人越少越好(即乙岸运少人优先),同时牧师优先运走;

同时注意下面两点:

1. 不能重复上次渡船操作(通过链表中前一操作比较),避免进入死循环;

2. 任何时候河两边的野人和牧师数均分别大于等于0且小于等于3;

【实验过程】

设计程序求解传教士和野人问题。附录C++程序及注释如下:

7

//wildman.cpp

#include "iostream.h"

typedef struct _riverside // 岸边状态类型

{

int wildMan; // 野人数

int churchMan; // 牧师数

}RIVERSIDE;

typedef struct _boat // 船的状态类型

{

int wildMan; // 野人数

int churchMan; // 牧师数

}BOAT;

typedef struct _question // 整个问题状态

{

RIVERSIDE riverSide1; // 甲岸

RIVERSIDE riverSide2; // 乙岸

int side; // 船的位置, 甲岸为-1, 乙岸为1 BOAT boat; // 船的状态

_question* pPrev; // 指向前一渡船操作

_question* pNext; // 指向后一渡船操作

}QUESTION;

//函数定义

bool Process(QUESTION* pQuest);

bool FindNext(QUESTION* pQuest);

void VisitList(QUESTION* pQuest); //遍历链表输出结果

//

int main()

{

// 初始化

QUESTION* pHead = new QUESTION;

pHead->riverSide1.wildMan = 3;

pHead->riverSide1.churchMan = 3;

pHead->riverSide2.wildMan = 0;

pHead->riverSide2.churchMan = 0;

pHead->side = -1; // 船在甲岸

pHead->pPrev = NULL;

pHead->pNext = NULL;

pHead->boat.wildMan = 0;

pHead->boat.churchMan = 0;

if (Process(pHead))

8

{

cout<<"成功渡河!"<<endl;

VisitList(pHead);

}

else

cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;

// 回收内存空间

while (pHead)

{

QUESTION* pTemp = pHead->pNext;

delete pHead;

pHead=pTemp;

}

pHead = NULL;

return 0;

}

// 渡船过程, 递归调用函数FindNext(...)

bool Process(QUESTION* pQuest)

{

if (FindNext(pQuest))

{

QUESTION* pNew = new QUESTION;

pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan pQuest->boat.wildMan*(pQuest->side);

pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan pQuest->boat.churchMan*(pQuest->side);

pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;

pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan; pNew->side = (-1)*pQuest->side;

pNew->pPrev = pQuest;

pNew->pNext = NULL;

pNew->boat.wildMan = 0;

pNew->boat.churchMan = 0;

pQuest->pNext = pNew;

if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3) return true; // 完成

return Process(pNew);

}

else

{

QUESTION* pPrev = pQuest->pPrev;

if (pPrev == NULL)

+ + 9

return false; // 无解

delete pQuest;

pPrev->pNext = NULL;

return Process(pPrev); // 返回其父节点重新再找

}

return true;

}

// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作 // 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧

bool FindNext(QUESTION* pQuest)

{

// 基本规则

// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先. static BOAT boatState[5]; // 5个算符

if (pQuest->side == -1)

{

boatState[0].wildMan = 2;

boatState[0].churchMan = 0;

boatState[1].wildMan = 1;

boatState[1].churchMan = 1;

boatState[2].wildMan = 0;

boatState[2].churchMan = 2;

boatState[3].wildMan = 1;

boatState[3].churchMan = 0;

boatState[4].wildMan = 0;

boatState[4].churchMan = 1;

}

else

{

boatState[0].wildMan = 0;

boatState[0].churchMan = 1;

boatState[1].wildMan = 1;

boatState[1].churchMan = 0;

boatState[2].wildMan = 0;

boatState[2].churchMan = 2;

boatState[3].wildMan = 1;

boatState[3].churchMan = 1;

boatState[4].wildMan = 2;

boatState[4].churchMan = 0;

}

int i; // 用来控制算符

if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0)

// 初始状态, 第一次渡河时

10

i = 0; // 取算符1

else

{

for (i=0; i<5; i++) // 扩展同一节点时, 已用过的算符不再用, 按优先级来 if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)

break;

i++;

}

if (i < 5)

{

int j;

for (j=i; j<5; j++)

{

int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;

int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;

int nWildMan2 = 3 - nWildMan1;

int nChurchMan2 = 3 - nChurchMan1;

// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0 if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&

(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&

nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)

{

// 本操作是否重复上次操作,注意方向不同

if (pQuest->pPrev != NULL)

{

if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&

pQuest->pPrev->boat.churchMan == boatState[j].churchMan)

continue;

}

break; // 该操作可行, 推出循环

}

}

if (j < 5)

{

pQuest->boat.wildMan = boatState[j].wildMan;

pQuest->boat.churchMan = boatState[j].churchMan;

return true;

}

11

}

return false;

}

//遍历链表输出结果

void VisitList(QUESTION* pQuest)

{

QUESTION* HD=pQuest;

cout<<"甲岸[野人,传教士]数量的变化:"<<endl;

while(HD!=NULL)

{

cout<<"["<<(HD->riverSide1).wildMan<<","<<HD->riverSide1.churchMan<<"]"; if(HD->pNext!=NULL)

cout<<"-->";

HD=HD->pNext;

}

cout<<endl;

}

12

实验三 八数码问题

【实验目的】

启发式搜索就是利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。本实验通过解决八数码问题,帮助学生更好的熟悉和掌握启发式搜索的定义、估价函数和算法过程。

【实验内容】

在3×3的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态S0,目标状态Sg,如下图所示。可以使用的操作有

空格左移,空格上移,空格右移,空格下移

即只允许把位于空格左、上、右、下方的牌移入空格。请编程实现该问题的解决。

S0 Sg 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5

【实验原理】

一、搜索策略简介

1. 无信息的搜索策略——盲目搜索

在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随即调用操作算子)进行的搜索,它能快速地运用一个操作算子。盲目搜索中,由于没有可参考的信息,因此只要能匹配的操作算子都须运用,这会搜索更多的状态。

2. 有信息的搜索——启发式搜索

考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选取较合适的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态,提高搜索效率。

启发式搜索每使用一个操作算子便需做更多的计算与判断,其性能一般要优于盲目搜索,但不可过于追求更多的甚至完整的启发信息。

二、搜索算法

1. 辅助用的数据结构

open表:记录已生成但其子状态未扩展的状态。

closed表:记录其子状态已被扩展的状态。

13

(1) 广度优先搜索算法中的open表采用的是先进先出的“队列”。

(2) 深度优先搜索算法中的open表采用的是后进先出的“栈”。

(3) 启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一

个表,每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃

其它的状态,而把它们保留在open表中。

2. 算法过程

Procedure breadth_first_search

Begin

Open:=[start];closed:=[ ];

While open ≠ [ ] do

Begin

从open表中删除第一个状态,称之为n;

将n放入closed表中;

If n=目的状态 Then Return(success);

生成n的所有子状态;

从n的子状态中删除已在open或closed表中出现的状态;

{*避免循环搜索*}

将n的其余子状态,由不同的算法按不同的顺序加入到open表;

End;

End.

三、启发式策略中估价函数的确定

启发式策略中的“启发”(heuristic)可以体现在三个方面:问题的表达;操

作算子的构造;操作算子的选择。这里特别关注操作算子的选择——控制性启发

信息。

控制性启发信息往往被反映在估价函数之中。估价函数的任务就是估计待搜

索结点的“有希望”程度(或者说估计操作算子的“性能”),并依此给它们排定

次序。

估价一个结点的价值,必须综合考虑两方面的因素:已经付出的代价(实际);

将要付出的代价(估计)

f (n) = g(n) + h(n)

g(n)项保持了搜索的宽度优先成分,有利于搜索的完备性,但会影响搜索的

效率,h(n)体现了搜索的启发信息,有利于搜索的效率,但影响搜索的完备性。

定义h*(n)为状态n到目的状态的最优路径的代价。对一具体问题,只要有

解,则一定存在h*(n)。于是,当要求估价函数f(n)中的h(n)都小于等于h*(n)即

14 {*初始化*}

h(n)≤h*(n) 时,A搜索算法就成为A*搜索算法。

【例】八数码问题的搜索树

初始 S0

2 8 3

7 5 1 2 3 4 7 6 5 1 6 4 —

Sg(0)

其估价函数可以定义为:

f(n) = d(n) + w(n) (1) 其中d(n)代表状态的深度,每步为单位代价;w(n)表示以“不在位”的将牌数。

估价函数的另一个定义为:

f(n) = d(n) + p(n) (2)

其中p(n) = 将牌“不在位”的距离和。

采用这两种估价函数的A算法都是A*算法。附录程序采用的估价函数为(2)式,但其d(n)=0。

【实验过程】

估价函数:

////////////////////////////////////

// CaculateH:计算当前H值

// 参数:当前节点

// 返回值:H值

////////////////////////////////////

int CMain::CaculateH(CDisplay *Item)

{

DataType Src[MaxItem][MaxItem]; for(int i=0; i<MaxItem; i++) for(int j=0; j<MaxItem; j++) Src[i][j] = Item->GetDispData(i,j); // 数组Src为当前状态 int Hop = 0; for(i=0; i<MaxItem; i++) for(int j=0; j<MaxItem; j++) { 15

if(Src[i][j] == m_Desc[i][j]) continue; // 数组m_Desc为目标状态 if(Src[i][j] == 0 ) continue;

else

{

int Hhop = Scan(Src[i][j], Position(i,j));

if(Hhop == 65535) return 65535;

Hop += Hhop;

}

}

return Hop;

}

//////////////////////////////////////////////

// Scan: 扫描 计算H值的辅助函数

// 入口:CaculateH()

// 参数:i的位置,与i的值

// 返回值:H(i)的值

//////////////////////////////////////////////

int CMain::Scan(DataType Desc,Position Srcpos)

{

Position Descpos;

for(int i=0;i<MaxItem;i++)

for(int j=0;j<MaxItem;j++)

{

if(this->m_Desc[i][j] == Desc) //m_Desc数组表示目标状态 {

Descpos = Position(i,j);

return (int)fabs(Descpos.x - Srcpos.x)

+(int)fabs(Descpos.y-Srcpos.y);

}

}

return 65535;

}

附录1:广度优先搜索eightnum.c

附录2:A*算法 8数码A星VC.rar

16

更多类似范文
┣ 人工智能大作业八数码问题 3700字
┣ 采用A算法解决八数码问题 10400字
┣ 人工智能A算法八数码报告 8300字
┣ 实验一 八数码 5100字
┣ 更多八数码问题实验报告
┗ 搜索类似范文

更多相关推荐:
人工智能实验报告800字

华北电力大学实验报告实验名称课程名称人工智能及应用专业班级软件0902学生姓名董一号20xx0920xx4成绩指导教师刘丽实验日期20xx429学实验报告如打印纸张用A4左装订页边距上下25cm左29cm右21...

prolog实验报告600字

华北电力大学实验报告实验名称PROLOG语言编程练习及图搜索问题求解课程名称人工智能及应用专业班级学生姓名学号成绩指导教师实验日期20xx年5月实验报告如打印纸张用A4左装订页边距上下25cm左29cm右21c...

人工智能实验报告(华北电力大学科技学院)600字

华北电力大学科技学院实验报告实验名称课程名称人工智能及应用专业班级软件12k1学生姓名马云峰号1219xx020xx6成绩指导教师刘丽实验日期20xx514学华北电力大学科技学院实验报告第页共页华北电力大学科技...

专栏推荐
大家在关注

地图地图CC