人工智能实验报告_八数码问题(7800字)

来源:m.ttfanwen.com时间:2016.12.6

实验一 启发式搜索算法

姓名:尹鹏飞 学号:S201407031 日期:2014/10/22

一、实验目的:

熟练掌握启发式搜索A?算法及其可采纳性。

二、实验内容:

使用启发式搜索算法求解8数码问题

编制程序实现求解8数码问题A?算法,采用估价函数

??w?n?, f?n??d?n?????p?n?

其中:d?n?是搜索树中结点n的深度;w?n?为结点n的数据库中错放的棋子个数;p?n?为结点n的数据库中每个棋子与其目标位置之间的距离总和。

本实验采用d(n)+p?n? 作为启发式函数.

三、实验原理:

1. 问题描述:

八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。

要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2. 原理描述:

2.1 有序搜索算法:

(1)原理:

在搜索过程中,OPEN表中节点按照其估价函数值以递增顺序排列,选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点,这种搜索方法称为有序搜索。

在本例中,估价函数中的g(n)取错放的棋子个数d(n),h(n)为节点n的状态与目标状态之间错放的个数,即函数p?n?。

(2)算法描述:

① 把起始节点S放到OPEN表中,并计算节点S的f(S);

② 如果OPEN是空表,则失败退出,无解;

③ 从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i;

④ 把节点i从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中;

⑤ 如果i是个目标节点,则成功退出,求得一个解;

⑥ 扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:

计算f(j);如果j 既不在OPEN表中,又不在CLOCED表中,则用估价函数f把 它添入OPEN表中。从j加一指向其父节点i的指针,以便一旦找到目标节点时记住一个解答路径;如果j已在OPEN表或CLOSED表中,则比较刚刚对j计算过的f和前面计算过的该节点在表中的f值。如果新的f较小,则

(I)以此新值取代旧值。

(II)从j指向i,而不是指向他的父节点。

(III)如果节点j在CLOSED表中,则把它移回OPEN表中。

⑦ 转向②,即GOTO②。

(3)算法流程图:

2.2启发式搜索技术

(1)原理

人工智能实验报告八数码问题

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,

再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

(2)估价函数

计算一个节点的估价函数,可以分成两个部分:

1、 已经付出的代价(起始节点到当前节点);

2、 将要付出的代价(当前节点到目标节点)。

节点n的估价函数f(n)定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值,即f*(n) = g*(n)+ h*(n)。

g*(n)是从初始节点到达当前节点n的实际代价;

h*(n)是从节点n到目标节点的最佳路径的估计代价,体现出搜索过程中采用的启发式信息(背景知识),称之为启发函数。

g*(n)所占的比重越大,越趋向于宽度优先或等代价搜索;反之,h*(n)的比重越大,表示启发性能就越强。

本实验中我们使用函数p(n),其值是节点n与目标状态节点相比较,每个错位棋牌在假设不受阻拦的情况下,移动到目标状态相应位置所需走步(移动次数)的总和。显然p(n)比?(n)更接近于h*(n),因为p(n)不仅考虑了错位因素,还考虑了错位的距离。

(3)算法描述:

参考有序搜索算法描述,基本相同。流程图亦参考有序算法流程图。

四、实验程序及其说明:

程序开发语言采用C#和面向对象的设计思想,设计的类内容如下: 类视图

人工智能实验报告八数码问题

SplashForm用来显示启动界面;

MainForm 用来显示数据设置界面;

ShowForm 用来显示结果界面;

Number用来记录每个节点当前的状态和权值;

属性: private int[] num;//保存当前输入的八数码状态

private int w, p;//分别记录当前的八数码搜索深度和不在位棋子数

private Number next;//指向下一个节点

private Number parent;//指向父节点

private int index;//定义当前0所在的位置

方法: //复写父类比较方法

public override bool Equals(Object num)

//两个对象的比较方法

public bool CompareLow(Number num)

NumberUtil类,工具类,对八数码的各种状态进行控制管理

private Queue numQueue;//八数码队列,保存open表

private int[] soure;//初始状态

private int[] target;//目标状态

private Number result;//结果集

方法:

public bool Control(Number num)//控制策略

public bool Calculate() //计算结果

Queue 用来作为程序的open表,扩展节点

private Number head;//定义队列的头

private ArrayList listClose;//close表保存所有出现的状态表

//添加新的元素,并按照A*算法的计算值递增排序

public void addNumber(Number num)

//出队一个元素 public Number equeue()

五、实验小结

通过本次试验,我对启发式搜索有了更加深入的了解。

在实验中,通过对两种启发式搜索所扩在的节点数来看,p(n)看来比?(n)更加有效,能在复杂情况下求得更加优质的解,避免不必要的节点的扩展。但是对于估价函数h*(n)来说,它的定义趋向多元化,p(n)只是它的一个比较好的特例,对一复杂的搜索问题,如国际象棋问题,他就显得较简单。所以,要更好地定义一个估价函数还有待深入讨论。

在寻找最佳扩展路径的过程中我发现,最佳扩展路基上的节点均在CLOSED表中,利用标志flag,以及它们之间的父子关系,我很容易的就找到了扩展路径,避免了再用一个路径指针path来找到路径,这样节省了存储空间,更利于搜索。

通过实验结果来看,这两个函数都是可采纳的,尽管?(n)存在不必要的扩展。

六、实验代码及输出结果

1. 源代码:

class Queue

