人工智能 八数码难题.doc

实 验 报 告
课程名称 人工智能_____________
实验项目 八数码难题______________
实验仪器 电脑 、visual C++_________
系 别 ____________
专 业 __ _____
班级/学号
学生姓名 _ _________
实验日期____
成 绩 _______________________
指导教师 _________
实验目的
理解并熟悉掌握深度优先搜索和广度优先搜索地方法。
实验内容
九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数
【算法分析】
    解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。
    这个问题也可以推广到流行的拼图游戏。
【具体步骤】
一、确定问题规模（考虑搜索的时间代价）
二、确定产生式规则（如果规则太多，则时间代价会很大）
三、套用经典宽度搜索框架写程序
三、代码和结果
#include <>
#include <>
typedef struct Node {
int num[9]; //棋盘状态
int deepth; //派生的深度 g(n)
int diffnum; //不在位的数目 h(n)
int value; //耗散值 f(n)=g(n)+h(n)
struct Node * pre;
struct Node * next;
struct Node * parent;
}numNode; /* ---------- end of struct numNode ---------- */
int origin[9]; //棋盘初始状态
int target[9]; //棋盘目标状态
int numNode_num,total_step;
numNode *open,*close; //Open表和Close表
numNode *create_numNode()
{
return (numNode *)malloc(sizeof(numNode));
}
numNode *open_getfirst(numNode *head); //返回第一项，并从Open表中删除
void open_insert(numNode *head,numNode *item); //向Open表中按序插入新节点
void close_append(numNode *head,numNode *item); //向Close表中插入新节点
int expand(numNode *item); //扩展节点
int print_result(numNode *item); //打印结果
numNode *copy_numNode(numNode *orgin);
char isNewNode(numNode *open,numNode *close,int num[9]);
//是否在Open表或Close表中
void print_num(int num[9]); //打印棋盘状态
int diff(int num[9]); //求不在位棋子的个数
void init(); //初始化，获得棋盘初始状态和目标状态
void swap(int *a,int *b);
int operate(int num[],int op);
void free_list(numNode *head);
/*
* === FUNCTION ======================================================================
* Name: 主函數
* Description: 程序入口
* ==========