奥鹏大连理工大学远程与继续教育学院《人工智能》课程设计

大连理工大学远程与继续教育学院《人工智能》课程设计

五、对于重排九宫问题的启发式函数

给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：

8 1 2 4 3 7 6 5

1 2 3 8 4 7 6 5

初始格局 目标状态

#include \#include #include #include #include

static int target[9]={1,2,3,8,0,4,7,6,5}; //class definition class eight_num {

private:

int num[9];

int not_in_position_num; int deapth;

int eva_function;

大连理工大学远程与继续教育学院《人工智能》课程设计

public:

eight_num* parent; eight_num* leaf_next; eight_num* leaf_pre;

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) {

num[0]=num1; num[1]=num2; num[2]=num3; num[3]=num4; num[4]=num5; num[5]=num6; num[6]=num7; num[7]=num8; num[8]=num9; }

eight_num(void) {

for (int i=0;i<9;i++) num[i]=i; }

void cul_para(void);

void get_numbers_to(int other_num[9]); int get_nipn(void)

{return not_in_position_num;} int get_deapth(void) {return deapth;} int get_evafun(void) {return eva_function;}

void set_num(int other_num[9]); void show(void);

eight_num& operator=(eight_num&);

eight_num& operator=(int other_num[9]); int operator==(eight_num&);

int operator==(int other_num[9]); };

//计算启发函数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; }

//构造函数1

eight_num::eight_num(int init_num[9]) {

for (int i=0;i<9;i++) num[i]=init_num[i]; }

//显示当前节点的状态 void eight_num::show() {

cout<

//复制当前节点状态到一个另数组中

void eight_num::get_numbers_to(int other_num[9]) {

for (int i=0;i<9;i++) other_num[i]=num[i]; }

大连理工大学远程与继续教育学院《人工智能》课程设计

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

for (int i=0;i<9;i++) num[i]=other_num[i]; }

eight_num& eight_num::operator=(eight_num& another_8num) {

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

num[i]=another_8num.num[i];

not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1;

eva_function=not_in_position_num+deapth; return *this; }

eight_num& eight_num::operator=(int other_num[9]) {

for (int i=0;i<9;i++) num[i]=other_num[i]; return *this; }

int eight_num::operator==(eight_num& another_8num) {

int match=1;

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

if(num[i]!=another_8num.num[i]) {

match=0; break; }

if (match==0) return 0; else

return 1; }

int eight_num::operator==(int other_num[9]) {

int match=1;

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

if(num[i]!=other_num[i]) {

match=0; break;

大连理工大学远程与继续教育学院《人工智能》课程设计

}

if (match==0) return 0; else

return 1; }

//class definition over //空格向上移

int move_up(int num[9]) {

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; } }

//空格向下移

int move_down(int num[9]) {

for (int i=0;i<9;i++) if (num[i]==0) break; if (i>5)

return 0; else {

num[i]=num[i+3]; num[i+3]=0; return 1; } }

//空格向左移

int move_left(int num[9]) {

for (int i=0;i<9;i++) if (num[i]==0) break;

if (i==0||i==3||i==6)