求八数码中遇到的问题
我的代码在vs2010下编译通过后，运行，输入数组后程序崩了，提示deque iterator not dereferencable
我没有发现我的代码的错误，求高人帮助，我采用的是全局择优搜索解八数码下面是我的代码
- C/C++ code
#include<iostream>#include<deque>#include<vector>#include<string.h>using namespace std;int go_l[3][3]={0}; //目标节点class QNode{public: int depth; //节点的深度 int diff; //与父亲节点不同位置的数字个数 int fs; //估价函数值 fs=depth+diff int arry[3][3]; //八数码数组 QNode() //空构造函数 { depth=0; diff=0; fs=0; memset(arry,0,sizeof(arry)); } QNode(const QNode &ha) //复制构造函数 { this->depth=ha.depth; this->diff=ha.diff; this->fs=ha.fs; for(int i=0;i!=3;i++) for(int j=0;j!=3;j++) this->arry[i][j]=ha.arry[i][j]; } QNode(int dep,int dif,int (&aa)[3][3]) //赋值构造函数2 { this->depth=dep; this->diff=dif; this->fs=this->depth+this->diff; for(int i=0;i!=3;i++) for(int j=0;j!=3;j++) this->arry[i][j]=aa[i][j]; } void Display() //打印 { cout<<"深度为"<<this->depth<<endl; //cout<<"与父亲节点位置不同的数字个数为"<<diff<<endl; for(int i=0;i!=3;i++) { for(int j=0;j!=3;j++) cout<<this->arry[i][j]<<' '; cout<<endl; } } bool Equal(QNode &a) //判断是否相等 { for(int i=0;i!=3;i++) { for(int j=0;j!=3;j++) { if(this->arry[i][j]!=a.arry[i][j]) return false; continue; } } return true; } void Exchange(QNode &p) //交换节点数值 { int r=0,s=0,t=0; r=this->depth; this->depth=p.depth; p.depth=r; //交换depth s=this->diff; this->diff=p.diff; p.diff=s; //交换diff值 this->fs=depth+diff; //交换估价函数值 p.fs=p.depth+p.diff; for(int i=0;i!=3;i++) //交换二维数组arry的值 { for(int j=0;j!=3;j++) { t=this->arry[i][j]; this->arry[i][j]=p.arry[i][j]; p.arry[i][j]=t; } } }};deque<QNode> open; //open表vector<QNode> whole; //记录已经扩展过得节点//vector<QNode> opens; //用于排序，然后插入open表vector<QNode> closed; //closed表int Check_cal(int (&a)[3][3]) //计算与父亲节点位置不同的数字个数{ int hi=1,count=0; while(hi<9) { int flag=0; for(int i=0;i!=3;i++) { for(int j=0;j!=3;j++) { if(a[i][j]==hi&&go_l[i][j]!=hi) flag=1; else continue; } } if(flag==1) count++; hi++; } return count;}bool Check_equ(QNode &a){ for(int i=0;i!=3;i++) { for(int j=0;j!=3;j++) { if(a.arry[i][j]!=go_l[i][j]) return false; continue; } } return true;}bool Check_can(QNode &a,vector<QNode> &whole) //检验是否可以扩展（即与已经扩展过得节点是否相同），相同则返回false{ if(whole.size()==1&&whole[0].Equal(a)) return true; else { for(vector<QNode>::size_type i=0;i!=whole.size();i++) if(a.Equal(whole[i])) return false; return true; }}void Sort(deque<QNode> &open) //递增冒泡排序{ for(int it=0;it!=open.size()-1;it++) { for(deque<QNode>::iterator jt=open.begin();jt!=open.end()-it-1;jt++) { if(jt->fs>(jt+1)->fs) jt->Exchange(*(jt+1)); } }}void Extend(QNode &a,vector<QNode> &whole) //扩展父亲节点，插入open表并排序{ int l=0,r=0,flag,m,n; QNode q1,q2,q3,q4; for(int i=0;i!=3;i++) { for(int j=0;j!=3;j++) { if(a.arry[i][j]==0) { l=i; r=j; } continue; } } if(l==1&&r==1) flag=4; if((l==0&&r==0)||(l==2&&r==0)||(l==0&&r==2)||(l==2&&r==2)) flag=2; if((l==1&&r==0)||(l==2&&r==1)||(l==1&&r==2)||(l==0&&r==1)) flag=3; switch(flag) { case 4: q1.depth=a.depth+1;q2.depth=a.depth+1;q3.depth=a.depth+1;q4.depth=a.depth+1; //子节点的深度为父节点深度加1 for(m=0;m!=3;m++) //修改相应的八数码二维数组 { for(n=0;n!=3;n++) { q1.arry[m][n]=a.arry[m][n]; q2.arry[m][n]=a.arry[m][n]; q3.arry[m][n]=a.arry[m][n]; q4.arry[m][n]=a.arry[m][n]; } } m=0;n=0; q1.arry[1][1]=q1.arry[1][0]; q1.arry[1][0]=0; q2.arry[1][1]=q2.arry[2][1]; q2.arry[2][1]=0; q3.arry[1][1]=q3.arry[1][2]; q3.arry[1][2]=0; q4.arry[1][1]=q4.arry[0][1]; q4.arry[0][1]=0; q1.diff=Check_cal(q1.arry);q2.diff=Check_cal(q2.arry);q3.diff=Check_cal(q3.arry);q4.diff=Check_cal(q4.arry); //获得diff q1.fs=q1.depth+q1.diff;q2.fs=q2.depth+q2.diff;q3.fs=q3.depth+q3.diff;q4.fs=q4.depth+q4.diff; //获得估价函数值 whole.push_back(q1);whole.push_back(q2);whole.push_back(q3);whole.push_back(q4); open.push_back(q1);open.push_back(q2);open.push_back(q3);open.push_back(q4); Sort(open); break; case 3: q1.depth=a.depth+1;q2.depth=a.depth+1;q3.depth=a.depth+1; //深度加1 for(m=0;m!=3;m++) //修改相应的八数码二维数组 { for(n=0;n!=3;n++) { q1.arry[m][n]=a.arry[m][n]; q2.arry[m][n]=a.arry[m][n]; q3.arry[m][n]=a.arry[m][n]; } } for(m=0;m!=3;m++) { for(n=0;n!=3;n++) { if(a.arry[m][n]==0) { l=m;r=n; break; } } } if(l==1&&r==0) { q1.arry[l][r]=q1.arry[0][0];q1.arry[0][0]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[2][0];q2.arry[2][0]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; q3.arry[l][r]=q3.arry[1][1];q3.arry[1][1]=0; q3.diff=Check_cal(q3.arry);q3.fs=q3.depth+q3.diff; whole.push_back(q1);whole.push_back(q2);whole.push_back(q3); open.push_back(q1);open.push_back(q2);open.push_back(q3); Sort(open); } if(l==2&&r==1) { q1.arry[l][r]=q1.arry[2][0];q1.arry[2][0]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[1][1];q2.arry[1][1]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; q3.arry[l][r]=q3.arry[2][2];q3.arry[2][2]=0; q3.diff=Check_cal(q3.arry);q3.fs=q3.depth+q3.diff; whole.push_back(q1);whole.push_back(q2);whole.push_back(q3); open.push_back(q1);open.push_back(q2);open.push_back(q3); Sort(open); } if(l==1&&r==2) { q1.arry[l][r]=q1.arry[2][2];q1.arry[2][2]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[1][1];q2.arry[1][1]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; q3.arry[l][r]=q3.arry[0][2];q3.arry[0][2]=0; q3.diff=Check_cal(q3.arry);q3.fs=q3.depth+q3.diff; whole.push_back(q1);whole.push_back(q2);whole.push_back(q3); open.push_back(q1);open.push_back(q2);open.push_back(q3); Sort(open); } if(l==0&&r==1) { q1.arry[l][r]=q1.arry[0][0];q1.arry[0][0]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[1][1];q2.arry[1][1]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; q3.arry[l][r]=q3.arry[0][2];q3.arry[0][2]=0; q3.diff=Check_cal(q3.arry);q3.fs=q3.depth+q3.diff; whole.push_back(q1);whole.push_back(q2);whole.push_back(q3); open.push_back(q1);open.push_back(q2);open.push_back(q3); Sort(open); } break; case 2: q1.depth=a.depth+1;q2.depth=a.depth+1; //子节点深度为父节点加1 for(m=0;m!=3;m++) //修改相应的八数码二维数组 { for(n=0;n!=3;n++) { q1.arry[m][n]=a.arry[m][n]; q2.arry[m][n]=a.arry[m][n]; } } for(m=0;m!=3;m++) { for(n=0;n!=3;n++) { if(a.arry[m][n]==0) { l=m;r=n; break; } } } if(l==0&&r==0) { q1.arry[l][r]=q1.arry[1][0];q1.arry[1][0]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[0][1];q2.arry[0][1]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; whole.push_back(q1);whole.push_back(q2); open.push_back(q1);open.push_back(q2); Sort(open); } if(l==2&&r==0) { q1.arry[l][r]=q1.arry[1][0];q1.arry[1][0]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[2][1];q2.arry[2][1]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; whole.push_back(q1);whole.push_back(q2); open.push_back(q1);open.push_back(q2); Sort(open); } if(l==2&&r==2) { q1.arry[l][r]=q1.arry[2][1];q1.arry[2][1]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[1][2];q2.arry[1][2]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; whole.push_back(q1);whole.push_back(q2); open.push_back(q1);open.push_back(q2); Sort(open); } if(l==0&&r==2) { q1.arry[l][r]=q1.arry[0][1];q1.arry[0][1]=0; q1.diff=Check_cal(q1.arry);q1.fs=q1.depth+q1.diff; q2.arry[l][r]=q2.arry[1][2];q2.arry[1][2]=0; q2.diff=Check_cal(q2.arry);q2.fs=q2.depth+q2.diff; whole.push_back(q1);whole.push_back(q2); open.push_back(q1);open.push_back(q2); Sort(open); } break; default:cout<<"出错了!亲!"<<endl; }}int main(void){ int num=0,i,j,t=0; int arr[3][3]={0}; cout<<"请输入您的八数码,空格处用0代替,亲!"<<endl; for(i=0;i!=3;i++) for(j=0;j!=3;j++) cin>>arr[i][j]; cout<<"请输入您的目标八数码,空格处用0代替,亲!"<<endl; for(i=0;i!=3;i++) for(j=0;j!=3;j++) cin>>go_l[i][j]; num=Check_cal(arr); QNode q(t,num,arr); open.push_back(q); whole.push_back(q); if(open.empty()) { cout<<"问题无解，失败了,亲"<<endl; return 0; } while(!open.empty()) { begin: closed.push_back(open.front()); //取open表头结点入closed表，并删除open表的头结点 open.pop_front(); if(Check_equ(closed.back())) { cout<<"恭喜亲,找到目标节点,任务完成"<<endl; /*return 0;*/ break; } else { if(!Check_can(closed.back(),whole)) goto begin; Extend(closed.back(),whole); } } cout<<"出结果了亲!"<<endl; cout<<"你输入的起始节点到目标节点需要经过一下步骤"<<endl; for(vector<QNode>::iterator iter=closed.begin();iter!=closed.end();iter++) iter->Display(); return 0;}
[解决办法]
同求高人啊,我调试了一下你的代码,发现错误就是出现在输出路径的循环里,我用全0做输入,发现还是崩了.
[解决办法]
亲，目测一下，你这个是课程设计
[解决办法]
建议用A*吧，网上有资料，主要看下估值函数怎么算就行了，你的程序可能是双向列表使用有错。
双向列表的操作很容易让迭代器失效。
void Sort(deque<QNode> &open) //递增冒泡排序
{
for(int it=0;it!=open.size()-1;it++)
{
for(deque<QNode>::iterator jt=open.begin();jt!=open.end()-it-1;jt++)
{
if(jt->fs>(jt+1)->fs)
jt->Exchange(*(jt+1));
}
}
}
[解决办法]
以前做acm的时候有关于八数码的问题，太长了，看不了
[解决办法]
[解决办法]
哈哈，我们搞机械的，看了这个就眼花头晕！
[解决办法]
你这个8数码写的也太复杂了。。
建议你用“康拓展开”来记录状态。
然后双向BFS搜索。。在搜索之前还要判断是否有解。