8数码问题

入到open表中；

⑤把当前结点从open表中移除；

End while

End if 输出结果；

End

算法流程如下： 开始 读入棋局初始状态 否 是否可解 是 初始状态加入open表 在 open表中找到评价值最小的节点，作为当前结点 是 是目标节点 否 扩展新状态，把不重复的新状态加入open表中 当前结点从open表移除 输出结果 结束

3.使用的软件以及编程语言

实验环境：硬件环境：PC机。

软件环境：Windows 7 ;VC++ 6.0。

编程语言：C++语言。

4.实验结果

系统输入以及运行结果如下：

(1)初始状态是2 8 3 1 0 4 7 6 5，用h作为启发函数结果都如下：

(2)初始状态是2 0 3 1 8 4 7 6 5，用h作为启发函数结果都如下：

5.部分重要源程序

static int target[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态

class eight_num { private:

int num[9]; 定义八数码的初始状态

int not_in_position_num; 定义不在正确位置八数码的个数 int deapth; 定义了搜索的深度

int eva_function; 评价函数的值，每次选取最小的进行扩展

public: 数

eight_num(int init_num[9]);

eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){} eight_num(void){ } 计算启发函数g(n)的值

void eight_num::cul_para(void){} 显示当前节点的状态 void eight_num::show(){} 复制当前节点状态到一个另数组中

void eight_num::get_numbers_to(int other_num[9]){} 设置当前节点状态(欲设置的状态记录的other数组中) void eight_num::set_num(int other_num[9]){}

eight_num& eight_num::operator=(eight_num& another_8num){} eight_num& eight_num::operator=(int other_num[9]){} int eight_num::operator==(eight_num& another_8num){} int eight_num::operator==(int other_num[9]){} 空格向上移

eight_num* parent; 指向节点的父节点 eight_num* leaf_next; 指向open表的下一个节点

eight_num* leaf_pre; 指向open 表的前一个节点初始状态的构造函

int move_up(int num[9]){} 空格向下移

int move_down(int num[9]){} 空格向左移

int move_left(int num[9]){} 空格向右移

int move_right(int num[9]){} 判断可否解出

int icansolve(int num[9],int target[9]){} 判断有无重复

int existed(int num[9],eight_num *where){} 寻找估价函数最小的叶子节点

eight_num* find_OK_leaf(eight_num* start){} }

//计算启发函数g(n)的值 void eight_num::cul_para(void) { }

int i;

int temp_nipn=0; for (i=0;i<9;i++)

if (num[i]!=target[i])

temp_nipn++;

not_in_position_num=temp_nipn; if (this->parent==NULL)

deapth=0;

else

deapth=this->parent->deapth+1;

eva_function=not_in_position_num+deapth;

//空格向上移

int move_up(int num[9]) { }

//寻找估价函数最小的叶子节点

eight_num* find_OK_leaf(eight_num* start) { }

eight_num *p,*OK; p=OK=start;

int min=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next)

if(min>p->get_evafun()) { }

OK=p;

min=p->get_evafun();

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

if (num[i]==0)

break;

if (i<3)

return 0;

else { }

num[i]=num[i-3]; num[i-3]=0; return 1;

return OK;