8 puzzle问题 bfs,输入初始状态和最终状态,输出最少移动次数,输出最少移动次数下的移动路径,c++代码
时间: 2024-06-10 14:10:53 浏览: 14
以下是一个基于C语言的8 puzzle问题BFS算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_QUEUE_SIZE 10000
#define MAX_HASH_SIZE 1000000
#define PUZZLE_SIZE 3
typedef struct {
int puzzle[PUZZLE_SIZE][PUZZLE_SIZE];
int space_x, space_y;
int depth;
int prev;
} Puzzle;
Puzzle *queue[MAX_QUEUE_SIZE];
int head = 0, tail = 0;
int hash[MAX_HASH_SIZE];
int hash_count = 0;
int goal[PUZZLE_SIZE][PUZZLE_SIZE] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int get_hash(Puzzle *puzzle) {
int h = 0;
for (int i = 0; i < PUZZLE_SIZE; i++) {
for (int j = 0; j < PUZZLE_SIZE; j++) {
h = h * 10 + puzzle->puzzle[i][j];
}
}
return h % MAX_HASH_SIZE;
}
void enqueue(Puzzle *puzzle) {
queue[tail++] = puzzle;
tail %= MAX_QUEUE_SIZE;
}
Puzzle *dequeue() {
Puzzle *puzzle = queue[head++];
head %= MAX_QUEUE_SIZE;
return puzzle;
}
void init_hash() {
memset(hash, -1, sizeof(hash));
}
void insert_hash(Puzzle *puzzle, int key) {
hash[key] = hash_count++;
}
int get_prev(Puzzle *puzzle) {
return puzzle->prev;
}
int get_depth(Puzzle *puzzle) {
return puzzle->depth;
}
void set_depth(Puzzle *puzzle, int depth) {
puzzle->depth = depth;
}
void set_prev(Puzzle *puzzle, int prev) {
puzzle->prev = prev;
}
int is_goal(Puzzle *puzzle) {
for (int i = 0; i < PUZZLE_SIZE; i++) {
for (int j = 0; j < PUZZLE_SIZE; j++) {
if (puzzle->puzzle[i][j] != goal[i][j]) {
return 0;
}
}
}
return 1;
}
void print_puzzle(Puzzle *puzzle) {
for (int i = 0; i < PUZZLE_SIZE; i++) {
for (int j = 0; j < PUZZLE_SIZE; j++) {
printf("%d ", puzzle->puzzle[i][j]);
}
printf("\n");
}
}
void print_path(Puzzle *puzzle) {
int path[MAX_QUEUE_SIZE];
int path_count = 0;
path[path_count++] = get_prev(puzzle);
while (get_prev(puzzle) != -1) {
puzzle = queue[get_prev(puzzle)];
path[path_count++] = get_prev(puzzle);
}
for (int i = path_count - 1; i >= 0; i--) {
printf("Move %d:\n", path_count - i - 1);
print_puzzle(queue[path[i]]);
}
}
void bfs(Puzzle *puzzle) {
init_hash();
set_depth(puzzle, 0);
set_prev(puzzle, -1);
enqueue(puzzle);
while (head != tail) {
Puzzle *puzzle = dequeue();
int h = get_hash(puzzle);
if (is_goal(puzzle)) {
print_path(puzzle);
return;
}
for (int i = 0; i < 4; i++) {
int x = puzzle->space_x + dx[i];
int y = puzzle->space_y + dy[i];
if (x < 0 || x >= PUZZLE_SIZE || y < 0 || y >= PUZZLE_SIZE) {
continue;
}
Puzzle *new_puzzle = (Puzzle *) malloc(sizeof(Puzzle));
*new_puzzle = *puzzle;
new_puzzle->puzzle[puzzle->space_x][puzzle->space_y] = new_puzzle->puzzle[x][y];
new_puzzle->puzzle[x][y] = 0;
new_puzzle->space_x = x;
new_puzzle->space_y = y;
set_depth(new_puzzle, get_depth(puzzle) + 1);
set_prev(new_puzzle, head - 1);
int new_h = get_hash(new_puzzle);
if (hash[new_h] == -1) {
insert_hash(new_puzzle, new_h);
enqueue(new_puzzle);
} else {
free(new_puzzle);
}
}
}
printf("No solution found.\n");
}
int main() {
Puzzle puzzle;
printf("Enter initial state:\n");
for (int i = 0; i < PUZZLE_SIZE; i++) {
for (int j = 0; j < PUZZLE_SIZE; j++) {
scanf("%d", &puzzle.puzzle[i][j]);
if (puzzle.puzzle[i][j] == 0) {
puzzle.space_x = i;
puzzle.space_y = j;
}
}
}
bfs(&puzzle);
return 0;
}
```
在这个实现中,我们使用了一个队列来存储待扩展的状态,并使用哈希表来避免重复状态的扩展。我们首先将初始状态加入队列,并将其深度设置为0,前驱状态设置为-1。然后在每轮循环中,我们从队列头部取出一个状态进行扩展,然后将其子状态加入队列。如果一个子状态已经在哈希表中出现过了,那么我们就不需要再对它进行扩展了,因为它已经被访问过了。当我们找到一个目标状态时,我们可以通过前驱指针逆序遍历队列,输出移动路径。
如果一个初始状态无法达到目标状态,那么程序会输出"No solution found."。
相关推荐
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)