人工智能作业-八皇后问题求解算法设计与实现+源代码+文档说明

这是一个八皇后问题求解算法设计与实现的作业 ## 编译运行 ``` mkdir build cd build cmake .. make ./bhh ``` ## 1.整体技术路线 本次作业首先分别创建了两个类，一个完成深度优先算法类名为DFS，一个完成广度优先算法类名为BFS。 在深度优先算法中，首先创建一个带参构造函数传入棋盘的大小。 接着创建Solve函数作为算法的启动函数，在启动函数中使用构造函数传入的参数N，创建了一个向量储存容器board并使容量为N，并将内部数据全部设置为-1。 接着创建一个check函数检查放置的皇后是否符合规则。然后创建一个printBoard函数用来输出棋盘。 接着创建solve函数来进行问题的解决。首先创建一个一个if语句使递归调用到棋盘的最后的时候能够输出棋盘的大小。通过不断地递归调用solve函数来向下拓展节点。每个节点到底的时候将会输出节点。 在广度优先算法中，首先创建一个带参构造函数传入棋盘的大小。 通过队列来逐层搜索解空间。初始状态是一个空棋盘，将其入队。然后，在循环中，不断从队列中取出状态，找到下一个空行，并尝试在该行的每一列放置皇后，确保没有冲突。 如果找到了一种放置方式，就将这个新状态入队，然后在回溯前重置当前行的皇后位置，以便继续搜索其他可能性。 当队列为空时，所有可能的解都已经探索完毕，算法结束。在算法的主循环中，如果找到一个解，则调用 printBoard 函数打印该解。 ## 2.开发环境简介 操作系统：Ubuntu 22.04 语言版本 ：C++17 编辑器：Clion 2023.2.1 编译器环境：GUN 11.4.0 构建工具：Cmake 3.22.1 ## 3.程序软件设计 ### 1.状态图节点的数据结构设计 状态图结构实现使用了vector来表示每一行皇后的摆放的状态。 ### 2.队列的数据结构设计 使用queue实现了队列数据结构设计。 ## 4.程序软件实现 ### 1.深度优先搜索的实现 ``` void DFS::solve(vector<int> &board, int row) { if (row == N) { // 找到一个解，打印棋盘 printBoard(board); return; } for (int col = 0; col < N; col++) { if (check(board, row, col)) { board[row] = col; // 在当前行的col列放置皇后 solve(board, row + 1); // 递归到下一行 board[row] = -1; // 回溯，重置当前行的皇后位置 } } } ``` ### 2.广度优先搜索的实现 ``` void BFS::Solve() { queue<vector<int>> q; // 创建队列用于BFS q.push(vector<int>(N, -1)); // 初始化队列，将一个N大小的向量入队，-1表示空行 while (!q.empty()) { vector<int> board = q.front(); // 从队列中取出一个棋盘状态 q.pop(); // 将取出的状态出队 int row = 0; while (row < N && board[row] != -1) { row++; // 寻找空行 } if (row == N) { // 找到一个解，打印棋盘 printBoard(board); } else { for (int col = 0; col < N; col++) { if (check(board, row, col)) { board[row] = col; // 在当前行的col列放置皇后 q.push(board); // 将新状态入队 board[row] = -1; // 回溯，重置当前行的皇后位置 } } } } } ``` ## 5.其他改进设计 无 ## 6.设计体会和收获 我学会了函数的递归调用，以及深度优先搜索的实现，广度优先搜索的实现。