用c++编写用深度优先算法和广度优先算法解决八数码问题
时间: 2023-07-31 17:06:21 浏览: 167
好的,我可以为您讲解一下如何用C++编写用深度优先算法和广度优先算法解决八数码问题。
八数码问题是一种经典的搜索问题,旨在找到一种移动拼图块的方式,以使得初始状态变为目标状态。其中,每个拼图块只能移动到空格上,而且只能沿横向或纵向移动。这个问题可以使用深度优先算法和广度优先算法进行解决。
首先,我们需要定义一个八数码状态的数据结构。一种常见的表示方式是使用一个一维数组来表示状态,其中0表示空格。例如,初始状态[1,2,3,4,0,5,6,7,8]可以表示为:
```
1 2 3
4 5
6 7 8
```
接下来,我们可以使用一个搜索树来表示所有可能的状态。搜索树的根节点为初始状态,每个节点表示一个状态,其子节点是通过移动一块得到的所有可能状态。我们可以使用一个队列来实现广度优先算法,或使用递归函数来实现深度优先算法。
下面是一种使用广度优先算法解决八数码问题的C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 9;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
struct State {
int a[N];
int pos;
int steps;
};
bool check(const State& s) {
for (int i = 0; i < N; i++) {
if (s.a[i] != i) return false;
}
return true;
}
void print(const State& s) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << s.a[i * 3 + j] << " ";
}
cout << endl;
}
cout << endl;
}
int bfs(const State& start) {
queue<State> q;
vector<State> vis;
q.push(start);
vis.push_back(start);
while (!q.empty()) {
State s = q.front();
q.pop();
if (check(s)) return s.steps;
for (int i = 0; i < 4; i++) {
int nx = s.pos / 3 + dx[i], ny = s.pos % 3 + dy[i];
if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
State t = s;
swap(t.a[s.pos], t.a[nx * 3 + ny]);
t.pos = nx * 3 + ny;
t.steps++;
bool ok = true;
for (int i = 0; i < vis.size(); i++) {
if (vis[i].pos == t.pos && vis[i].a == t.a) {
ok = false;
break;
}
}
if (ok) {
q.push(t);
vis.push_back(t);
}
}
}
return -1;
}
int main() {
State start;
for (int i = 0; i < N; i++) {
cin >> start.a[i];
if (start.a[i] == 0) start.pos = i;
}
start.steps = 0;
cout << bfs(start) << endl;
return 0;
}
```
这个实现中,我们定义了一个State结构体来表示八数码状态,其中a数组存储状态,pos表示空格位置,steps表示移动步数。check函数用于判断是否到达目标状态,print函数用于输出状态。
在bfs函数中,我们使用一个队列q和一个vector vis来实现广度优先搜索。每次从队列中取出一个状态,尝试通过移动一块来得到所有可能的状态,然后将未访问过的状态加入队列中。如果已经访问过,则不再加入队列。
这个实现中,我们使用了一个check函数来判断是否到达目标状态,但实际上也可以在枚举状态时直接判断。另外,我们可以使用一个pre数组来记录状态的前驱节点,以便输出路径。
接下来,我们看一下如何使用深度优先算法解决八数码问题。这个实现中,我们使用了递归函数来实现深度优先搜索。
```c++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int N = 9;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
struct State {
int a[N];
int pos;
int steps;
};
bool check(const State& s) {
for (int i = 0; i < N; i++) {
if (s.a[i] != i) return false;
}
return true;
}
void print(const State& s) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << s.a[i * 3 + j] << " ";
}
cout << endl;
}
cout << endl;
}
bool dfs(const State& s, int depth, int limit, vector<State>& vis, stack<State>& path) {
if (check(s)) {
while (!path.empty()) {
print(path.top());
path.pop();
}
print(s);
return true;
}
if (depth + s.steps > limit) return false;
for (int i = 0; i < 4; i++) {
int nx = s.pos / 3 + dx[i], ny = s.pos % 3 + dy[i];
if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
State t = s;
swap(t.a[s.pos], t.a[nx * 3 + ny]);
t.pos = nx * 3 + ny;
t.steps++;
bool ok = true;
for (int i = 0; i < vis.size(); i++) {
if (vis[i].pos == t.pos && vis[i].a == t.a) {
ok = false;
break;
}
}
if (ok) {
vis.push_back(t);
path.push(t);
if (dfs(t, depth + 1, limit, vis, path)) return true;
path.pop();
}
}
return false;
}
int iddfs(const State& start) {
vector<State> vis;
stack<State> path;
for (int limit = 0; ; limit++) {
vis.clear();
path.push(start);
vis.push_back(start);
if (dfs(start, 0, limit, vis, path)) return limit;
path.pop();
}
return -1;
}
int main() {
State start;
for (int i = 0; i < N; i++) {
cin >> start.a[i];
if (start.a[i] == 0) start.pos = i;
}
start.steps = 0;
cout << iddfs(start) << endl;
return 0;
}
```
这个实现中,我们定义了一个dfs函数来实现深度优先搜索,并使用一个limit参数来控制搜索深度。在dfs函数中,我们首先判断当前状态是否为目标状态,如果是,则输出路径并返回true。否则,如果当前深度加上移动步数已经超过了限制,则返回false。然后,我们枚举所有可能的状态,并判断是否已经访问过,如果未访问过,则递归调用dfs函数。如果递归调用返回true,则表示已经找到了目标状态,否则需要弹出当前状态。
在iddfs函数中,我们使用一个循环来不断增加限制,直到找到目标状态或搜索到最大深度为止。
这个实现中,我们使用了一个vis数组来记录已经访问过的状态,以便避免重复访问。另外,我们使用了一个path栈来记录路径,以便输出路径。在输出路径时,我们可以从栈顶往栈底依次输出状态。
需要注意的是,八数码问题并不是所有情况下都有解的。如果初始状态与目标状态不可达,则算法会一直搜索下去,直到达到限制深度为止。因此,在实际应用中,需要对问题进行判断,以避免无谓的计算。
阅读全文
相关推荐















