大连理工大学远程与继续教育学院《人工智能》课程设计
五、对于重排九宫问题的启发式函数
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：
8 1 2 4 3 7 6 5
1 2 3 8 4 7 6 5
初始格局 目标状态
#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)
奥鹏大连理工大学远程与继续教育学院《人工智能》课程设计
