aidlg.cpp

八数码问题全局择优算法这个程序是上学期上人工智能课的时候

	switch(modle)
	{
	case 0:
		if((position+1==Pic[1][1].position)||(position+3==
			Pic[1][1].position)||(position-3==Pic[1][1].position))
			return true;
	case 1:
		if((position+1==Pic[1][1].position)||(position+3==
			Pic[1][1].position)||(position-3==Pic[1][1].position)||
			(position-1==Pic[1][1].position))
			return true;
	case 2:
		if(position-1==Pic[1][1].position||position+3==
			Pic[1][1].position||position-3==Pic[1][1].position)
			return true;
	default:return false;
	}
}

void CAIDlg::OnAutocomplete() 
{
	// TODO: Add your command handler code here
	CString strCount;
	if(GlobalSelect()!=NULL)
	{
		autohead=head;
		if(autohead->Next!=NULL)
		{
			MoveCount=0;
			strCount.Format("次数：%d",MoveCount);
			m_Count.SetWindowText(strCount);
			SetTimer(1,500,NULL);
			MouseFlag=FALSE;
		}
		else
		MessageBox("成功完成！");
		
	}
	else
		MessageBox("对不起！此状态没有解！");
}

struct status* CAIDlg::GlobalSelect()
{
	struct status	*cUrrent,*OpenHead,*temp;
	int i,j,k;
	head=(struct status*)new(struct status);
	cUrrent=head;
	OpenHead=head;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			cUrrent->position[3*i+j]=Pic[i][j].position;
		cUrrent->depth=0;
		cUrrent->Parent=NULL;
		cUrrent->Next=NULL;
		cUrrent->charge=Charge(cUrrent);
	if(Completed(cUrrent))
		{
			return head;
		}
	else
		{
			for(k=0;k<50000;k++)
			{
				if(CanLeft(cUrrent))
				{
					temp=new(struct status);
					for(i=0;i<9;i++)
					{
						temp->position[i]=cUrrent->position[i];
						if(temp->position[i]==(cUrrent->position[4]-1))
							j=i;
					}
					temp->position[4]--;
					temp->position[j]++;
					if(NoSame(temp))	
					{
						temp->Parent=cUrrent;
						temp->depth=cUrrent->depth+1;
						temp->charge=Charge(temp);
						InSert(cUrrent,temp);
						if(Completed(temp))
						{
							Prepare(temp);
							return head;
						}
						
					}
					else
						delete temp;
				}
				if(CanRight(cUrrent))
				{
					temp=new(struct status);
					for(i=0;i<9;i++)
					{
						temp->position[i]=cUrrent->position[i];
						if(temp->position[i]==(cUrrent->position[4]+1))
							j=i;
					}
					temp->position[4]++;
					temp->position[j]--;
					if(NoSame(temp))	
					{
						temp->Parent=cUrrent;
						temp->depth=cUrrent->depth+1;
						temp->charge=Charge(temp);
						InSert(cUrrent,temp);
						if(Completed(temp))
						{
							Prepare(temp);
							return head;
						}
						
					}
					else
						delete temp;
				}
				if(CanUp(cUrrent))
				{
					temp=new(struct status);
					for(i=0;i<9;i++)
					{
						temp->position[i]=cUrrent->position[i];
						if(temp->position[i]==(cUrrent->position[4]-3))
							j=i;
					}
					temp->position[4]-=3;
					temp->position[j]+=3;
					if(NoSame(temp))	
					{
						temp->Parent=cUrrent;
						temp->depth=cUrrent->depth+1;
						temp->charge=Charge(temp);
						InSert(cUrrent,temp);
						if(Completed(temp))
						{
							Prepare(temp);
							return head;
						}
						
					}
					else
						delete temp;
				}
				if(CanDown(cUrrent))
				{
					temp=new(struct status);
					for(i=0;i<9;i++)
					{
						temp->position[i]=cUrrent->position[i];
						if(temp->position[i]==(cUrrent->position[4]+3))
							j=i;
					}
					temp->position[4]+=3;
					temp->position[j]-=3;
					if(NoSame(temp))	
					{
						temp->Parent=cUrrent;
						temp->depth=cUrrent->depth+1;
						temp->charge=Charge(temp);
						InSert(cUrrent,temp);
						if(Completed(temp))
						{
							Prepare(temp);
							return head;
						}
						
					}
					else
						delete temp;
				}
				cUrrent=cUrrent->Next;
			}
			return NULL;
	}
}

int CAIDlg::Charge(status *cNode)//return the charge
{
	char chargetable[9][2]={{0,0},{1,0},{2,0},{0,1},{1,1},{2,1},{0,2},{1,2},{2,2}};
	char charge=0;
	int x,y;
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		if((i*j)!=1)
		{
		x=int(cNode->position[i*3+j])%3;
		y=int(cNode->position[i*3+j])/3;
		charge=charge+abs(x-chargetable[i*3+j][0])+abs(y-chargetable[i*3+j][1]);
		}
	return (charge+cNode->depth);

}

BOOL CAIDlg::Completed(struct status *cNode)
{
	int i;
	for(i=0;i<9;i++)
	{
		if(cNode->position[i]!=ObjectStatus[i])
		return FALSE;
	}
	return TRUE;
}

