八数码问题（经典）
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。
给出一种初始状态S0和目标状态Sg，请找到一种最少步骤的移动方法，实现从初始状态S0到目标状态Sg的转变。*
输入
输入测试次数t
对于每次测试，首先输入一个初始状态S0，一行九个数字，空格用0表示。然后输入一个目标状态Sg，一行九个数字，空格用0表示。
输出
只有一行，该行只有一个数字，表示从初始状态S0到目标状态Sg需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入
2
283104765
123804765
283104765
283164705
样例输出
4
1
思路
对于八数码问题，我们可以向下面一样去搜索，一层一层去搜索
这一道八数码问题是一道非常有意思的题目，第一种方法毫无疑问就是单向的BFS，用单向的BFS不断往下进行搜索，直到搜索到末态，输出结果
这里用了一个map去存储步数，代码如下
单向BFS
#include<iostream> #include<string> #include<queue> #include<algorithm> #include<map> using namespace std; int dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };//x,y的移动 int main() { int t; cin >> t; while (t--) { long long start, end; cin >> start >> end;//输入 map<long long,long long>m;//用一个map去存储步数 m[start] = 0;//设置开始步数为0 queue<long long> q; q.push(start);//将开始的数据压入队列 while (!q.empty())//开始搜索 { long long u = q.front();//得到当前搜索的状态 q.pop(); long long n = u; if (u == end) break;//当前搜索状态为最终状态，退出循环 int f = 0, g = 0, c[3][3]; for (int i = 2; i >= 0; i--) for (int j = 2; j >= 0; j--) { c[i][j] = n % 10;//将整数转数组 n /= 10; if (!c[i][j]) { f = i, g = j; }//得到0所在的位置 } for (int i = 0; i < 4; i++) { int nx = f + dx[i], ny = g + dy[i], ns = 0;//nx与ny为0移动后的坐标 if (nx < 0 || ny < 0 || nx>2 || ny>2) continue;//越界则不搜 swap(c[nx][ny], c[f][g]);//交换位置 for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) ns = ns * 10 + c[i][j];//将数组转为整数 if (!m.count(ns))//若不存在ns，或者说m[ns]为0，这样的话就对ns进行操作 //若本身存在也不对其进行操作，因为题目求的是最少步数 { m[ns] = m[u] + 1;//当前步数+1 q.push(ns);//压入队列继续搜索 } swap(c[nx][ny], c[f][g]);//记得一定要交换位置回来继续返回原来位置的搜索 } } cout << m[end] << endl;//输出end状态的步数 } return 0; }
优化
再者，除了单向搜索，在我们已经知道末态的结果下，我们是否可以进行双向BFS，由于单向搜索可能允许到后面会时间超限，我就想到了可以运用双向的BFS进行操作，可以看上面的图两边都进行搜索，如果搜索到了同一个节点，说明得到了一个连通的路，最后末态搜索的步数和从初态搜索的步数就是最后的步数，得出最终的答案
双向BFS对于大数据的搜索树来说是比单向的BFS优很多的，代码也如下
双向BFS
#include<iostream> #include<queue> #include<map> using namespace std; int dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };//x,y的移动 int main() { int t; cin >> t; while (t--) { bool flag = false;//标志 queue<int> q; map<int, int> v;//map v表示每种状态的搜索的方向，向上和向下 map<int, int> ans;//map ans表示达到每种状态的最少步数 int s, e; cin >> s >> e; if (s == e) { cout << '0' << endl; continue;//若初态和末态相同，则可以说明步数为0 } q.push(s), q.push(e);//起始状态与终止状态同时入队 v[s] = 2; v[e] = 1;//将两个方向标记成不同的数字 ans[s] = 0, ans[e] = 1;//初始化ans while (!q.empty())//开始搜索 { int cur = q.front(); //得到当前的搜索状态 q.pop(); int fx = 0, fy = 0, c[3][3], now = cur; for (int i = 2; i >= 0; i--) for (int j = 2; j >= 0; j--) { c[i][j] = now % 10;//数字转数组 now /= 10; if (!c[i][j]) { fx = i, fy = j; }//得到0的位置 } for (int i = 0; i < 4; i++) { int nx = dx[i] + fx, ny = dy[i] + fy; if (nx < 0 || ny < 0 || nx>2 || ny>2) continue;//越界 swap(c[nx][ny], c[fx][fy]);//交换数据 int ns = 0; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) ns = ns * 10 + c[i][j]; if (v[ns] == v[cur]) //方向相同 { swap(c[fx][fy], c[nx][ny]);//一定要先换回来再跳过 continue; } if (v[ns] + v[cur] == 3)//说明新延伸出的点已被另一方向访问过 //或者说得到了双向BFS的同一节点 { cout << ans[cur] + ans[ns] << endl;//两方向步数和即为总步数 flag = true;//找到了标志为true break; } ans[ns] = ans[cur] + 1;//步数为当前步数+1 v[ns] = v[cur];//与当前的方向相同 q.push(ns); swap(c[fx][fy], c[nx][ny]);//重新换回来 } if (flag == true) break;//标志为true，退出循环 } } return 0; }
骑士
题目描述
国际象棋中骑士的走法如图所示。
请计算给定骑士在棋盘上的起点，走到终点所需最少步数。
输入
每个测试包括一行，为用空格隔开的起点和终点。每个点由字母表示的列+数字表示的行组成。
输出
最少步数
样例输入
e2 e4
a1 b2
b2 c3
a1 h8
样例输出
2
4
2
6
思路
这道题同样可以用单搜，第一次遇到末态的步数即为最少步数，所以我们需要定义一个数组，判断点是否访问过，因为只有第一次访问到的才是最短的步数
单向BFS
#include<cstdlib> #include<cstdio> #include<iostream> #include<string> #include<algorithm> #include<map> #include<queue> #include<string.h> using namespace std; struct node//定义一个节点 { int x, y, step;//坐标与步数 }o; queue <node> q; bool vis[8][8];//vis表示点是否被访问过 int dx[8] = { -1,1,-1,1,-2,2,-2,2 },dy[8] = { -2,2,2,-2,-1,1,1,-1 };//x,y的移动 int main() { string a, b; while (cin>>a&&a[0]!=EOF)//只要有输入 { cin >>b; //分别得到输入的坐标 x1.y1 x2,y2 int x1 = a[0] - 'a' + 1, x2 = b[0] - 'a' + 1, y1 = a[1] - '0', y2 = b[1] - '0'; memset(vis, false, sizeof(vis));//将vis数组全初始化为false vis[x1][y1] = true;//定义初始节点已访问过 node temp;//定义多一个temp节点进行下面的中间变换 temp.x = x1, temp.y = y1, temp.step = 0;//初始化坐标与步数 q.push(temp);//压入队列 while (!q.empty()) { o = q.front();//得到当前状态的节点 q.pop(); if (o.x == x2 && o.y == y2) //若与末状态相同，则直接退出当前循环 { cout << o.step << endl;//输出当前的步数 break; } for (int i = 0; i < 8; i++) { int x = o.x + dx[i], y = o.y + dy[i];//对于当前的移动 if (x <= 0 || x>8 || y <= 0 || y>8) continue;//越界 if (vis[x][y]) continue;//若已经访问过，则不做操作 vis[x][y] = true;//设置为x，y已访问 node temp; temp.x = x, temp.y = y, temp.step = o.step + 1;//存储坐标与当前步数 q.push(temp); } } while (!q.empty()) q.pop();//由于q为全局变量，所以首先要将q对数据全部删除再进行下一步操作 } return 0; }
当然，这道题也同样是可以运用双向BFS可以更快来得到答案
双向BFS
#include<queue> #include<iostream> #include<string> using namespace std; struct horse//定义一个马的结构体 { int x, y, step;//存储坐标和步数 }st,ed,temp; int dx[8] = { -1,1,-1,1,-2,2,-2,2 }, dy[8] = { -2,2,2,-2,-1,1,1,-1 };//x,y的移动 bool vis[8][8];//vis表示点是否被访问过 int dis[10][10];//用dis来存储步数 int bfs() { if (st.x == ed.x&&st.y == ed.y) return 0;//如果初始状态与末态状态一样，则返回0 queue<horse> q1;//正向搜索 queue<horse> q2;//反向搜索 vis[st.x][st.y] = 1;//1代表正方向 vis[ed.x][ed.y] = 2;//2代表反方向 //起始状态访问的节点记为1，结束状态的记为2 //当某一状态的队列拓展节点时 //若vis为0，则标记为自己队列的 //若已被另一状态的队列标记，则意味着出现重合 q1.push(st), q2.push(ed); int fx, fy, xx, yy; while (true)//进行双向BFS搜索 { if (q1.size() < q2.size()) { fx = q1.front().x; fy = q1.front().y; int t = q1.front().step; q1.pop(); //当前q1的节点少，取q1的节点 for (int i = 0; i < 8; i++) { xx = fx + dx[i]; yy = fy + dy[i]; if (xx < 1 || xx>8 || yy < 1 || yy>8) continue;//越界 if (vis[xx][yy] == 0) { temp.step = t + 1; temp.x = xx, temp.y = yy; q1.push(temp); vis[xx][yy] = 1; //没访问过，标记1表示q1 dis[xx][yy] = temp.step; } else if (vis[xx][yy] == 2) { return dis[xx][yy] + t + 1;//q2曾访问过这，q1目前访问这，即重合 } } } else { fx = q2.front().x; fy = q2.front().y; int t = q2.front().step; q2.pop(); //同样的，这里q2的节点少，取q2的队首 for (int i = 0; i < 8; i++) { xx = fx + dx[i]; yy = fy + dy[i];//越界 if (xx < 1 || xx>8 || yy < 1 || yy>8) continue; if (vis[xx][yy] == 0) { temp.step = t + 1; temp.x = xx; temp.y = yy; q2.push(temp); vis[xx][yy] = 2; dis[xx][yy] = temp.step; } else if (vis[xx][yy] == 1) { return dis[xx][yy] + t + 1;//q1曾访问过,q2目前访问过，即重合 } } } } } int main() { string a, b; while (cin >> a && a[0] != EOF) { cin >> b; int x1 = a[0] - 'a' + 1, x2 = b[0] - 'a' + 1, y1 = a[1] - '0', y2 = b[1] - '0'; memset(vis, false, sizeof(vis)); memset(dis, 0, sizeof(dis)); st.x = x1, st.y = y1; ed.x = x2, ed.y = y2; int path = bfs(); cout << path << endl; } }
再次优化
除了这种双向广搜，其实用启发式搜索，也就是A*算法可以更快得到答案，这才是最好的，也是当今人工智能常用的一个搜索方法
可以运用A*算法，下面是A*算法的一些概述
A*算法概述：
采用广度优先搜索策略，在搜索过程中使用启发函数，即有大致方向的向前进虽然目标有时候不是很明确。
A*算法核心：
A*算法的关键在于启发函数，启发函数的优劣直接影响A*算法的效率。
f(n)=g(n)+h(n);
这个式子中：
f(n)表示从初始状态到目标状态的估测代价。
g(n)表示从初始状态到当前状态的代价（已经确定）。
h(n)表示从当前状态到目标状态的估测代价(预测）。
其中：h(n)的好坏直接影响评估函数的好坏。
一个好的f(n)总能明确指引算法前进的方向，可以迅速的到达目标状态。
f*(n)=g*(n)+h*(n); 我们假设的从初始状态到目标状态的实际最小代价。
这个式子中：f(n)表示从初始状态到目标状态的实际代价。
g*(n)表示从初始状态到当前状态的代价（已经确定）g*(n)和g(n)是相等的。
h*(n)表示从当前状态到目标状态的实际代价。
若h(n)<=h*(n),则总能找到最优解。（当h(n)<h*(n)的时候，不可能找到一条从初始状态到达目标状态的路径。在搜索过程中使得h(n)逐渐接近h*(n)，最终找到最优路径。
优点：
与广度优先搜索策略和深度优先搜索策略相比，A*算法不是盲目搜索，而是有提示的搜索。
缺点：
该算法一般要使用大量的空间用于存储已搜索过的中间状态，防止重复搜索。
用途：
从初始状态出发 =>经过一系列中间状态 =>最终到达目标状态（或者无法到达）。
该算法用于经过中间状态时候的行进策略（其中的中间状态或者由题目给出，或者在前边已经推导得出）。
IDA∗ 算法：即迭代加深 AA∗ 算法，可以有效的解决 AA∗ 空间增长带来的问题，甚至可以不用到优先级队列。因为我不会 所以不再赘述。
详细可以看A*算法与IDA*算法
介绍完A*算法以后，我们来看看这道题如何进行操作
首先进行估价函数的设计，这个估计就是启发式的。在寻路问题和迷宫问题中，我们通常用曼哈顿（manhattan）估价函数预估费用。这一估价值我们通常用字母 HH 表示。
H 值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目标格之间的曼哈顿距离乘以 10 。
另外，因为我们寻找的是最短路，那么估价函数应取最小值，所以我们就要用优先队列来维护。当然不要忘了重载自定义节点的比较操作符。
然后搞清楚这些以后，我们就可以开始进行搜索啦
1.首先，将起点压入优先队列，寻找起点周围所有可到达的方格，并把他们加入队列。将所有这些方格的“父方格”设为起点。
2.从队列中弹出起点，并检查所有在队列中的节点，选取 F 值最小的进行搜索。（详见代码）
3.重复以上过程直到终点被加入队列。
最后，代码如下
A*算法
#include <iostream> #include <queue> #include <string> using namespace std; int dx[8] = { -1,1,-1,1,-2,2,-2,2 }, dy[8] = { -2,2,2,-2,-1,1,1,-1 };//x,y的移动 int ans; bool vis[8][8]; int xx1, yy1, xx2, yy2; struct node { int x, y, step, g, h, f; bool operator < (const node & u)const { //为优先队列重载运算符 return f > u.f; } }k; priority_queue<node>q; bool check(node u) { //判是否出界 if (u.x < 0 || u.y < 0 || u.x >= 8 || u.y >= 8)return 0; return 1; } int gujia(node u) { //估价函数 return (abs(u.x - xx2) + abs(u.y - yy2)) * 10; } void astar() { //A*算法 while (!q.empty()) { node u = q.top(); q.pop(); vis[u.x][u.y] = 1; if (u.x == xx2 && u.y == yy2) { ans = u.step; break; } for (int i = 0; i < 8; i++) { node v; v.x = u.x + dx[i], v.y = u.y + dy[i]; if (check(v) && !vis[v.x][v.y]) { //计算当前点的位置与函数 v.g = u.g + 23; //取23的原因是骑士每走一步都是2*1的，23=根号5乘以十再向上取整 v.h = gujia(v); v.f = v.g + v.h; v.step = u.step + 1; q.push(v); } } } } int main() { string a, b; while (cin>>a>>b) { xx1 = a[0] - 'a', yy1 = a[1] - '1'; xx2 = b[0] - 'a', yy2 = b[1] - '1'; memset(vis, 0, sizeof vis);//初始化vis为0代表都没访问过 k.x = xx1, k.y = yy1, k.g = k.step = 0, k.h = gujia(k), k.f = k.g + k.h; while (!q.empty())q.pop(); //多组数据须清空队列 q.push(k); astar(); cout << ans << endl; } return 0; }
过河问题（十分有意思）
题目描述
多个囚犯参与者要过河，其中只有监管者一人可以划船。小船每次最多载两人过河。监管者不在时，已有积怨的囚犯可能会斗殴。请问他们该如何安全过河？
假设一开始所有人都在河的左岸，用0表示，如果成功过河，则到达河的右岸，用1表示。
请采用BFS求解，并输出过河过程。
输入
首先输入要过河的人数n（包括监管者和囚犯）
接着输入监管者的编号s（假设每个人的编号从0开始,编号最小的在最右边）
然后输入有积怨的囚犯的对数m
接下来m行，两两输入有积怨的囚犯编号
输出
如有解，输出划船过河方案，即每一步的状态，也就是每个人此时在河的左岸还是右岸。初始状态全部为0。
否则，输出No solution
样例输入
4
3
2
0 1
1 2
样例输出
0000
1010
0010
1011
0001
1101
0101
1111
思路
这道题思路也是广搜BFS，注意这道题不一样的地方就是序号是从右到左的，如果从左到右进行广搜会得到不一样的答案。思路大概就是从右到左进行广搜，首先判断会不会打架，打架就剪枝了，不打架就继续搜索，最后搜索到末态，最后将路径全部输出。
BFS
#include<iostream> #include<string> #include<queue> #include<map> #include<stack> using namespace std; int a[100], b[100]; int n, s, m; struct node//定义当前的一个节点 { stack<string> path;//定义一个栈来储存路径 string s;//当前状态 }tmp; inline void flip(char &c)//类似于硬币的翻转，0变1，1变0 { if (c == '0') c='1'; else c = '0'; } inline bool fight(string str)//判断是否会打架 { for(int i=0;i<m;i++) if (str[n-s-1] == str[n-a[i]-1] && str[n-a[i]-1] == str[n-b[i]-1]) return false;//不会打架 else if (str[n - a[i] - 1] == str[n - b[i] - 1]) return true;//会打架 return false;//不会打架 } int main() { cin >> n >> s >> m; for (int i = 0; i < m; i++) cin >> a[i] >> b[i]; string st, ed; for (int i = 0; i < n; i++) { st += '0'; ed += '1';//st全为0,ed全为1 } queue <node> q; tmp.s = st; tmp.path.push(st);//初始化，将初始状态压入队列 q.push(tmp); string str; while (!q.empty()) { str = q.front().s;//得到当前的状态 stack<string> p = q.front().path;//得到当前的路径 q.pop(); tmp.path = p; if (p.size() >= 100) //若路径的值大于100，可以近似认为搜索100层都没有找到路径 //可能路径不存在，输出no solution { cout << "No solution" << endl; return 0; } if (str == ed) {//若与末状态相同，则输出 //由于栈的特性是先进先出，所以我讲栈里面的元素压入到另一个栈内 //最后将栈的数据输出，则为路径 stack<string> temp; while (!p.empty()) { temp.push(p.top()); p.pop(); } while (!temp.empty()) { cout << temp.top() << endl;//输出路径 temp.pop(); } return 0; } flip(str[n - s - 1]);//监管者肯定过河 for (int i = n - 1; i >= 0; i--) { if (i == n -s -1)//只有监管者过河 { if (fight(str)) continue;//会出现争执，不做操作 tmp.s = str; tmp.path.push(str); q.push(tmp);//压入队列 tmp.path.pop(); continue; } if (str[n - s - 1] == str[i]) continue;//囚犯要与监管者在同一边才能过河 flip(str[i]);//囚犯过河 if (fight(str)) {//如果过河后，会出现打架的情况，说明情况不可行 flip(str[i]); continue;//则返回开始状态，进行下一步搜索 } tmp.s = str;//得到当前状态 tmp.path.push(str);//将路径压入栈中 q.push(tmp);//压入栈中 tmp.path.pop(); flip(str[i]);//返回原先的状态，进行下一步搜索 } } cout << "No solution" << endl;//无解 return 0; }
优化
对于上面的代码，我个人在debug时发现一个问题，如果是00000->00001->00000这种路径是存在的，也就是说，在搜索的时候，会碰到之前搜索过的路径，然后我在搜索的过程中，先判断路径中是否有重合的，若重合了，说明搜索重复了，为了去掉多余的搜索，则直接删除掉。最后的结果是一样的，但是时间几乎减少了一半，并且空间的利用也更优了，nice！
（又菜又爱思考）
后面仔细想了想，其实就是一个剪枝的过程，是否可以用一个map或者是一个数组来表示状态是否被搜索过，因为再搜索重复路径的过程中，可能会耗费时间。可以判断这个点是否被访问过进行剪枝，如果访问过了，那就可以进行剪枝，这样应该会比我的代码更加快一点，可是我懒得打了，就这样吧哈哈哈，希望有点帮助。（我觉得应该可以实现，类似于前面的题）
#include<iostream> #include<string> #include<queue> #include<map> #include<stack> using namespace std; int a[100], b[100]; int n, s, m; struct node//定义一个节点 { stack<string> path;//存储路径 string s;//存储当前的状态 }tmp; inline void flip(char &c)//类似于硬币的翻转，0变1，1变0 { if (c == '0') c='1'; else c = '0'; } inline bool fight(string str)//进行判断是否会打架 { for(int i=0;i<m;i++) if (str[n-s-1] == str[n-a[i]-1] && str[n-a[i]-1] == str[n-b[i]-1]) return false;//不会打架 else if (str[n - a[i] - 1] == str[n - b[i] - 1]) return true;//会打架 return false;//不会打架 } int main() { cin >> n >> s >> m; for (int i = 0; i < m; i++) cin >> a[i] >> b[i]; string st, ed; for (int i = 0; i < n; i++) { st += '0'; ed += '1';//st全为0,ed全为1 } queue <node> q; tmp.s = st; tmp.path.push(st); q.push(tmp);//将当前状态压入队列 string str; int count = 0; while (!q.empty()) { bool flag = 1; str = q.front().s; stack<string> p = q.front().path; q.pop(); tmp.path = p; if (p.size() >= 100) { cout << "No solution" << endl; return 0; } if (str == ed) { stack<string> temp; while (!p.empty()) { temp.push(p.top()); p.pop(); } while (!temp.empty()) { cout << temp.top() << endl; temp.pop(); } return 0; } if (p.size()>=3) { p.pop(); while (!p.empty()) { if (p.top() == str) { flag = false; break; } p.pop(); } } if (flag == false) continue; flip(str[n - s - 1]);//监管者肯定过河 for (int i = n - 1; i >= 0; i--) { if (i == n -s -1)//只有监管者过河 { if (fight(str)) continue;//会出现争执 tmp.s = str; tmp.path.push(str); q.push(tmp); tmp.path.pop(); continue; } if (str[n - s - 1] == str[i]) continue;//要与监管者在同一边 flip(str[i]); if (fight(str)) { flip(str[i]); continue;} tmp.s = str; tmp.path.push(str); q.push(tmp); tmp.path.pop(); flip(str[i]); } } cout << "No solution" << endl; return 0; }
最后，终于搞完了，累，送给大家一句话吧！
人生没有一劳永逸，想要不被抛弃，必须自己争气。
