📄 jiug.cpp
字号:
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));
m_node++;
//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
}
}
///////////////////////////////广度优先算法////////////
bool CJiuG::Bfs()
{
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 nindex=0;
//Open表为空，失败退出
if(OpenList.IsEmpty())
return false;
pmin=(JGState *)OpenList.GetAt(OpenList.FindIndex(nindex));
//将n节点从Open表删除，加入到Close表中
OpenList.RemoveAt(OpenList.FindIndex(nindex));
CloseList.AddTail((void *)pmin);
newstate=(JGState *)malloc(sizeof(JGState));
m_node++;
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));
m_node++;
//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));
m_node++;
//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));
m_node++;
//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 + -