?? jiug.cpp
字號:
// JiuG.cpp: implementation of the CJiuG class.
#include "stdafx.h"
#include "Jiugong.h"
#include "JiuG.h"
#include "math.h"//計算估價函數是會用到abs()，如果用錯位數，則不用包含
#include "stdlib.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CJiuG::CJiuG()
{
m_ndepth=100;//設置默認的深度為100，可以在程序中改動
}
CJiuG::~CJiuG()
{
}
/////////////////////////////////////////////////////////////////////
//左移
bool CJiuG::MoveLeft(JGState *src,JGState *result)
{
int x,y,tempx,tempy;
for(x=0;x<3;x++){
for(y=0;y<3;y++){
if(src->state[x][y]==0){
tempx=x;
tempy=y;
}
}
}
if(tempy==0)
return false;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
result->state[i][j]=src->state[i][j];
}
}
result->state[tempx][tempy] = src->state[tempx][tempy-1];
result->state[tempx][tempy-1] = 0;
result->curdistance=src->curdistance+1;
result->prestate=src;
result->nextstate=NULL;
return true;
}
////////////////////////////////////////////////////////////////////
//右移
bool CJiuG::MoveRight(JGState *src,JGState *result)
{
int x,y,tempx,tempy;
for(x=0;x<3;x++){
for(y=0;y<3;y++){
if(src->state[x][y]==0){
tempx=x;
tempy=y;
}
}
}
if(tempy==2)
return false;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
result->state[i][j]=src->state[i][j];
}
}
result->state[tempx][tempy]=src->state[tempx][tempy+1];
result->state[tempx][tempy+1]=0;
result->curdistance=src->curdistance+1;
result->prestate=src;
result->nextstate=NULL;
return true;
}
///////////////////////////////////////////////////////////////////
//上移，上面的左移，右移，下面的下移，結構一樣
bool CJiuG::MoveUp(JGState *src,JGState *result)
{
int x,y,tempx,tempy;
//尋找空格位置
for(x=0;x<3;x++){
for(y=0;y<3;y++){
if(src->state[x][y]==0){
tempx=x;
tempy=y;
}
}
}
//判斷是否可移
if(tempx==0)
return false;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
result->state[i][j]=src->state[i][j];
}
}
result->state[tempx][tempy]=src->state[tempx-1][tempy];
result->state[tempx-1][tempy]=0;
result->curdistance=src->curdistance+1;//深度加一
result->prestate=src;//設置前趨節點
result->nextstate=NULL;
return true;
}
////////////////////////////////////////////////////////////////////
//下移
bool CJiuG::MoveDown(JGState *src,JGState *result)
{
int x,y,tempx,tempy;
for(x=0;x<3;x++){
for(y=0;y<3;y++){
if(src->state[x][y]==0){
tempx=x;
tempy=y;
}
}
}
if(tempx==2)
return false;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
result->state[i][j]=src->state[i][j];
}
}
result->state[tempx][tempy]=result->state[tempx+1][tempy];
result->state[tempx+1][tempy]=0;
result->curdistance=src->curdistance+1;
result->prestate=src;
result->nextstate=NULL;
return true;
}
///////////////////////////////////////////////////////////////////
//比較兩個狀態是否相等
bool CJiuG::Compare(JGState *src1,JGState *src2)
{
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
if(src1->state[i][j]!=src2->state[i][j])
return false;
}
}
return true;
}
///////////////////////////////////////////////////////////////////
//計算估價函數，采用了每一步移到正確的位置需要的步數
int CJiuG::ComputeFn(JGState *cur,JGState *dest)
{
int xcur[9],ycur[9],xdest[9],ydest[9];//保存9個坐標
int i,j;
int result=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
xcur[cur->state[i][j]]=i;
ycur[cur->state[i][j]]=j;
xdest[dest->state[i][j]]=i;
ydest[dest->state[i][j]]=j;
}
}
for(i=1;i<9;i++){
result=result+abs(xcur[i]-xdest[i])+abs(ycur[i]-ydest[i]);
}
return result;
/*int result=0;//注釋掉的部分是采用了錯位數來計算
int i,j;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(cur->state[i][j]!=dest->state[i][j])
result++;
}
}
return result;*/
}
///////////////////////////////////////////////////////////////////
//搜索最優解，這是程序的核心部分
bool CJiuG::Search()
{
int MAXDEPTH=m_ndepth;
FreeList(&OpenList);
FreeList(&CloseList);
FreeList(&ResultList);
JGState *newstate,*pstart;
int i,k;
newstate=(JGState *)malloc(sizeof(JGState));
CopyJG(&StateInit,newstate);
newstate->curdistance=0;
newstate->nextstate=NULL;
newstate->prestate=NULL;
pstart=newstate;
curstep=pstart;
//如果初始狀態和末態相同，搜索成功退出
if(Compare(&StateInit,&StateObj)==true){
ResultList.AddTail((void *)newstate);
return true;
}
//將起始結點加入Open表中
OpenList.AddHead((void *)newstate);
//搜索
while(true){
JGState *pmin;
int nmin;
int nindex=0;
//Open表為空，失敗退出
if(OpenList.IsEmpty())
return false;
i=OpenList.GetCount();
nmin=100000000;
//搜索Open表中估計值最小的節點
for(k=0;k<i;k++){
JGState *ptemp;
ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
int ntemp=ptemp->curdistance+ComputeFn(ptemp,&StateObj);
if(ntemp<nmin){
nmin=ntemp;
pmin=ptemp;
nindex=k;
}
}
//將估價函數最小的節點從Open表刪除，加入到Close表中
OpenList.RemoveAt(OpenList.FindIndex(nindex));
CloseList.AddTail((void *)pmin);
newstate=(JGState *)malloc(sizeof(JGState));
//move to left，用了搜索深度控制。下面的右移，上移，下移程序結構相同
//可以將相同的部分寫成函數，我沒有這樣做
if((MoveLeft(pmin,newstate)==true)&&(newstate->curdistance<=MAXDEPTH)){
if((Compare(newstate,&StateObj)==false)){
//不是目標節點，則看是否可以加入到Open表中
bool inopen=false;
bool inclose=false;
JGState *ptemp;
//檢查是否在Open表中
i=OpenList.GetCount();
if(i==0)
inopen=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inopen=true;
if(ptemp->curdistance>newstate->curdistance)
CopyJG(newstate,ptemp);
break;
}
}
}
//檢查是否在Close表中
i=CloseList.GetCount();
if(i==0)
inclose=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inclose=true;
break;
}
}
}
if((inopen==false)&&(inclose==false))
OpenList.AddHead(newstate);
}//end if
else{
//找到目標結點
JGState *newstate1;
ResultList.AddHead((void *)newstate);
newstate=newstate->prestate;
//回溯，得到ResultList
while(newstate!=pstart){
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
newstate=newstate->prestate;
}
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
return true;
}//end else
}//end if
else{
free(newstate);
}//end move left
newstate=(JGState *)malloc(sizeof(JGState));
//move to right
if(MoveRight(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
if((Compare(newstate,&StateObj)==false)){
//不是目標節點，則看是否可以加入到Open表中
bool inopen=false;
bool inclose=false;
JGState *ptemp;
i=OpenList.GetCount();
if(i==0)
inopen=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inopen=true;
if(ptemp->curdistance>newstate->curdistance)
CopyJG(newstate,ptemp);
break;
}
}
}
i=CloseList.GetCount();
if(i==0)
inclose=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inclose=true;
break;
}
}
}
if((inopen==false)&&(inclose==false))
OpenList.AddHead(newstate);
}//end if
else{
//找到目標結點
JGState *newstate1;
ResultList.AddHead((void *)newstate);
newstate=newstate->prestate;
while(newstate!=pstart){
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
newstate=newstate->prestate;
}
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
return true;
}//end else
}//end if
else{
free(newstate);
}//end move right
newstate=(JGState *)malloc(sizeof(JGState));
//move to up
if(MoveUp(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
if((Compare(newstate,&StateObj)==false)){
//不是目標節點，則看是否可以加入到Open表中
bool inopen=false;
bool inclose=false;
JGState *ptemp;
i=OpenList.GetCount();
if(i==0)
inopen=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inopen=true;
if(ptemp->curdistance>newstate->curdistance)
CopyJG(newstate,ptemp);
break;
}
}
}
i=CloseList.GetCount();
if(i==0)
inclose=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inclose=true;
break;
}
}
}
if((inopen==false)&&(inclose==false))
OpenList.AddHead(newstate);
}//end if
else{
//找到目標結點
JGState *newstate1;
ResultList.AddHead((void *)newstate);
newstate=newstate->prestate;
while(newstate!=pstart){
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
newstate=newstate->prestate;
}
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
return true;
}//end else
}//end if
else{
free(newstate);
}//end move up
newstate=(JGState *)malloc(sizeof(JGState));
//move to down
if(MoveDown(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
if((Compare(newstate,&StateObj)==false)){
//不是目標節點，則看是否可以加入到Open表中
bool inopen=false;
bool inclose=false;
JGState *ptemp;
i=OpenList.GetCount();
if(i==0)
inopen=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inopen=true;
if(ptemp->curdistance>newstate->curdistance)
CopyJG(newstate,ptemp);
break;
}
}
}
i=CloseList.GetCount();
if(i==0)
inclose=false;
else{
for(k=0;k<i;k++){
ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
if(Compare(newstate,ptemp)==true){
inclose=true;
break;
}
}
}
if((inopen==false)&&(inclose==false))
OpenList.AddHead(newstate);
}//end if
else{
//找到目標結點
JGState *newstate1;
ResultList.AddHead((void *)newstate);
newstate=newstate->prestate;
while(newstate!=pstart){
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
newstate=newstate->prestate;
}
newstate1=(JGState *)malloc(sizeof(JGState));
CopyJG(newstate,newstate1);
ResultList.AddHead(newstate1);
return true;
}//end else
}//end if
else{
free(newstate);
}//end move down
}
}
///////////////////////////////////////////////////////////////////
//釋放內存
void CJiuG::FreeList(CPtrList *list)
{
if(list->IsEmpty())
return;
int i=list->GetCount();
JGState *p;
for(int j=0;j<i;j++){
p=(JGState *)list->GetHead();
list->RemoveHead();
free(p);
}
}
void CJiuG::CopyJG(JGState *src,JGState *dest)
{
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
dest->state[i][j]=src->state[i][j];
}
}
dest->curdistance=src->curdistance;
dest->prestate=src->prestate;
dest->nextstate=src->nextstate;
}
//////////////////////////////////////////////////////////////////
//計算逆序奇偶性，以判斷有無解，基于我對九宮問題解是否可達的證明
//返回0為偶，返回1為奇
int CJiuG::ComputeJO(JGState *jo)
{
int result=0;
int i,j;
int k=0;
int temp[8];
//除去0，將其余8個數依次加入到數組中
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(jo->state[i][j]!=0){
temp[k]=jo->state[i][j];
k++;
}
}
}
//判斷奇偶性
for(i=0;i<7;i++){
for(j=i+1;j<8;j++){
if(temp[i]>temp[j])
result++;
}
}
result=result%2;
return result;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -