人工智能大作业
人工智能大作业
班级:021351
姓名(学号):
2015年12月16号
题目一:搜索算法编程及实验报告
题目:八数码难题的求解
1.实验目的
问题描述:现有一个3*3的棋盘,其中有0-8一共9个数字,0表示空格,其他的数字可以和0交换位置(只能上下左右移动)。给定一个初始状态和一个目标状态,找出从初始状态到目标状态的最短路径的问题就称为八数码问题。
例如:实验问题为
到目标状态:
从初始状态:
要求编程解决这个问题,在盲目搜索和启发式搜索方法中分别选择一种方法来求解八数码难题。给出搜索树从初始节点到目标节点的路径。
2.实验设备及软件环境
利用计算机编程软件Visual C++ 6.0,用C语言编程解决该问题。
3.实验方法
法1:用启发式搜索中的有序搜索方法来解决该问题
(1).算法描述:
①.把初始节点S放到OPEN表中,计算()
f S,并把其值与节点S联系起
来。
②.如果OPEN表是个空表,则失败退出,无解。
③.从OPEN表中选择一个f值最小的节点。结果有几个节点合格,当其
中有一个为目标节点时,则选择此目标节点,否则就选择其中任一节点作为
节点i。
④.把节点i从OPEN表中移出,并把它放入CLOSED的扩展节点表中。
⑤.如果i是目标节点,则成功退出,求得一个解。
⑥.扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:
a.计算()
f j。
b.如果j既不在OPEN表中,也不在CLOSED表中,则用估价函数f把
它添加入OPEN表。从j加一指向其父辈节点i的指针,以便一旦找
到目标节点时记住一个解答路径。
c.如果j已在OPEN表或CLOSED表上,则比较刚刚对j计算过的f值
和前面计算过的该节点在表中的f值。如果新的f值较小,则
I.以此新值取代旧值。
II.从j指向i,而不是指向它的父辈节点。
III.如果节点j在CLOSED表中,则把它移回OPEN表。
⑦转向②,即GO TO ②。
(2).流程图描述:
(3).程序源代码:
#include
#include
struct node{
int number[3][3];//用二维数组存放8数码
int W;//W表示与目标状态相比错放的数码数
int Depth;//记录当前节点的深度
struct node *parent;//指向父节点的指针
struct node *next;//指向链表中下一个节点的指针};
int CounterW(int Number[3][3])
{//函数说明:计算当前状态与目标状态的W值
int i,j;
int W=0;
int Desnode[3][3]={1,2,3,8,0,4,7,6,5};
for(i=0; i<3; i++)
for(j=0; j<3; j++)
if(Number[i][j] != Desnode[i][j])
W++;
return W;
}
void PrintNode(node *A)
{
int i,j;
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
printf("%d ",A->number[i][j]);
printf("\n");
}
printf("\n");
}
int CheckNode(node *open, node *close, int a[3][3]) {//检验该节点状态是否出现过的子程序
int CheckFlag=0;
int flag1,flag2;
node *p=open;
node *q=close;
while(p != NULL)
{
flag1=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
if(a[i][j]==p->number[i][j])
flag1++;
}
if(flag1 == 9)
break;
else
p=p->next;
}
while(q != NULL)
{
flag2=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
if(a[i][j] == q->number[i][j])
flag2++;
}
if(flag2 == 9)
break;
else
q=q->next;
}
if((flag1==9) || (flag2==9))
CheckFlag=1;//如果出现过,置标志位为1
return CheckFlag;
}
struct node *FindNextNode(node *Prenode, node *open, node *close) { //扩展Prenode指向的节点,并将扩展所得结点组成一条单链表int i,j,m,n; //循环变量
int temp; //临时替换变量
int flag=0;
int a[3][3];//临时存放二维数组
struct node *p, *q, *head;
head=(node *)malloc(sizeof(node));//head指向该链表首结点,并且作为返回值
p=head;
q=head;
head->next=NULL;//初始化
for(i=0;i<3;i++)//找到二维数组中0的位置
{
for(j=0;j<3;j++)
if(Prenode->number[i][j]==0)
{
flag=1;
break;
}
if(flag==1)
break;
}
//根据0的位置的不同,对a进行相应的变换
for(m=0;m<3;m++)//将Prenode->number赋给a
for(n=0;n<3;n++)
a[m][n]=Prenode->number[m][n];
if(i+1<=2)//情况1,0向下移
{
temp=a[i][j]; a[i][j]=a[i+1][j]; a[i+1][j]=temp;
int CheckNum=CheckNode(open, close, a);
if(CheckNum == 0)//若该结点未出现过则执行下面的操作
{
q=(node *)malloc(sizeof(node));
for(m=0;m<3;m++)//将a赋给扩展节点q->number for(n=0;n<3;n++)
q->number[m][n]=a[m][n];
PrintNode(q);
q->parent=Prenode;
q->Depth=q->parent->Depth+1;//子结点的深度等于其父结点深度加1
q->W=CounterW(q->number);
q->next=NULL;
p->next=q;//扩展节点插入head链表
p=p->next;
}
}
for(m=0;m<3;m++)//将Prenode->number重新赋给a
for(n=0;n<3;n++)
a[m][n]=Prenode->number[m][n];
if(i-1>=0)//情况2,0向上移
{
temp=a[i][j]; a[i][j]=a[i-1][j]; a[i-1][j]=temp;
int CheckNum=CheckNode(open, close, a);
if(CheckNum == 0)//若该结点未出现过则执行下面的操作
{
q=(node *)malloc(sizeof(node));
for(m=0;m<3;m++)//将a赋给q->number
for(n=0;n<3;n++)
q->number[m][n]=a[m][n];
PrintNode(q);
q->parent=Prenode;
q->Depth=q->parent->Depth+1;
q->W=CounterW(q->number);
q->next=NULL;
p->next=q;
p=p->next;
}
}
for(m=0; m<3; m++)
for(n=0; n<3; n++)
a[m][n]=Prenode->number[m][n];
if(j-1>=0)//情况3,0向左移
{
temp=a[i][j]; a[i][j]=a[i][j-1]; a[i][j-1]=temp;
int CheckNum=CheckNode(open, close, a);
if(CheckNum == 0)//若该结点未出现过则执行下面的操作
{
q=(node *)malloc(sizeof(node));
for(m=0; m<3; m++)//将a赋给q->number
for(n=0; n<3; n++)
q->number[m][n]=a[m][n];
PrintNode(q);
q->parent=Prenode;
q->Depth=q->parent->Depth+1;
q->W=CounterW(q->number);
q->next=NULL;
p->next=q;
p=p->next;
}
}
for(m=0;m<3;m++)
for(n=0;n<3;n++)
a[m][n]=Prenode->number[m][n];
if(j+1<=2)//情况4,0向右移
{
temp=a[i][j]; a[i][j]=a[i][j+1]; a[i][j+1]=temp;
int CheckNum=CheckNode(open, close, a);
if(CheckNum == 0)//若该结点未出现过则执行下面的操作
{
q=(node *)malloc(sizeof(node));
for(m=0; m<3; m++)//将a赋给q->number
for(n=0; n<3; n++)
q->number[m][n]=a[m][n];
PrintNode(q);
q->parent=Prenode;
q->Depth=q->parent->Depth+1;
q->W=CounterW(q->number);
q->next=NULL;
p->next=q;
p=p->next;
}
}
head=head->next;
return head;
}
node *insert(node *open,node *head)
{ //将head链表的结点依次插入到open链表相应的位置,
//使open表中的结点按从小到大排序。函数返回open指针node *p,*q;//p、q均指向open表中的结点,p指向q所指的前一个结点
int flag=0;
if((open==NULL) && (head != NULL))//初始状态,open表为空
{ //首先将head表第一个结点直接放入open表中
open=head;
q=head;
head=head->next;
q->next=NULL;
}
if((open != NULL) && (open->next==NULL) &&(head != NULL))
{//open表中只有一个元素
q=open;
if((head->W + head->Depth) < (open->W + open->Depth))
//若后一结点的f值小于首结点,则将它插入到首结点位置
{
open=head;
head=head->next;
open->next=q;
}
else//或者第二个结点的位置
{
q->next=head;
head=head->next;
q=q->next;
q->next=NULL;
}
p=open;
}
while(head!=NULL)
{
q=open;
if((head->W + head->Depth) < (open->W + open->Depth))
{ //插入到表头
open=head;
head=head->next;
open->next=q;
continue;
}
else
{
q=q->next; p=open;
} //否则,q指像第二个结点,p指向q前一个结点
while(q->next!=NULL) //将head的一个结点插入到链表中(非表尾的位置)
{
if(q->W < head->W)
{
q=q->next;
p=p->next;
}
else
{
p->next=head;
head=head->next;
p->next->next=q;
break;
}
}
if(q->next==NULL)//将head的一个结点插入到表尾或倒数第二个位置
{
if((q->W + q->Depth) < (head->W + head->Depth))
{
q->next=head;
head=head->next;
q->next->next=NULL;
}
else
{
p->next=head;
head=head->next;
p->next->next=q;
}
}
}
return open;
}
void main()
{
int i,j;
int key=0;
node FirstNode;
node *open, *close;
node *p, *r;
node *NodeList;
printf("请输入初始状态的8数码(按每行从左往右依次输入,用0表示空格):\n");
for(i=0; i<3; i++)
for(j=0; j<3; j++)
scanf("%d",&FirstNode.number[i][j]);
printf("\n");
printf("搜索树为:\n");
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
printf("%d ",FirstNode.number[i][j]);
printf("\n");
}
printf("\n");
FirstNode.parent=(node *)malloc(sizeof(node));
FirstNode.Depth=0;//开始结点深度为零
FirstNode.W=CounterW(FirstNode.number);
open=&FirstNode;
p=&FirstNode;
if(open->W == 0)//该结点的状态与目标结点相同
{
printf("该结点已为目标结点状态!\n");
return;
}
r=&FirstNode;
close=&FirstNode;
r->next=NULL;
open=NULL;
NodeList=FindNextNode(r,open,close);//NodeList指向新扩展出来的链表
open=insert(open,NodeList);//将扩展出来的结点插入到open表中
{
r->next=open;//将open表的第一个元素加到close表,r始终指向close表的最后一个元素
open=open->next;
r=r->next;
r->next=NULL;
if(r->W == 0)
{
key=1;
printf("\n启发式搜索成功!\n");
break;
}
NodeList=FindNextNode(r,open,close);;//对close表最后一个结点进行扩展,扩展得到的链表接到head表
open=insert(open,NodeList);//将扩展的结点按顺序插入到open表中
}
if(key == 1)
{
p=close;
printf("最优搜索过程如下:\n");
printf("结点深度为:%d\n",FirstNode.Depth);
printf("-------------\n");
while(p!=NULL)
{
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
printf("%d ",p->number[i][j]);
printf("\n");
}
printf("\n");
p=p->next;
printf("结点深度为:%d\n",p->Depth);
printf("-------------\n");
}
} else
printf("查找失败,该问题无解!\n");
}
法2:用盲目搜索中的宽度优先搜索法解决该问题
⑴.算法描述:
放入OPEN表;
①.把初始节点S
②.如果OPEN表为空,则问题无解,退出;否则继续。
③.把OPEN表的第一个节点(记为n)取出放入CLOSE表;
④.扩展节点n。如果没有后继节点,则转向上述第②步。
⑤.把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。
⑥.如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第②步。
⑵.流程图:
⑶.程序源代码:
#include
#include
#define TIME 50 //限定只搜索前50步,50步以后如果仍然没有搜索到结果,认为无解。
#define MAXSIZE 200
int n = 1, i,j, k;
int result[9] = { 1, 2, 3, 8, 0, 4, 7, 6, 5 };//所要达到的最终状态,0代表空格。
typedef struct{
int num[9];
char expension; //记录是否可以扩展,Y代表可以扩展,N代表不可以。
char banOperate; //表示不可以执行的操作,'L'代表不能左移,'R'代表不能右移,
//'U'代表不能上移,'D'代表不能下移,'C'代表可以任意移动。
int father; //记录父节点的下标。
}Node;
Node store[MAXSIZE]; //将搜索过的状态存储于该数组中。
int same(int temp) //判断是否达到了目标状态。
{
for (j = 0; j<9; j++)
if (store[temp].num[j] != result[j])
return 0;
return 1;
}
void printResult() //输出搜索结果。
{
for (j = 1; j <= n; j++)
{
printf("第%d步搜索后:\n", j);
printf("\t%d\t%d\t%d\n", store[j].num[0], store[j].num[1], store[j].num[2]);
printf("\t%d\t%d\t%d\n", store[j].num[3], store[j].num[4], store[j].num[5]);
printf("\t%d\t%d\t%d\n", store[j].num[6], store[j].num[7], store[j].num[8]);
printf("\n\n");
}
}
int left(int temp) //将空格进行左移操作。
{
for (j = 0; j<9; j++) //判断空格的位置。
if (store[temp].num[j] == 0)
break;
if (j == 0 || j == 3 || j == 6)
return 0;
for (k = 0; k<9; k++)
store[n].num[k] = store[temp].num[k];
int tempNum = store[n].num[j - 1]; //将移动后的状态赋给
store[n]
store[n].num[j - 1] = 0;
store[n].num[j] = tempNum;
store[temp].expension = 'N';
store[n].banOperate = 'R';
store[n].expension = 'Y';
store[n].father = temp;
if (same(n)) //判断store[n]是否为最终想得到的状态。
{
printResult();
exit(1);
}
n++;
return 1;
}
int right(int temp) //将空格进行右移操作。{
for (j = 0; j<9; j++)
if (store[temp].num[j] == 0)
break;
if (j == 2 || j == 5 || j == 8)
return 0;
for (k = 0; k<9; k++)
store[n].num[k] = store[temp].num[k];
int tempNum = store[n].num[j + 1];
store[n].num[j + 1] = 0;
store[n].num[j] = tempNum;
store[temp].expension = 'N';
store[n].banOperate = 'L';
store[n].expension = 'Y';
store[n].father = temp;
if (same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
int up(int temp) //将空格进行上移操作。{
for (j = 0; j<9; j++)
if (store[temp].num[j] == 0)
break;
if (j == 0 || j == 1 || j == 2)
return 0;
for (k = 0; k<9; k++)
store[n].num[k] = store[temp].num[k];
int tempNum = store[n].num[j - 3];
store[n].num[j - 3] = 0;
store[n].num[j] = tempNum;
store[temp].expension = 'N';
store[n].banOperate = 'D';
store[n].expension = 'Y';
store[n].father = temp;
if (same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
int down(int temp) //将空格进行下移操作。{
for (j = 0; j<9; j++)
if (store[temp].num[j] == 0)
break;
if (j == 6 || j == 7 || j == 8)
return 0;
for (k = 0; k<9; k++)
store[n].num[k] = store[temp].num[k];
int tempNum = store[n].num[j + 3];
store[n].num[j + 3] = 0;
store[n].num[j] = tempNum;
store[temp].expension = 'N';
store[n].banOperate = 'U';
store[n].expension = 'Y';
store[n].father = temp;
if (same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
void init()
{
Node start;
printf("请输入初始状态,用空格分开,0代表空格:\n");//输入初始的状态。
for (i = 0; i<9; i++)
scanf("%d", &start.num[i]);
for (k = 0; k<9; k++)
if (start.num[k] == 0)
break;
start.banOperate = 'C';
start.expension = 'Y';
start.father = -1;
store[0] = start; //将初始状态赋于store[0]。
}
void main(){
init();
if (same(0))
{
printf("没有必要进行搜索,初始状态即为最终状态!");
exit(1);
}
for (i = 0; i