eight_code2dlg.cpp

輸入起始和目標狀態,計算出其搜索的各種属性

		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);// 向上移动
          temp_i.array[2][2]=temp_i.array[1][2];
          temp_i.array[1][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
	    	handle(temp_i);
		  break;
		  }
}
//--------------------------------------------------------------------------------------------

void CEight_COde2Dlg::deal_with()
{
	GetLocalTime( &star );                              
	Node temp;
	while(open_null()==false){//判断open表是否为空，不为空则继续循环
			get_min_open(temp,positioninopen);//获得open表中f最小结点		
			if(compare(temp,endnode)==true){//判断是否为终结点
			    GetLocalTime( &finish );
               // roadlen=step_num;
			    break;
			}
			open[positioninopen]=-1;//将结点从open表中删除
			close[closelen]=temp.selfposition;//将结点加入close表
    		closelen++;
			expend(temp,endnode);//扩展结点
	       	//Sleep(10);
	}
}
//--------------------------------------------------------------------------------------------

void CEight_COde2Dlg::print_state(int positioninnode)
{
      //int temp;
	  //temp=open[positioninopen];
	  m_midd_edit0=nodearray[0].array[0][0];
	  m_midd_edit1=nodearray[0].array[0][1];
      m_midd_edit2=nodearray[0].array[0][2];
	  m_midd_edit3=nodearray[0].array[1][0];
	  m_midd_edit4=nodearray[0].array[1][1];
	  m_midd_edit5=nodearray[0].array[1][2];
      m_midd_edit6=nodearray[0].array[2][0];
	  m_midd_edit7=nodearray[0].array[2][1];
	  m_midd_edit8=nodearray[0].array[2][2];
}
//--------------------------------------------------------------------------------------------
/*单击开始按钮，程序开始执行*/
void CEight_COde2Dlg::OnBegin() 
{	
	
	UpdateData(TRUE);
	initializestate();
    //输入数据合法性检测
	if(!((checkerr(nodearray[0]) )&&( checkerr(endnode)) ) ){
		AfxMessageBox("输入错误！");
        OnClearButton();
		return;
	}
	//判断能否找出解路径
    if(!judgement(nodearray[0],endnode)) {		
		AfxMessageBox("无法到达目标状态！");
        OnClearButton();
		return;
	}
	
	deal_with();                //进入扩展函数
	print_state(positioninopen);//单步输出中间节点
	saveroad(positioninopen);   //存储了关键路径
    print_runtime();            //输入运行时间
	print_NodeNum();            //输入扩展节点的数目
	print_AvgNode();            //输入平均分枝因子
	print_road_len();
	UpdateData(FALSE);	
}
//--------------------------------------------------------------------------------------------
 /*当选择h(n)=W(n)作为启发函数时*/
