用C++写一个分支限界法求解数码问题的代码
时间: 2023-11-15 07:05:47 浏览: 53
以下是一个用C++实现的分支限界法求解数码问题的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 3;
const int MAXSTATE = 1000000;
int state[MAXSTATE][MAXN];
int dist[MAXSTATE];
int goal[MAXN][MAXN] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
struct Node {
int s[MAXN][MAXN];
int x, y; // 空格的位置
int f, g, h;
bool operator<(const Node& rhs) const {
return f > rhs.f;
}
};
int get_dist(int s[MAXN][MAXN]) {
int res = 0;
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
if (s[i][j] != 0) {
res += abs(i - (s[i][j] - 1) / MAXN) + abs(j - (s[i][j] - 1) % MAXN);
}
}
}
return res;
}
int state_id(int s[MAXN][MAXN]) {
int res = 0, p = 1;
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
state[res][i] = s[i][j];
res += p * s[i][j];
p *= MAXN * MAXN;
}
}
return res;
}
void print_state(int s[MAXN][MAXN]) {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
cout << s[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void print_ans(Node& node) {
if (dist[state_id(node.s)] == -1) {
cout << "No solution." << endl;
} else {
vector<Node> ans;
while (!(node.x == -1 && node.y == -1)) {
ans.push_back(node);
int t = node.g - 1;
node = Node();
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
node.s[i][j] = state[t][i * MAXN + j];
if (node.s[i][j] == 0) {
node.x = i;
node.y = j;
}
}
}
}
for (int i = ans.size() - 1; i >= 0; i--) {
print_state(ans[i].s);
}
}
}
void astar(int s[MAXN][MAXN]) {
memset(dist, -1, sizeof(dist));
priority_queue<Node> q;
Node start;
memcpy(start.s, s, sizeof(start.s));
start.x = start.y = 0;
start.g = 0;
start.h = get_dist(s);
start.f = start.g + start.h;
q.push(start);
while (!q.empty()) {
Node node = q.top();
q.pop();
int id = state_id(node.s);
if (dist[id] != -1) continue;
dist[id] = node.g;
if (memcmp(node.s, goal, sizeof(node.s)) == 0) {
print_ans(node);
return;
}
for (int dir = 0; dir < 4; dir++) {
int nx = node.x + dx[dir], ny = node.y + dy[dir];
if (nx < 0 || nx >= MAXN || ny < 0 || ny >= MAXN) continue;
Node next = node;
swap(next.s[node.x][node.y], next.s[nx][ny]);
next.x = nx;
next.y = ny;
next.g++;
next.h = get_dist(next.s);
next.f = next.g + next.h;
q.push(next);
}
}
}
int main() {
int s[MAXN][MAXN] = {{2, 3, 0}, {1, 8, 4}, {7, 6, 5}};
astar(s);
return 0;
}
```
在这个示例代码中,我们使用8数码问题作为例子,使用A*算法来求解。其中,我们使用了一个状态数组`state`来记录每个状态对应的数字排列,使用一个`dist`数组来记录每个状态到起始状态的距离。在`get_dist`函数中,我们使用曼哈顿距离来计算当前状态到目标状态的距离。在`state_id`函数中,我们将数字排列转换成一个唯一的整数表示,方便后续处理。在`astar`函数中,我们通过不断扩展当前状态的方式来搜索最优解,直到找到目标状态或者无解为止。在搜索过程中,我们使用一个优先队列来维护当前状态的扩展顺序,每次选取最优状态进行扩展。最后,我们使用`print_ans`函数来输出解的路径。