2025年人工智能-八数码问题-宽度优先搜索

科技前沿 • 2025-03-05 20:24 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

第一个难点在于怎样判断当前状态是否已经遍历过，可以把每一种状态映射为字符串，如果该状态遍历过了，就将<该状态对应的字符串，1>加入到 map 中，每次需要判断该状态是否遍历过的时候直接使用 map 搜索 value 的值是否存在就可以。更近一步地，可以直接把 vector<int>作为 map 的第一个值，也不需要将状态转化为字符串，直接比较判断就可以，极大地简化了代码。

第二个难点在于保存移动路线，输出结果需要走完每一步的状态，所以保存路线是必须的。在结构体中保存状态数组、移动路线数组和深度，每一个新的状态的步骤就是上一个状态的步骤加上当前的移动步骤，在得到结果后按照当前状态中存储的移动路线输出即可。

讯享网

#include<bits/stdc++.h> using namespace std; struct state{ vector<int>now; //当前的状态数组 vector<int>steps; //当前已经走过的步骤记录 int deep; //深度 }; int step[4]={-3,-1,1,3}; //移动路线 vector<int>start_state,end_state; //初态和终态 map<vector<int>,int>vis; //标记状态 int find_(vector<int>a){ //找到0的位置 for(int i=0;i<9;i++) if(a[i]==0)return i; } void print_matrix(vector<int>a){ //打印矩阵 printf("%d %d %d\n%d %d %d\n%d %d %d\n\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]); } void print(state t){ //打印结果 vector<int>k=start_state; printf("initial\n"); print_matrix(k); for(int i=0;i<t.steps.size();i++){ int index=find_(k); swap(k[index+t.steps[i]],k[index]); printf("step %d\n",i+1); print_matrix(k); } } bool check(int index,int k){ //判断该步是否可以移动 if(k==-3&&(index==3||index==4||index==5||index==6||index==7||index==8))return 1; if(k==-1&&(index==1||index==2||index==4||index==5||index==7||index==8))return 1; if(k==1&&(index==0||index==1||index==3||index==4||index==6||index==7))return 1; if(k==3&&(index==0||index==1||index==2||index==3||index==4||index==5))return 1; return 0; } int main() { for(int i=0;i<9;i++) { //读入初态 int x;cin>>x; start_state.push_back(x); } for(int i=0;i<9;i++) { //读入终态 int x;cin>>x; end_state.push_back(x); } bool flag=0; //标记是否找到结果 vector<int>k; //把第一个状态加入到空队列中 state t; t.now=start_state;t.steps=k;t.deep=0; queue<state>q; q.push(t); vis[start_state]=1; //将初态标记为已经遍历过 while(!q.empty()){ t=q.front(); if(t.now==end_state){ //判断是否得到结果 flag=1; print(t); break; } if(t.deep>10){ //深度>10,结束搜索 break; } else{ int index=find_(t.now); for(int i=0;i<4;i++){ if(check(index,step[i])){ state s; s.now=t.now; s.steps=t.steps; s.deep=t.deep+1; swap(s.now[index],s.now[index+step[i]]); s.steps.push_back(step[i]); if(!vis.count(s.now)){ q.push(s); vis[s.now]=1; } } } } q.pop(); } if(!flag)printf("no answer\n"); return 0; } /* 3 1 2 4 0 5 6 7 8 0 1 2 3 4 5 6 7 8 */

讯享网

2025年人工智能-八数码问题-宽度优先搜索

相关推荐