void CEight_COde2Dlg::On_Wn() 
{
	UpdateData(TRUE);
	flag=0;
	m_wn=0;
    m_pn=1;
	m_wf=1;
	UpdateData(FALSE);
}
//--------------------------------------------------------------------------------------------
/*当选择h(n)=P(n)作为启发函数时*/
void CEight_COde2Dlg::On_Pn() 
{
	UpdateData(TRUE);
	flag=1;
 	m_wn=1;
    m_pn=0;
 	m_wf=1;
	UpdateData(FALSE);
}
//--------------------------------------------------------------------------------------------
/*当选择宽度优先作为启发函数时*/
void CEight_COde2Dlg::OnWf() 
{
	UpdateData(TRUE);
    flag=2;
 	m_wn=1;
    m_pn=1;
 	m_wf=0;
	UpdateData(FALSE);		
}
//--------------------------------------------------------------------------------------------
/*保存解路径*/
void CEight_COde2Dlg::saveroad(int positioninopen)
{
	int positioninnode=open[positioninopen];
    Node temp;
    int onesteplen=0;
	copynode(temp,nodearray[positioninnode]);
	while(temp.pointer!=-1){
		onestep[onesteplen]=temp.selfposition;
		onesteplen++;
		copynode(temp,nodearray[temp.pointer]);
	}
	step_num=onesteplen;
	roadlen=step_num;
}
//----------------------------------------------------------------------------------------------
/*单击‘单步执行’按钮，可以看到解路径上每一步的中间状态*/
void CEight_COde2Dlg::OnOneStep() 
{
  
   step_num--;
   if(step_num<0){
		AfxMessageBox("显示结束！");
	  
	  }
  // int temp=onestep[step_num];

   if(step_num>=0){
      
	  int temp=onestep[step_num];
    
	  m_midd_edit0=nodearray[temp].array[0][0];
	  m_midd_edit1=nodearray[temp].array[0][1];
      m_midd_edit2=nodearray[temp].array[0][2];
	  m_midd_edit3=nodearray[temp].array[1][0];
	  m_midd_edit4=nodearray[temp].array[1][1];
	  m_midd_edit5=nodearray[temp].array[1][2];
      m_midd_edit6=nodearray[temp].array[2][0];
	  m_midd_edit7=nodearray[temp].array[2][1];
	  m_midd_edit8=nodearray[temp].array[2][2];
	  m_Step=roadlen-step_num;
	  UpdateData(FALSE);

	 if(step_num==0){
		AfxMessageBox("显示结束！");
	  
	  }
   }
}
//----------------------------------------------------------------------------------------------
/*自动初始化，这里以课本例题为例*/

void CEight_COde2Dlg::OnInitialNode() 
{
 m_begin_edit0=nodearray[0].array[0][0]=2;
 m_begin_edit1=nodearray[0].array[0][1]=8;
 m_begin_edit2=nodearray[0].array[0][2]=3;
 m_begin_edit3=	nodearray[0].array[1][0]=1;
 m_begin_edit4=	nodearray[0].array[1][1]=6;
 m_begin_edit5=	nodearray[0].array[1][2]=4;
 m_begin_edit6=	nodearray[0].array[2][0]=7;
 m_begin_edit7=	nodearray[0].array[2][1]=0;
 m_begin_edit8=	nodearray[0].array[2][2]=5;

 nodearray[0].pointer=-1;
 nodearray[0].g=0;
 nodearray[0].selfposition=0;
 len++;
 open[0]=0;
 openlen++;

 m_end_edit0=	endnode.array[0][0]=1;
 m_end_edit1=	endnode.array[0][1]=2;
 m_end_edit2=	endnode.array[0][2]=3;
 m_end_edit3=	endnode.array[1][0]=8;
 m_end_edit4=	endnode.array[1][1]=0;
 m_end_edit5=	endnode.array[1][2]=4;
 m_end_edit6=	endnode.array[2][0]=7;
 m_end_edit7=	endnode.array[2][1]=6;
 m_end_edit8=	endnode.array[2][2]=5;

 nodearray[0].h=get_h(nodearray[0],endnode,flag);
 nodearray[0].f=nodearray[0].g+nodearray[0].h;
 UpdateData(FALSE);

}
//----------------------------------------------------------------------------------------------
/*统计运行时间*/
void CEight_COde2Dlg::print_runtime()
{
    int minute= finish.wMinute- star.wMinute;
	int second= finish.wSecond- star.wSecond ;
	int millisecond= finish.wMilliseconds- star.wMilliseconds;
	if(millisecond < 0)
	{
		second-=1;
		millisecond+=1000;
	}
	if(second < 0)
	{
		minute-=1;
		second+=60;
	}

	m_Minute=minute;
	m_Second=second;
	m_Millisecond=millisecond;
	UpdateData(FALSE);

}
//----------------------------------------------------------------------------------------------
/*统计扩展节点的数目*/
void CEight_COde2Dlg::print_NodeNum()
{
    
	m_Nodenum=len-1;   //这里要减去头节点与目标节点
	UpdateData(FALSE);	
}
//----------------------------------------------------------------------------------------------
/*计算平均分枝因子*/
void CEight_COde2Dlg::print_AvgNode()
{   
	 m_AvgNode=  (len-1+0.00)/step_num;	//扩展的节点数目除以扩展的步数
	 UpdateData(FALSE);

}

