人工智能 圆盘问题 免费.doc

实 验 报 告

课程名称 人工智能
实验项目 圆盘问题
实验仪器 PC

系 别______ ______
专 业_______ _________
班级/学号
学生姓名 _______
实验日期 ______ _
成 绩 _______________________

一、 实验目的
理解并熟悉掌握深度优先搜索和广度优先搜索地方法。

二、 实验内容
设有3个大小不等的圆盘A,B,C套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立的绕轴做逆时针转动，每次转动90度，初始状态S0和目标状态Sg，用深度优先搜索和广度优先搜索求从S0到Sg的路径。

三、代码和结果

//*******************************************************************
//圆盘转动问题：有三个圆盘，每个可独自逆时针转动，每次转动°
//*******************************************************************

#include <malloc.h>
#include "stdio.h"

typedef struct TNode
{
__int64 data;
TNode* LChild;
TNode* RChild;
}node;

//把所以状态列出来，以右边为基准，则初态为，终态为
__int64 Node[64]={123412341234,123412344123,123412343412,123412342341,
123441231234,123441234123,123441233412,123441232341,
123434121234,123434124123,123434123412,123434122341,
123423411234,123423414123,123423413412,123423412341,
341212341234,341212344123,341212343412,341212342341,
341241231234,341241234123,341241233412,341241232341,
341234121234,341234124123,341234123412,341234122341,
341223411234,341223414123,341223413412,341223412341,
412312341234,412312344123,412312343412,412312342341,
412341231234,412341234123,412341233412,412341232341,
412334121234,412334124123,412334123412,412334122341,
412323411234,412323414123,412323413412,412323412341,
234112341234,234112344123,234112343412,234112342341,
234141231234,234141234123,234141233412,234141232341,
234134121234,234134124123,234134123412,234134122341,
234123411234,234123414123,234123413412,234123412341};

//在空二叉树或二叉树中插入一个新的结点
node* Insert(node* root,__int64 value)
{
node* current;
node* parent;
node* new_node;
new_node=(node*)malloc(sizeof(node));
new_node->data=value;
new_node->LChild=NULL;
new_node->RChild=NULL;
if(root==NULL)
{
return new_node;
}
else
{
current=root;
while(current!=NULL)
{
parent=current;
if(current->data >value)
current=current->LChild;
else
current=current->RChild;
}
if(parent->data>value)
parent->LChild=new_node;
else
parent->RChild=new_node;
}
return root;
}

//创建一棵新二叉树
node* Create(__int64* data,int len)
{
node* root=NULL;
int i;
for(i=0;i<len;i++)
root=Insert(root,data[i]);
return root;
}

//深度优先搜索
void PreOrder(node* root)
{
if(root!=NULL&&root->data!=412312342341)
{
printf( "%I64u--->",root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}

//广度优先搜索
void Level(node* root)
{

const int maxsize=64;
node* Queen[maxsize];
node* current=NULL;
int rear=0;
int fore=0;

if(root!=NULL)
{
rear=(rear+1)%maxsize;
Queen[rear]=root;
}
while(fore!=rear)
{
fore=(fore+1)%maxsize;
current=Queen[fore];
printf( "%I64u--->",current->data);
if(current->LChild!=NULL&&current->data!=412312342341)//出列结点的左孩子不为空且没搜索到终态节点，则入列
{
rear=(rear+1)%maxsize;
Queen[rear]=current->LChild;
}
if(current->RChild!=NULL&&current->data!=412312342341)//出列结点的右孩子不为空且没搜索到终态节点，则入列
{
rear=(rear+1)%maxsize;
Queen[rear]=current->RChild;
}
}
}

int main(int argc, char* argv[])
{
node* root=NULL;
root=Create(Node,64);
printf("深度优先搜索：\n");
PreOrder(root);
printf("412312342341");
printf("\n广度优先搜索：\n");
Level(root);
printf("412312342341\n");
return 0;
}
实验心得：
对人工智能编程有了初步的了解。