{

private Number head;//定义队列的头

private ArrayList listClose;//close表保存所有出现的状态表

public Queue() {

listClose = new ArrayList();

head = new Number();

head.Next = null;

}

internal Number Head

{

get { return head; }

set { head = value; }

}

private int count = 0;//队列中的元素

public int Count

{

get { return count; }

set { count = value; }

}

public void show() {

Number n = head.Next;

while(n!=null){

Console.WriteLine(n.ToString());

n = n.Next;

}

}

//添加新的元素,并按照A*算法的计算值递增排序

public void addNumber(Number num) {

//如果该状态已出现则不再加入其中

if(listClose.IndexOf(num)>=0){

Console.WriteLine(listClose.IndexOf(num)+"-------");

return;

}

listClose.Add(num);

Number n = head.Next;//获取头元素

Number front = head;//前节点

if (n == null) head.Next = num;

else {

for (;n!=null;n=n.Next)//遍历所有元素

{

//采用头插法将数据插入后面

if(num.CompareLow(n)){//如果num比当前对象小,则直接插入前面 num.Next = n;

front.Next = num;//插入成功

count++;//增加当前的节点数目

return;

}

front = n;

}

}

front.Next = num;//直接插入尾部

count++;//增加当前的节点数目

}

//出队列

public Number equeue()

{

if(count ==0)

return null;

Number n = head.Next;

head.Next = head.Next.Next;

count--;

return n;

}

}

}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace AICode

{

class NumberUtil

{

private Queue numQueue;//八数码队列,保存open表

private int[] soure;//初始状态

public int[] Soure

{

get { return soure; }

set { soure = value; }

}

private int[] target;//目标状态

public int[] Target

{

get { return target; }

set { target = value; }

}

private Number result;//结果集

internal Number Result

{

get { return result; }

set { result = value; }

}

private int index;//当前的0所在数组中的下标

public int Index

{

get { return index; }

set { index = value; }

}

public NumberUtil() {

numQueue = new Queue();//

}

//获取结果栈对象

public Stack<Number> getResult()

{

Stack<Number> s = new Stack<Number>(); if (result != null)

{

for (Number n = result; n != null; n = n.Parent) {

s.Push(n);

}

}

return s;

}

//对A,B两个数组进行比较

public bool compareArray(int[] a,int[] b) {

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

{

if (a[i] != b[i]) return false;

}

return true;

}

//A*算法策略

public void A(Number n,int[] t) {

int countP = 0;

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

{

int temp = n.Num[i];

if (n.Num[i] != t[i]) {

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

{

if(t[j]==temp){

int r = Math.Abs(j%3 - i%3); int c = Math.Abs(j/3 - i/3); countP+= r+c;

}

}

}

}

n.P = countP;

}

public bool Calculate() { //计算结果

//首先将首元素添加到队列中

Number n = new Number();

n.Index = index;

n.Num = (int[])soure.Clone();

A(n,target);//计算权值

n.D = 1;

numQueue.addNumber(n);

int MAXCount = 0;

while(numQueue.Count>0){

//从队首出对一个元素

Number num = numQueue.equeue(); if (!Control(num)) { return true; }; // numQueue.show();

// Console.WriteLine("============"); MAXCount++;

if (MAXCount>10000)

{

return false;

}

}

return false;

}

public bool Control(Number num)//控制策略 { //开始利用A*算法进行结果的搜索

int index = num.Index;//获取当前0所在的数组位置

int row, col; //行和列

col = index % 3;//表示在二维数组中的行数

row = index / 3;//表示二维数组中的列

//每个八数码有四种空间状态

//(1)

if(row-1>=0){

Number n = new Number();

//获取数组的副本

int[] s =(int[])num.Num.Clone();

int i=(row-1)*3+col;

int temp = s[i]; s[i] = s[index]; s[index] = temp;

//设置对象的值 \

n.D = num.D+1;

n.Num = s;

n.Index = i;

n.Parent = num;//添加对象的父节点

A(n, target);//计算权值

//将对象添加到队列中,如果找到对象了,则返回

if (compareArray(n.Num,target)) { this.result = n; return false; } numQueue.addNumber(n);

}

if(row+1<=2){

Number n = new Number();

//获取数组的副本

int[] s = (int[])num.Num.Clone();

int i = (row + 1) * 3 + col;

int temp = s[i]; s[i] = s[index]; s[index] = temp;

//设置对象的值

n.D = num.D + 1;

n.Num = s;

n.Parent = num;//添加对象的父节点

n.Index = i;

A(n, target);//计算权值

//将对象添加到队列中

if (compareArray(n.Num, target)) { this.result = n; return false; } numQueue.addNumber(n);

}

if(col-1>=0){

Number n = new Number();

//获取数组的副本

int[] s = (int[])num.Num.Clone();

int i = row * 3 + col-1;

int temp = s[i]; s[i] = s[index]; s[index] = temp;

//设置对象的值

n.D = num.D + 1;

n.Num = s;

n.Index = i;

n.Parent = num;//添加对象的父节点

A(n, target);//计算权值

//将对象添加到队列中

if (compareArray(n.Num, target)) { this.result = n; return false; } numQueue.addNumber(n);

}

if(col+1<=2){

Number n = new Number();

//获取数组的副本

int[] s = (int[])num.Num.Clone();

int i = row * 3 + col +1;

int temp = s[i]; s[i] = s[index]; s[index] = temp;

//设置对象的值

n.D = num.D + 1;

n.Num = s;

n.Index = i;

n.Parent = num;//添加对象的父节点

A(n, target);//计算权值

//将对象添加到队列中

if (compareArray(n.Num, target)) { this.result = n; return false; } numQueue.addNumber(n);

}

return true;

}

}

}

2. 输出结果:

人工智能实验报告八数码问题

人工智能实验报告八数码问题

人工智能实验报告八数码问题

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