//----------------------------------------------------------------------------------------------
/*‘清空’操作*/

void CEight_COde2Dlg::OnClearButton() 
{	
  	len=0;//数组长度
    openlen=0;
    closelen=0;
    roadlen=0;
	flag=1;
	step_num=0;
	memset(open,-1,sizeof(int)*3000);
	memset(close,-1,sizeof(int)*3000);
	memset(nodearray,0,sizeof(int)*15*3000);
	memset(onestep,-1,sizeof(int)*1000);
	m_begin_edit0 = 0;
	m_begin_edit1 = 0;
	m_begin_edit2 = 0;
	m_begin_edit3 = 0;
	m_begin_edit4 = 0;
	m_begin_edit5 = 0;
	m_begin_edit6 = 0;
	m_begin_edit7 = 0;
	m_begin_edit8 = 0;
	m_end_edit0 = 0;
	m_end_edit1 = 0;
	m_end_edit2 = 0;
	m_end_edit3 = 0;
	m_end_edit4 = 0;
	m_end_edit5 = 0;
	m_end_edit6 = 0;
	m_end_edit7 = 0;
	m_end_edit8 = 0;
	m_midd_edit0 = 0;
	m_midd_edit1 = 0;
	m_midd_edit2 = 0;
	m_midd_edit3 = 0;
	m_midd_edit4 = 0;
	m_midd_edit5 = 0;
	m_midd_edit6 = 0;
	m_midd_edit7 = 0;
	m_midd_edit8 = 0;
	m_Minute = 0;
	m_Second = 0;
	m_Millisecond = 0;
	m_Nodenum = 0;
	m_AvgNode = 0.0;
	m_road_len=0;
	m_Step=0;
 	m_wn=0;
    m_pn=1;
 	m_wn=1;	
    UpdateData(FALSE);

}
//----------------------------------------------------------------------------------------------
/*判断是否能找出解路径*/
bool CEight_COde2Dlg::judgement(Node &a, Node &b)
{
    int m1=0, m2=0;//利用int SmallerNum(char *p, int index)函数分别求出初始状态数组中每个元素之前比自己小的元素的个数.然后一次相加得m1,同理求出目标状态数组的m2,然后看m1和m2 是否满足同样的奇偶性.相同则有解.反之无解

	int i;
	for(i=1; i<9; i++)
	{
		m1= m1+ sigma(i, a);
	}
	for(i=1; i<9; i++)
	{
		m2= m2+ sigma(i, b);
	}

	if( m1 % 2  ==  m2 % 2 )
		return true;
	else 
        return false;

}

int CEight_COde2Dlg::sigma(long x, Node &a)
{

	long temp[8];
	int i, j, count, total, p;

	count=0;
	total=0;
	for(i=0; i<3; i++)
	{
		for(j=0; j<3; j++)
		{
			if(a.array[i][j] != 0)
			{
				temp[count]=a.array[i][j];

				if( a.array[i][j] == x)
					p=count;

				count+=1;
			}
		}
	}

	for(i=0; i<p; i++)
	{
		if(temp[i] < temp[p])
			total+=1;
	}

	return total;

}
//----------------------------------------------------------------------------------------------
/*输入合法性判断*/

bool CEight_COde2Dlg::checkerr(Node a)
{
	for(int i=0; i<3; i++)
		for(int j=0; j<3; j++){
			if(a.array[i][j]<0 && a.array[i][j]>8)return false;
		}
	int tmp_array[9]={0};
	int temp;
	for(int m=0; m<3; m++){
		for(int n=0; n<3; n++){
			temp=a.array[m][n];
			tmp_array[temp]=1;
		}
	}
	for(int k=0; k<9; k++){
		if(tmp_array[k]==0)return false;
	}
	return true;
}

void CEight_COde2Dlg::print_road_len()
{
	m_road_len=step_num+1;
    UpdateData(FALSE);
}