BOOL CAIDlg::CanLeft(status *cNode)
{
	if(cNode->position[4]%3!=0)
	{
		if(cNode->Parent==NULL)
			return TRUE;
		if((cNode->Parent)->position[4]%3!=0)
			return TRUE;
	}
	return FALSE;
}

BOOL CAIDlg::CanRight(status *cNode)
{
	if(cNode->position[4]%3!=2)
	{
		if(cNode->Parent==NULL)
			return TRUE;
		if(cNode->Parent->position[4]%3!=2)
			return TRUE;
	}
		return FALSE;
}

BOOL CAIDlg::CanUp(status *cNode)
{
	if((int)(cNode->position[4]/3)!=0)
	{
		if(cNode->Parent==NULL)
			return TRUE;
		if((int)(cNode->Parent->position[4]/3)!=0)
			return TRUE;
	}
		return FALSE;
}

BOOL CAIDlg::CanDown(status *cNode)
{
	if((int)(cNode->position[4]/3)!=2)
	{
		if(cNode->Parent==NULL)
			return TRUE;
		if((int)(cNode->Parent->position[4]/3)!=2)
			return TRUE;
	}
		return FALSE;
}

BOOL CAIDlg::NoSame(status *cNode)
{
	struct status *temp;
	temp=head;
	int i;
	while(temp)/////////////////////////////////////////////!=NULL)
	{	
		bool flag=true;
		for(i=0;i<9;i++)
			if(cNode->position[i]!=temp->position[i])
			{
				temp=temp->Next;
				flag=false;
				break;
			}
			if(flag)
				return FALSE;
	}
	return TRUE;
}

void CAIDlg::InSert(status *cNode,status *temp)
{
	struct status *cUrrent;
	cUrrent=cNode;
	while(cUrrent->Next)
	{
		if(temp->charge<cUrrent->Next->charge)
		{
			temp->Next=cUrrent->Next;
			cUrrent->Next=temp;
			return;
		}
		else
			cUrrent=cUrrent->Next;
	}
	cUrrent->Next=temp;
	temp->Next=NULL;
}

void CAIDlg::Prepare(status* object)
{
	struct status *temp1,*temp2,*temp3;
	temp1=object->Parent;
	temp3=object;
	object->Parent=NULL;
	while(temp1!=NULL)
	{
		temp2=temp1->Parent;
		temp1->Parent=temp3;
		temp3=temp1;
		temp1=temp2;
	}
}

void CAIDlg::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	if(nIDEvent==1)
	{int i,j,m,n,position[4];
	autohead=autohead->Parent;
	m=0;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		{
			if(Pic[i][j].position!=autohead->position[3*i+j])
			{
				position[m++]=i;
				position[m++]=j;
				Pic[i][j].position=autohead->position[3*i+j];
			}
		}
	i=position[0];
	j=position[1];
	m=position[2];
	n=position[3];
	SetPicPosition();
	//InvalidateRect(&Pic[i][j].PicRect,TRUE);
	//InvalidateRect(&Pic[m][n].PicRect,TRUE);
	//Invalidate();
	//SendMessage(WM_ONPAINT);
	//UpdateData();
	draw(i,j,m,n);
	//CDialog::OnTimer(nIDEvent);
	if(autohead->Parent==NULL)
	{
		KillTimer(1);
		MessageBox("成功完成！！");
		MouseFlag=TRUE;
		ReleaseSpace();
	}
	}
else
	{
		TimeCount++;
		CString Timestr;
		Timestr.Format("时间:%d分%d秒",TimeCount/60,TimeCount%60);
		m_Time.SetWindowText(Timestr);
	}
}

void CAIDlg::draw(int x, int y,int a,int b)
{
	CDC *pDC=GetDC();
	CDC memdc1;
	CRect Rect;
	CBitmap bitmap;
	CString strCount;
	MoveCount++;
  	bitmap.LoadBitmap(IDB_BITMAP);
	memdc1.CreateCompatibleDC(NULL);
	memdc1.SelectObject(bitmap);
	pDC->BitBlt(Pic[x][y].PicRect.left,
				Pic[x][y].PicRect.top,
				120,
				160,
				&memdc1,
				(y)*120,
				(x)*160,
				SRCCOPY);
	pDC->BitBlt(Pic[a][b].PicRect.left,
				Pic[a][b].PicRect.top,
				120,
				160,
				&memdc1,
				(b)*120,
				(a)*160,
				SRCCOPY);
	Rect.left=10;Rect.bottom=490;Rect.right=380;Rect.top=10;
	pDC->DrawEdge(&Rect,EDGE_BUMP,BF_RECT);
	strCount.Format("次数：%d",MoveCount);
	m_Count.SetWindowText(strCount);
	pDC->DeleteDC();
	DeleteObject(bitmap);
	return;
}

void CAIDlg::ReleaseSpace()
{
	struct status *temp;
	temp=head;
	while(temp->Next!=NULL)
	{
		temp=temp->Next;
		delete head;
		head=temp;
	}
	delete temp;
	head=NULL;
}

void CAIDlg::OnClose() 
{
	// TODO: Add your message handler code here and/or call default
		KillTimer(2);
		CDialog::OnClose();

}

BOOL CAIDlg::Finished()
{
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
	{
		if(Pic[i][j].position!=(3*i+j))
			return FALSE;
	}
	return TRUE;
}

BOOL CAIDlg::DestroyWindow() 
{
	// TODO: Add your specialized code here and/or call the base class
	return CDialog::DestroyWindow();
}