本文对八数码问题 启发式搜索 （C++）做了一点点修改
1 //fn=gn+hn 2 3 #include<iostream> 4 #include<queue> 5 #include<stack> 6 7 using namespace std; 8 9 #define num 9 10 11 struct node 12 { 13 int state[9];//当前状态 14 struct node* parent;//父节点 15 int value;//值 16 int depth;//在树中的深度 17 friend bool operator < (node A, node B) //按照value值小的方案构造优先级队列 18 { 19 return A.value > B.value; 20 } 21 }; 22 23 priority_queue<node> openTable; //open表 24 queue<node> closeTable; //close表 25 stack<node> Path; //最终路径 26 27 void init(node& s,node& g) 28 {//初始化 29 s.parent=NULL; 30 s.depth=0; 31 s.value=0; 32 g.parent=NULL; 33 g.depth=0; 34 g.value=0; 35 36 cout<<"please input the init status"<<endl; 37 for(int i=0;i<num;i++) 38 { 39 cin>>s.state[i]; 40 } 41 42 cout<<"please input the target status"<<endl; 43 for(int i=0;i<num;i++) 44 { 45 cin>>g.state[i]; 46 } 47 48 } 49 50 bool isreachable(node s,node g) 51 {//判断目标是否可达。若2个状态的逆序奇偶性相同则可达，不相同则不可达。 52 int count1=0; 53 int count2=0; 54 for(int i=0;i<=num-2;i++) 55 { 56 for(int j=i+1;j<num;j++) 57 { 58 if(s.state[i]>s.state[j]&&s.state[i]*s.state[j]!=0) 59 { 60 count1++; 61 } 62 } 63 } 64 65 for(int i=0;i<=num-2;i++) 66 { 67 for(int j=i+1;j<num;j++) 68 { 69 if(g.state[i]>g.state[j]&&g.state[i]*g.state[j]!=0) 70 { 71 count2++; 72 } 73 } 74 } 75 76 if(count1%2!=count2%2) 77 { 78 return false; 79 } 80 return true; 81 82 } 83 84 int value(node a,node g) 85 {//hn 86 int count=0; 87 for(int i=0;i<num;i++) 88 { 89 if(a.state[i]==0) 90 { 91 continue; 92 } 93 else if(a.state[i]!=g.state[i]) 94 { 95 for(int j=0;j<num;j++) 96 { 97 if(a.state[i]==g.state[j]) 98 { 99 count+=abs(i/3-j/3)+abs(i%3-j%3); 100 } 101 } 102 } 103 } 104 return count+a.depth; 105 } 106 107 bool isequal(node a,node g) 108 {//当前节点是否是目标 109 for(int i=0;i<num;i++) 110 { 111 if(a.state[i]!=g.state[i]) 112 { 113 return false; 114 } 115 } 116 return true; 117 } 118 119 bool createNode(node& a,node g) 120 {//产生新节点，加入open表 121 bool flag=true; 122 /* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */ 123 int blank;//定义空格下标 124 for(blank=0;blank<num;blank++) 125 { 126 if(a.state[blank]==0) 127 { 128 break; 129 } 130 } 131 if(blank==num)return false; 132 int x=blank/3,y=blank%3;//获取空格所在行列编号 133 /*找到S扩展的子节点，加入open表中*/ 134 for(int d=0;d<4;d++) 135 { 136 int newx=x,newy=y;//新空白格坐标 137 node tempnode;//临时节点，子节点 138 139 /*移动空格*/ 140 switch (d) 141 { 142 case 0://向上 143 newx--; 144 if(newx<0)continue; 145 break; 146 case 1://向左 147 newy--; 148 if(newy<0)continue; 149 break; 150 case 2://向下 151 newx++; 152 if(newx>2)continue; 153 break; 154 case 3://向右 155 newy++; 156 if(newy>2)continue; 157 break; 158 159 default: 160 break; 161 } 162 163 /*交换新旧空白格的内容*/ 164 int newblank=newx*3+newy;//新空格下标 165 166 if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) 167 { 168 tempnode=a; 169 tempnode.state[blank]=tempnode.state[newblank]; 170 tempnode.state[newblank]=0; 171 if(a.parent!=NULL&&(*a.parent).state[newblank]==0) 172 {//如果新节点和爷爷节点一样，舍弃该节点 173 continue; 174 } 175 176 /*把子节点都加入open表中*/ 177 tempnode.parent=&a; 178 tempnode.value=value(tempnode,g); 179 tempnode.depth=a.depth+1; 180 openTable.push(tempnode); 181 } 182 } 183 return flag; 184 } 185 186 bool findpath(node s,node g) 187 {//s->g 188 bool flag=true; 189 /*find path*/ 190 openTable.push(s); 191 while(true) 192 { 193 closeTable.push(openTable.top()); 194 openTable.pop(); 195 if(!isequal(closeTable.back(),g)) 196 { 197 flag=createNode(closeTable.back(),g); 198 } 199 else 200 { 201 break; 202 } 203 204 } 205 /*make path*/ 206 node tempnode; 207 tempnode=closeTable.back(); 208 while(tempnode.parent!=NULL) 209 { 210 Path.push(tempnode); 211 tempnode=*(tempnode.parent); 212 } 213 Path.push(tempnode); 214 return flag; 215 } 216 217 void printpath() 218 {//print path s -> g 219 cout<<"move "<<Path.size()-1<<" step"<<endl; 220 while(Path.size()!=0) 221 { 222 for(int i=0;i<num;i++) 223 { 224 cout<<Path.top().state[i]<<" "; 225 if((i+1)%3==0)cout<<endl; 226 } 227 Path.pop(); 228 cout<<endl; 229 } 230 } 231 232 int main() 233 { 234 node s,g; 235 init(s,g); 236 if(!isreachable(s,g)) 237 { 238 cout<<"cannot reach"<<endl; 239 system("pause"); 240 return 0; 241 } 242 else if (!findpath(s,g)) 243 { 244 cout<<"findpath error"<<endl; 245 system("pause"); 246 return 0; 247 } 248 else 249 { 250 printpath(); 251 cout<<"done"<<endl; 252 } 253 system("pause"); 254 return 0; 255 }