文档视界 最新最全的文档下载
当前位置:文档视界 › 人工智能实验报告

人工智能实验报告

人工智能实验报告
人工智能实验报告

计算机科学与技术1341901301 敏

实验一:知识表示方法

一、实验目的

状态空间表示法是人工智能领域最基本的知识表示方法之一,也是进一步学习状态空间搜索策略的基础,本实验通过牧师与野人渡河的问题,强化学生对知识表示的了解和应用,为人工智能后续环节的课程奠定基础。

二、问题描述

有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定野人与牧师都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出小船来回次数最少的最佳方案。

三、基本要求

输入:牧师人数(即野人人数):n;小船一次最多载人量:c。

输出:若问题无解,则显示Failed,否则,显示Successed输出一组最佳方案。用三元组(X1, X2, X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程:初始状态->中间状态->目标状态。

例:当输入n=2,c=2时,输出:221->110->211->010->021->000

其中:X1表示起始岸上的牧师人数;X2表示起始岸上的野人人数;X3表示小船现在位置(1表示起始岸,0表示目的岸)。

要求:写出算法的设计思想和源程序,并以图形用户界面实现人机交互,进行输入和输出结果,如:

Please input n: 2 Please input c: 2

Successed or Failed?: Successed

Optimal Procedure: 221->110->211->010->021->000

四、算法描述

(1)算法基本思想的文字描述;

从初始状态S(n,n,1)出发,形成的有合法且未达状态S11、S12、……、Sli 。再分别从S11、

S12、……、Sli 出发形成所有合法而未达状态S111、S112、…… 、Sli1、Sli2、Sli ……最终

达到目标(0,0,0)(有解),或者找不到合法而未达状态(无解)。若有解,则从目标返回找

前趋状态,前趋状态的前趋状态……直到初始状态。

(2)判别(X1,X2,X3)为合法状态条件:X1=0或X1=n 或X1=X2。

(3)数据结构:

1 栈STACK ,记下“已达”状态及踪迹,并兼作队列。

2 STATE[X1][X2]=

(4)算法基本思想的具体实现:

1 初始化:置STA TE[N+1][N+1][2]中的有状态为“未达”

置队列STACK 空,cond 为当前是否已达到目标: cond=

cond 置初值

2 以S (n,n,1)为始点,置STA TE 为“已达”。S 入队列STACK

3 while (队列STACK 空且未达到目标时)

A{ 取出队头元素地址=>p1,队头元素出队列

B while (未达到目标,且P1有可达、合法、且未到达过的相邻顶点Q )

if (Q=(000) 则{cond=1,Q 入队列}

否则 {置QW 为“已达”,Q 入队列} /* B 可用函数COMBINE 实现 */

4 if (cond=1)则按队列中前趋指针指示的次序依次输出序列,否则输出“渡河失败”。

5 COMBINE 函数的功能等价于从数量不等的物品,分别选出1件、2件、……C 件物品的

所有组合,同时对每一种组合确定其合法性。

COMBINE ( )

{ 1 栈SP 初始化(SP 存放已放入物品序号),NUM 为已取出物品个数,NUM=0,i 为准备取

出物品序号,i<=1。

2 do {

while (未达到目标,且所有物品还未取尽,且NUM

{若该种物品已取尽,则取下一种,i++;

取出第i 种物品中一件来,该物来序号(即i )进栈,NUM++;

判断该状态合法否?! /* 用函数dicision 实现 */

0 已达 1 未达

0 未达目标

1 已达到目标

}

if (未达到目标,且栈SP不空)

{则读栈SP=>i,将第种物品放回一件:NUM--:退栈;i++;}

}while(未达到目标,且并非所有情况均已列举完)

}

dicision ( )

{ if (当前状态(x1,x2,x3)合法且未达)

则(x1,x2,x3)及前趋指针入队列STACK;

if ((x1,x2,x3)==0,0,0)) 则cond=1;

}

五、源程序

#include

typedef struct node

{

int np; /* The normal people's number at start shore. */

int mp; /* The mad people's number at start shore. */

int shore; /* '0'=end shore,'1'=start shore */

int track; /* The track of the point */

}NODE;

NODE stack[80]; /* The massage from stack[1]*/

int state[80][80][2],n,c,front,back,cond;

void dicision(int t[])

{

int a[4],i;

for(i=0;i<4;i++) a[i]=t[i];

if(a[2]==1)

{

a[0]=n-a[0];

a[1]=n-a[1];

}

if((a[0]==0||a[0]==n||a[0]==a[1]) && state[a[0]][a[1]][a[2]]==1)

{

back++;

stack[back].np=a[0];

stack[back].mp=a[1];

stack[back].shore=a[2];

stack[back].track=front;

}

state[a[0]][a[1]][a[2]]=0;

if(a[0]==0 && a[1]==0 && a[2]==0)

cond=1;

}

void combine(int t[])

{

int sp[80];/* The stack */

int top; /* The stack sp's top*/

int all; /* The people's number at start shore */

int num; /* The things number which allready get */

int i;

top=i=num=0; t[2]=!t[2]; all=t[0]+t[1];

do

{

while(cond!=1 && num0 && i<2)

{

if(t[i]==0)

{

if(i<1) i++;

else return;

}

t[i]--;

sp[top++]=i;

num++;

all--;

dicision(t);

}

if(cond!=1 && top>0)

{

i=sp[--top];

t[i]++; all++; num--; i++;

}

}while(cond!=1&&( top>0 || (i<2&&all>0) ) );

}

void put(NODE stack[])

{

int i,j,m,b[80];

printf("\nStack Np Mp Shore Last point\n");

for(i=1;i<=back;i++)

printf("<%2d >%5d%5d%7d%10d\n",i,stack[i].np,stack[i].mp,stack[i].shore,stack[i].track); if(cond==1)

{

i=back;m=0;

while(i!=0)

{

b[m++]=i; i=stack[i].track;

}

printf("The cross way is: ");

for(j=m-1;j>=0;j--)

{

printf("(%d,",stack[b[j]].np);

printf("%d,",stack[b[j]].mp);

printf("%d",stack[b[j]].shore);

if(j!=0)

printf(")->");

}

printf(")\n");

printf("The stack is: %d->",back);

for(j=0;j

{

printf("%d",stack[b[j]].track); if(j!=m-2) printf("->");

}

printf("\nSeccess!");

}

else printf("Failure!");

printf("\n");

}

void main()

{

int i,j,s,t[4];

printf("please input the number of people (n): "); scanf("%d",&n); printf("please input the capacity of boat (c): "); scanf("%d",&c);

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

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

for(s=0;s<2;s++)

state[i][j][s]=1;

front=back=0;

cond=0;

state[n][n][1]=0;

back++;

stack[back].np=n;

stack[back].mp=n;

stack[back].shore=1;

stack[back].track=0;

while(back>front && cond!=1)

{

front++;

t[0]=stack[front].np;

t[1]=stack[front].mp;

t[2]=stack[front].shore;

t[3]=stack[front].track;

if(t[2]==0)

{ t[0]=n-t[0]; t[1]=n-t[1]; }

combine(t);

}

put(stack);

}

六、运行结果

实验二:九宫重排

一、实验目的

A*算法是人工智能领域最重要的启发式搜索算法之一,本实验通过九宫重排问题,强化学生对A*算法的理解与应用,为人工智能后续环节的课程奠定基础。

二、问题描述

给定九宫格的初始状态,要求在有限步的操作,使其转化为目标状态,且所得到的解是代价最小解(即移动的步数最少)。如:

三、基本要求

输入:九宫格的初始状态和目标状态

输出:重排的过程,即途径的状态

四、实验组织运行要求

本实验采用集中授课形式,每个同学独立完成上述实验要求。

五、实验条件

每人一台计算机独立完成实验。

六.算法描述

procedure heuristic_search

open :=[start] ;closed:=[ ] ;f(s) := g(s) + h(s) ;

while open != [ ] do

begin

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

if n = 目的状态then return (success) ;

生成n 的所有子状态;

if n 没有任何子状态then continue ;

for n 的每个子状态do

case 子状态is not already on open 表or closed 表:

begin

计算该子状态的估价函数值;

将该子状态加到open 表中;

end ;

case 子状态is already on open 表:

if 该子状态是沿着一条比在open 表已有的更短路径而到达

then 记录更短路径走向及其估价函数值;

case 子状态is already on closed 表:

if 该子状态是沿着一条比在closed 表已有的更短路径而到达

begin

将该子状态从closed 表移到open 表中;

记录更短路径走向及其估价函数值;

end ;

case end ;

将n 放入closed 表中;

根据估价函数值,从小到大重新排列open 表;

end ;

return (failure);

end

七.源代码

#include

using namespace std;

const int N = 3; //数组的维数

const int M = 100; //open 和close的大小

const static int goal[N][N] = {{1,2,3},//目标状态

{8,0,4},

{7,6,5}};

struct state //状态结点

{

int arrState[N][N];

int value; //该结点的启发值f(n)

int depth; //所在的第几层

int parent; //父节点

int nID; //结点标记

public:

state()

{

for(int i=0; i

for(int j=0; j

arrState[i][j] = -1;

value = -1; //该结点的启发值f(n)

depth = -1; //所在的第几层

parent = -1; //父节点

nID = -1; //结点标记

}

state& operator = (state s)

{

for(int i=0; i

for(int j=0; j

arrState[i][j] = s.arrState[i][j];

value = s.value;

depth = s.depth;

parent = s.parent;

nID = s.nID;

return *this;

}

bool operator == (state s)

{

for(int i=0; i

for(int j=0; j

if(arrState[i][j] != s.arrState[i][j])

return false;

return true;

}

bool operator != (state s)

{

return !(*this == s);

}

};

class Eight

{

private:

state open[M]; //open 表

int openIndex;//open表的元素个数

state closed[M]; //close 表

int closedIndex;//closed 表的元素个数

int start[N][N];//开始的状态

int nAutoIncrease;

public:

Eight();

Eight(int s[][N]);

void init();//初始化open 和close

int f(state s);

int w(int s[N][N]);

void sortOpen();//对Open表进行排序

void moveToClosed(state s);

//void moveToOpen(state s);

void genToOpen(state s);

void findZeroPostion(int &x,int &y, state s);//查找0 的位置进行上下左右移动bool compare(state s); //当前的状态与目标状态比较

void genNewState(state oldState);

void heuristicSearch();//查找路径

bool IsInOpen(state s);

bool IsInClosed(state s);

void move(state des,state src);

bool IsCanSolve(int s[N][N]);

void findPath();

void show(state s);

};

Eight::Eight()

{

start[0][0] = 2;

start[0][1] = 8;

start[0][2] = 3;

start[1][0] = 1;

start[1][1] = 6;

start[1][2] = 4;

start[2][0] = 7;

start[2][1] = 0;

start[2][2] = 5;

nAutoIncrease = 1;

openIndex = -1;

closedIndex = -1;

}

Eight::Eight(int s[][N])

{

for(int i = 0; i

for(int j = 0; j

start[i][j] = s[i][j];

nAutoIncrease = 1;

openIndex = -1;

closedIndex = -1;

}

void Eight::init()

{

for(int i = 0; i

for(int j = 0; j

open[0].arrState[i][j] = start[i][j];

open[0].nID = 0;

open[0].depth = 0;

open[0].parent = 0;

open[0].value = w(start) + 0; //f(0) = w(0) +d(0)

openIndex = 0;

closedIndex = -1;

}

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

void Eight::show(state s)

{

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

{

cout<<"\t";

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

cout<

cout<

}

cout<

// cout<<"fn="<

}

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

//启发值f(n) = depth + w(n)

int Eight::f(state s)

{

return s.depth + w(s.arrState);

}

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

//计算不在位w(n)的值

int Eight::w(int s[N][N])

{

int count = 0;

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

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

{

if(s[i][j] == 0 )//不考虑0的位置

continue;

if(s[i][j] != goal[i][j])

count++;

}

return count;

}

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

// sort for Open table

void Eight::sortOpen()

{

state temp;

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

for(int j = i+1; j < openIndex+1; j++)

if(open[i].value > open[j].value)

{

temp = open[i];

open[i] = open[j];

open[j] = temp;

}

}

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

// find current state '0' postion

void Eight::findZeroPostion(int &x, int &y, state s) {

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

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

if(s.arrState[i][j] == 0)

{

x = i; //保持行坐标

y = j; //保存列坐标

return;

}

}

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

// the two states exchange

void Eight::move(state des, state src)

{

for(int row = 0; row

for(int col = 0; col

des.arrState[row][col] = src.arrState[row][col];

des.depth = src.depth;

des.parent = src.parent;

des.value = src.value;

}

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

// extend other states

void Eight::genNewState(state oldState)

{

int row,col;

int temp;//保存状态转换数组中的值

state newState;

findZeroPostion(row,col,oldState);//find zero position

if(row +1 < N)//0向下移动

{

//move(newState, oldState);

newState = oldState;

newState.depth = oldState.depth +1;

newState.parent = oldState.nID;

newState.nID = nAutoIncrease++;//对ID自动编号

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row+1][col];

newState.arrState[row+1][col] = temp;

newState.value = w(newState.arrState) + newState.depth;

//newState.value = f(newState);

//push newState to open

genToOpen(newState);

}

if(row - 1 > -1)//0向上移动

{

newState = oldState;

newState.depth = oldState.depth +1;

newState.parent = oldState.nID;

newState.nID = nAutoIncrease++;//对ID自动编号

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row-1][col];

newState.arrState[row-1][col] = temp;

newState.value = w(newState.arrState) + newState.depth;

//newState.value = f(newState);

//push newState to open

genToOpen(newState);

}

if(col +1 < N)//0向右移动

{

newState = oldState;

newState.depth = oldState.depth +1;

newState.parent = oldState.nID;

newState.nID = nAutoIncrease++;//对ID自动编号

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row][col+1];

newState.arrState[row][col+1] = temp;

newState.value = w(newState.arrState) + newState.depth;

//newState.value = f(newState);

//push newState to open

genToOpen(newState);

}

if(col -1 > -1)//0向左移动

{

newState = oldState;

newState.depth = oldState.depth +1;

newState.parent = oldState.nID;

newState.nID = nAutoIncrease++;//对ID自动编号

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row][col-1];

newState.arrState[row][col-1] = temp;

newState.value = w(newState.arrState) + newState.depth;

//newState.value = f(newState);

//push newState to open

genToOpen(newState);

}

}

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

//把open表中已访问的state放到closed表中

void Eight::moveToClosed(state s)

{

int i = ++closedIndex;

closed[i] = s;

//delete from open table

for(int j = 0;j < openIndex-1; j++)

open[j]=open[j+1];

//open length-1

openIndex--;

}

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

//把扩展的状态放入open表中

void Eight::genToOpen(state s)

{

if(IsInOpen(s))

{

//show(s);

//cout<<"该状态已存在open表中!"<

nAutoIncrease--;

return;

}

if(IsInClosed(s))

{

//show(s);

//cout<<"该状态已存在closed表中!"<

nAutoIncrease--;

return;

}

int i = ++openIndex;

open[i] = s;

open[i].depth = s.depth;

open[i].parent = s.parent;

open[i].value = s.value;

}

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

// current state compare to goal state

bool Eight::compare(state s)

{

for(int i=0; i

for(int j=0; j

if(s.arrState[i][j] != goal[i][j])

return false;

return true;

}

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

// Is current state in closed table

bool Eight::IsInClosed(state s)

{

for(int k = 0; k <= closedIndex; k++)

{

if(closed[k] == s)

return true;

}

return false;

}

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

// Is current state in open table

bool Eight::IsInOpen(state s)

{

for(int k = 0; k <= openIndex; k++)

{

if(open[k] == s)

return true;

}

return false;

}

void Eight::heuristicSearch()

{

init();

state curState; //保存当前的状态

//cout<<"f0=="<

int n = 0;

while(openIndex != -1)

//while(n < 50000)

{

curState = open[0];

/*

for(int i = 0; i

{

cout<<"open[ "<

show(open[i]);

}

cout<<"------------------------------"<

*/

show(open[0]);

if(closedIndex >=M || openIndex >= M)

{

cout<<"宽度已达到极限"<

return;

}

if(compare(curState))

{

cout<<"已获得求解"<

return; //输出

}

moveToClosed(open[0]); //将该结点放入closed表中

genNewState(curState); //扩展结点并且将结点压入open表中

sortOpen(); //对新的open表排序

n++;

}

cout<<"深度达到极限"<

}

void Eight::findPath()

{

//int i;

sortOpen();

show(open[0]);

int nID = open[0].parent;

for(int i = closedIndex; i > -1; i--)

if(nID == closed[i].nID)

{

show(closed[i]); //输出

nID = closed[i].parent;

}

}

#include

using namespace std;

void main()

{

int goal[N][N] = {{8,0,3},

{2,1,4},

{7,6,5}};

Eight e(goal);

e.heuristicSearch();

e.findPath();

}

八.实验结果和分析

实验三:专家系统

一、实验目的

专家系统是人工智能的重要研究容和组成部分之一,本实验通过设计一个简单的专家系统,加深学生对专家系统的组成结构和构造原理的理解,并能转化为具体的应用。

二﹑问题描述

设计一个简单的专家系统,可根据属性的输入值自动识别事物的具体类别,容自拟。如一个动物专家系统可由以下11个属性组成,根据属性的对应值(Y或N),可判断动物的具体种类,运行结果如下图所示:

三、实验组织运行要求

本实验采用开放授课形式,每个同学独立完成上述实验要求。

四、实验条件

每人一台计算机独立完成实验。

五、源代码

#include

#include

using namespace std;

char *animal[]={"企鹅","海燕","鸵鸟","斑马","长颈鹿","虎","金钱豹"};

char *feature[]={"有毛","产奶","有羽毛","会飞","会下蛋","吃肉","有犬齿","有爪","眼睛盯前方","有蹄","反刍","黄褐色","有斑点","有黑色条纹","长脖","长腿","不会飞","会游泳","黑白两色","善飞","哺乳类","鸟类","肉食类","蹄类","企鹅","海燕","鸵鸟","斑马","长颈鹿","虎","金钱豹"};

typedef struct //存放规则的结构体

{

int relation[5];

int name;

}Rule;

相关文档