数字拼图问题(八数码)用广度优先遍历和深度优先遍历的区别

数字拼图问题，也被称为八数码问题，是一种经典的搜索问题。广度优先遍历和深度优先遍历都可以用来解决这个问题，但它们的实现方式和效率有所不同。

广度优先遍历从起点开始，逐层扩展搜索到的节点，直到找到目标节点。广度优先遍历能够保证找到的是最短路径，但是需要存储每一层的所有节点，因此空间复杂度比较高。在八数码问题中，广度优先遍历通常能够在较短的时间内找到解，但是需要较大的空间开销。

深度优先遍历则是从起点开始，向某一个方向一直搜索下去，直到搜索到底或者找到目标节点。深度优先遍历的空间复杂度比广度优先遍历低，但它不能保证找到的是最短路径。在八数码问题中，深度优先遍历可能会陷入死循环，或者不断地搜索下去而找不到解。

因此，在实际应用中，通常需要根据具体问题的特点来选择使用广度优先遍历还是深度优先遍历。如果需要找到最短路径，则应该选择广度优先遍历；如果空间开销比较重要，则应该选择深度优先遍历。

相关问题

用c++编写用深度优先算法和广度优先算法解决八数码问题

好的，我可以为您讲解一下如何用C++编写用深度优先算法和广度优先算法解决八数码问题。

八数码问题是一种经典的搜索问题，旨在找到一种移动拼图块的方式，以使得初始状态变为目标状态。其中，每个拼图块只能移动到空格上，而且只能沿横向或纵向移动。这个问题可以使用深度优先算法和广度优先算法进行解决。

首先，我们需要定义一个八数码状态的数据结构。一种常见的表示方式是使用一个一维数组来表示状态，其中0表示空格。例如，初始状态[1,2,3,4,0,5,6,7,8]可以表示为：

1 2 3
4   5
6 7 8

接下来，我们可以使用一个搜索树来表示所有可能的状态。搜索树的根节点为初始状态，每个节点表示一个状态，其子节点是通过移动一块得到的所有可能状态。我们可以使用一个队列来实现广度优先算法，或使用递归函数来实现深度优先算法。

下面是一种使用广度优先算法解决八数码问题的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数组来记录状态的前驱节点，以便输出路径。

接下来，我们看一下如何使用深度优先算法解决八数码问题。这个实现中，我们使用了递归函数来实现深度优先搜索。

#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栈来记录路径，以便输出路径。在输出路径时，我们可以从栈顶往栈底依次输出状态。

需要注意的是，八数码问题并不是所有情况下都有解的。如果初始状态与目标状态不可达，则算法会一直搜索下去，直到达到限制深度为止。因此，在实际应用中，需要对问题进行判断，以避免无谓的计算。

用c++实现用有界深度优先搜索解决八数码难题

好的，下面是用 C++ 实现用有界深度优先搜索解决八数码难题的代码：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

const int N = 3; // 拼图块的维度
const int MAX_DEPTH = 50; // 最大搜索深度

struct State {
    int board[N][N]; // 拼图块的当前状态
    int zero_row, zero_col; // 空格的位置
    int depth; // 当前状态的深度
    State *prev; // 前一状态
};

// 判断当前状态是否为目标状态
bool is_goal(State *s) {
    int num = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == N-1 && j == N-1) {
                if (s->board[i][j] != 0) return false;
            } else {
                if (s->board[i][j] != num) return false;
                num++;
            }
        }
    }
    return true;
}

// 复制当前状态
State *copy_state(State *s) {
    State *new_state = new State;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            new_state->board[i][j] = s->board[i][j];
        }
    }
    new_state->zero_row = s->zero_row;
    new_state->zero_col = s->zero_col;
    new_state->depth = s->depth;
    new_state->prev = s->prev;
    return new_state;
}

// 打印出拼图块的状态
void print_state(State *s) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << s->board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// 找到空格可移动的方向
vector<pair<int, int>> get_moves(State *s) {
    vector<pair<int, int>> moves;
    int r = s->zero_row, c = s->zero_col;
    if (r > 0) moves.push_back({r-1, c}); // 上
    if (r < N-1) moves.push_back({r+1, c}); // 下
    if (c > 0) moves.push_back({r, c-1}); // 左
    if (c < N-1) moves.push_back({r, c+1}); // 右
    return moves;
}

// 判断当前状态是否已被访问过
bool is_visited(State *s, unordered_set<State *> &visited) {
    return visited.find(s) != visited.end();
}

// 生成新的状态，返回是否成功
bool generate_new_state(State *s, int r, int c, State *&new_state) {
    new_state = copy_state(s);
    new_state->board[new_state->zero_row][new_state->zero_col] = new_state->board[r][c];
    new_state->board[r][c] = 0;
    new_state->zero_row = r;
    new_state->zero_col = c;
    new_state->depth = s->depth + 1;
    new_state->prev = s;
    return true;
}

// 搜索，返回是否找到解决方案
bool dfs(State *s, int depth, unordered_set<State *> &visited) {
    if (is_goal(s)) {
        return true;
    } else if (depth == 0) {
        return false;
    }
    vector<pair<int, int>> moves = get_moves(s);
    for (auto move : moves) {
        int r = move.first, c = move.second;
        State *new_state = NULL;
        if (generate_new_state(s, r, c, new_state)) {
            if (!is_visited(new_state, visited)) {
                visited.insert(new_state);
                if (dfs(new_state, depth-1, visited)) {
                    return true;
                }
            }
            delete new_state;
        }
    }
    return false;
}

int main() {
    // 初始化拼图块的状态
    State *start = new State;
    start->board[0][0] = 1;
    start->board[0][1] = 2;
    start->board[0][2] = 3;
    start->board[1][0] = 4;
    start->board[1][1] = 0;
    start->board[1][2] = 5;
    start->board[2][0] = 7;
    start->board[2][1] = 8;
    start->board[2][2] = 6;
    start->zero_row = 1;
    start->zero_col = 1;
    start->depth = 0;
    start->prev = NULL;

    unordered_set<State *> visited;
    visited.insert(start);

    for (int depth = 0; depth <= MAX_DEPTH; depth++) {
        if (dfs(start, depth, visited)) {
            cout << "Solution found at depth " << depth << endl;
            State *s = start;
            while (s != NULL) {
                print_state(s);
                s = s->prev;
            }
            return 0;
        }
    }

    cout << "Solution not found within depth " << MAX_DEPTH << endl;
    return 0;
}

在这个实现中，我们首先定义了一个 `State` 结构体，用于保存拼图块的状态和相关信息。然后定义了几个辅助函数，如判断当前状态是否为目标状态、复制当前状态、打印出拼图块的状态、找到空格可移动的方向、判断当前状态是否已被访问过、生成新的状态等。接着，定义了 `dfs` 函数，实现了有界深度优先搜索的过程。最后，在 `main` 函数中，我们初始化了拼图块的状态，并且依次调用 `dfs` 函数来搜索解决方案，直到找到或者超过最大深度限制。如果找到解决方案，我们打印出解决路径，否则打印出未找到解决方案的提示。