八数码问题广度优先C++
时间: 2023-12-04 12:04:09 浏览: 35
八数码问题是指在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字,另外一个格子为空格。空格周围的棋子可以移到空格中。给出一种初始布局和目标布局,找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。广度优先搜索是一种解决八数码问题的常用算法,它可以保证找到最短路径。C++是一种常用的编程语言,可以用来实现八数码问题的算法。通过C++实现广度优先搜索算法,可以方便地输入和输出八数码问题的起始状态和终止状态,并找到最短路径。
相关问题
C++用广度优先搜索解决八数码问题
八数码问题是一道经典的搜索问题,可以使用广度优先搜索进行求解。这里给出一个使用 C++ 实现的八数码问题的广度优先搜索算法。
```c++
#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;
const int N = 3; // 数码的行列数
const int M = N * N; // 数码的总个数
// 定义状态结构体
struct State {
string s; // 数码串
int x, y; // 0 的坐标
int step; // 步数
string path; // 路径
bool operator==(const State& t) const {
return s == t.s;
}
// 计算哈希值
size_t hash() const {
return std::hash<string>()(s);
}
};
// 定义哈希表
struct HashTable {
size_t operator()(const State& t) const {
return t.hash();
}
bool operator()(const State& a, const State& b) const {
return a == b;
}
};
// 定义移动数组:上下左右四个方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char direction[] = {'u', 'd', 'l', 'r'};
// 判断是否合法状态
bool valid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
// 计算下标
int get_index(int x, int y) {
return x * N + y;
}
// 初始化状态
State init_state() {
string s;
int x = 0, y = 0;
cout << "请输入八数码初始状态(0 表示空格):" << endl;
for (int i = 0; i < M; i++) {
int x;
cin >> x;
if (x == 0) {
x = N - 1;
y = N - 1;
} else {
x--;
y = i % N;
}
s += to_string(x * N + y); // 将坐标转化为数字串
}
return {s, x, y, 0, ""};
}
// 打印状态
void print_state(const State& state) {
for (int i = 0; i < M; i++) {
int x = state.s[i] / N;
int y = state.s[i] % N;
cout << state.s[i] << " ";
if (y == N - 1) {
cout << endl;
}
}
cout << "步数:" << state.step << endl;
cout << "路径:" << state.path << endl;
}
// 判断是否为目标状态
bool is_target(const State& state) {
return state.s == "012345678";
}
// 搜索八数码
void bfs(State start) {
queue<State> Q; // 存放状态的队列
unordered_set<State, HashTable, HashTable> vis; // 存放已访问的状态的哈希表
Q.push(start); // 将起点加入队列
vis.insert(start); // 标记起点已被访问
while (!Q.empty()) { // 只要队列不空,就一直搜索
State t = Q.front(); // 取出队首状态
Q.pop(); // 弹出队首状态
for (int i = 0; i < 4; i++) { // 枚举四个方向
int x = t.x + dx[i];
int y = t.y + dy[i];
if (valid(x, y)) { // 如果移动后的坐标合法
int j = get_index(x, y);
State next = t;
swap(next.s[j], next.s[get_index(t.x, t.y)]); // 移动数码
next.x = x;
next.y = y;
next.step++;
next.path += direction[i]; // 记录路径
if (!vis.count(next)) { // 如果移动后的状态没有被访问过
Q.push(next); // 将状态加入队列
vis.insert(next); // 标记状态已被访问
if (is_target(next)) { // 如果找到目标状态,输出结果
cout << "找到目标状态:" << endl;
print_state(next);
return;
}
}
}
}
}
cout << "无解" << endl;
}
int main() {
State start = init_state();
bfs(start);
return 0;
}
```
在这个实现中,我们定义了一个状态结构体,包含了数码串、0 的坐标、步数和路径。我们使用一个哈希表来存放已访问的状态,使用一个 queue 存放待搜索的状态。首先,我们从起点开始搜索,将起点加入队列并标记为已访问。然后,只要队列不空,就不断取出队首状态 t 并枚举四个方向。如果移动后的坐标合法,我们就可以得到移动后的状态 next,计算该状态的哈希值并查看是否已经被访问过。如果没有被访问过,我们将该状态加入队列并标记为已访问。如果找到目标状态,我们就输出结果并结束搜索。如果队列为空,说明无解。
广度优先搜索实现八数码 c++
好的,以下是广度优先搜索实现八数码的 C++ 代码:
```c++
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <string>
using namespace std;
const int N = 3; // 3x3 的矩阵
struct Node
{
string state; // 当前状态
int step; // 当前步数
int x, y; // 空格的位置
bool operator<(const Node& t) const
{
return state < t.state;
}
};
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
// 判断当前状态是否为目标状态
bool is_target(string state)
{
string target = "123456789";
target += '0' + N * N;
return state == target;
}
// 获取当前状态的下一步状态
vector<string> get_next_state(string state, int x, int y)
{
vector<string> res;
// 枚举空格的四个方向
for (int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= N || b < 0 || b >= N) continue;
swap(state[x * N + y], state[a * N + b]);
res.push_back(state);
swap(state[x * N + y], state[a * N + b]);
}
return res;
}
int bfs(string start)
{
queue<Node> q;
map<string, int> dist;
// 初始化起点
int x = 0, y = 0;
for (int i = 0; i < N * N; ++i)
if (start[i] == '0')
{
x = i / N, y = i % N;
break;
}
q.push({ start, 0, x, y });
dist[start] = 0;
while (!q.empty())
{
auto t = q.front();
q.pop();
if (is_target(t.state)) return t.step;
auto next_states = get_next_state(t.state, t.x, t.y);
for (auto& s : next_states)
if (!dist.count(s))
{
dist[s] = t.step + 1;
int x = 0, y = 0;
for (int i = 0; i < N * N; ++i)
if (s[i] == '0')
{
x = i / N, y = i % N;
break;
}
q.push({ s, t.step + 1, x, y });
}
}
return -1; // 无解
}
int main()
{
string start = "123456789";
start += '0' + N * N;
cout << bfs(start) << endl;
return 0;
}
```
该代码中,我们使用了 `struct Node` 表示状态,其中包含了当前状态的字符串表示 `state`、当前步数 `step`,以及空格的位置 `x`、`y`。
我们使用了 STL 中的 `queue` 表示队列,`map` 表示哈希表,`vector` 表示动态数组。
函数 `is_target` 判断当前状态是否为目标状态,函数 `get_next_state` 获取当前状态的下一步状态,函数 `bfs` 表示广度优先搜索算法。
在 `main` 函数中,我们定义了起点状态 `start`,并调用 `bfs` 函数进行搜索,最终输出结果。
需要注意的是,在本算法中,我们使用了哈希表 `map` 来判断当前状态是否已经访问过。同时,我们使用了 STL 中的 `swap` 函数来交换字符串中两个字符的位置。