C++八数码问题算法或策略比较[2025-11-17]
·
C++八数码问题算法或策略比较[2025-11-17]
大作业要求
内容
一般要求
大作业 1
1 一般要求
（1）文档部分（含源代码风格）
描述问题。包括：题目、任务、环境、感知、动作、评价标准、算法等。
算法。可以仿照书上的算法。
实验结果。包括细节，例如：统计结果。可以通过图、表等展示。还包括平均或统计结果等。
分析。例如：解的最优性、时间复杂度、空间复杂度、有效分支因子等。
1 一般要求
结论。用几句话、或一个自然段描述。
源代码风格：函数、变量命名是否规范。源代码排版是否合理等。
按照 A4 纸排版（可以一页或多页），签上姓名、学号，打印或手写后交给助教。
教师评分标准：是否全面？是否准确？是否有错别字？是否有错误？表格、图形是否清晰？如果不全面或存在错误、错别字，则扣分较多。
评价：可以仿照学术论文的格式，但是只要骨架即可。
1 一般要求
（2）源代码部分
在助教给出的 VS 项目上完成必须的一个或多个函数。
根据助教给出的输入参数运行程序、并记录运行结果。
在可正确运行后，将自己完成的一个或多个函数打包、提交给助教。
助教针对每个函数至少运行一次，以检查程序的正确性。
评价：要求同学们独立完成。如果有困难，则可以参考其他同学的答案，但是不要抄袭
1 一般要求
评分标准：如果编译不能通过，且是由于同学的错误或失误造成，则没有分数。如果某函数不能执行、或结果错误，则该函数没有分数。
2 大作业 1：八数码问题算法或策略比较
算法 1：广度优先
算法 2：深度有限。深度限定为 5-20
算法 3：启发式搜索。启发式函数采用不正确位置的数码个数
算法 4：启发式搜索。启发式函数采用到目标位置的曼哈顿距离之和。
框架：目标状态，如下图。
2 大作业 1：八数码问题算法或策略比较
起始状态：输入参数回退步数，一般为 backward_moves=5-20 步，框架基于随机数回退。
调试：在屏幕上动态输出移动过程。并最后给出实际移动步数和结果是否正确。例如：forward-moves=7 result=correct 或 wrong。
调试设置：setup=1 广度优先
2 深度有限
3 启发式搜索。启发式函数 1
4 启发式搜索。启发式函数 2
2 大作业 1：八数码问题算法或策略比较
交作业时间：第九周周五之前。电子版源代码发给助教老师，纸质版文档交给助教老师。如果推迟的话，则分数减半，请大家注意。
评分标准：4 个函数，各 2 分。文档：1 分。源代码风格：1 分。一共 10 分。
源码联系UP主 -> https://space.bilibili.com/329101171
eightFigurePuzzles.h代码
#pragma once
#include <iostream>
#include <vector>
using namespace std;
const int puzzleNum = 8;
/*
*描述：记录8数码九宫格内每一个格子对应的位置信息与存放的数码。
* xPosition :行数 0 代表第一行
* yPosition: 列数 0 代表第一行
* puzzleId: 数码 0~8
*/
typedef struct {
int xPosition;
int yPosition;
int puzzleId;
} PUZZLE;
/*
*描述：声明一个节点，存储当前九宫格状态
* 以目标状态为例，puzzle: {{0,0,0},{0,1,1},{0,2,2},
{1,0,3},{1,1,4},{1,2,5},
{2,0,6},{2,1,7},{2,2,8},}
nextActionList: {[1,0] 向上移动
[-1,0] 向下移动
[0,1] 向左移动
[0.-1]} 向右移动
nextAxtionList的大小<=4
depth： 当前状态所处深度
*/
typedef struct {
//vector<PUZZLE> puzzles;
PUZZLE puzzle[9];
vector<vector<int>> nextActionList;
vector<vector<int>> precedeActionList;
int depth;
} PUZZLE_NODE;
/*
* 输入：节点状态puzzleNode
* 输出 空格位置，二维数组。
* 描述：找到 空格 0 所在的位置,返回1个2维数组，分别代表行数和列数;
*/
int* findZeroPosition(PUZZLE_NODE puzzleNode);
/*
*
* 输入：节点状态puzzleNode
* 输出：actionList初始化后的puzzleNode
*描述：更新puzzleNode的后继可操作动作状态，其中 （1，0）代表空格向上移动，（-1，0）代表空格向下移动，（0，1）代表空格向左移动，（0，-1）代表空格向右移动。
*/
PUZZLE_NODE updatePuzzleNodeActionList(PUZZLE_NODE puzzleNode);
/*
* 输入：给定动作数组，例如[1,0],代表空格向上移动
* 输出：puzzleNode在执行完输入动作后得到的新的数码状态
* 描述：给定动作action（action为二维数组）和puzzleNode,返回执行该动作后新的节点
*/
PUZZLE_NODE moveToPuzzleNode(vector<int> action, PUZZLE_NODE puzzleNode);
/*
* 输入：puzzleNode的后继动作数量的大小
* 输出：随机动作索引
* 描述：用于生成PuzzleNode中随机动作索引，用于随机后退。
*/
int getRandomNumber(int actionSize);
/*
* 输入：puzzle1:当前状态某一位置上的状态，puzzle2：目标状态某一位置上的状态
* 输出：true:相等 false:不相等
* 描述：判断当前节点状态和目标节点状态在同一位置上两个8数码状态是否相同。
*/
bool isEqual(PUZZLE puzzle1, PUZZLE puzzle2);
/*
* 输入：当前数码节点状态currentNode，目标数码节点状态objNode
* 输出：两个节点状态是否匹配，如果匹配，说明找到目标状态，返回true;
* 如果不匹配，说明还未找到目标状态，返回false;
*描述：检测当前节点和目标节点状态是否相同。
*/
bool checkObject(PUZZLE_NODE currentNode, PUZZLE_NODE objNode);
/*
* 输入：回退步数
* 输出：给定目标状态回退backwardSteps后的初始状态
* 描述：给定回退步数，返回初始节点状态
*/
PUZZLE_NODE initialPuzzleNode(int backwardSteps);
/*
* 输入：动作
* 输出：给定目标状态回退backwardSteps后的初始状态
* 描述：输出动作
*/
void outputAction(vector<int> action, int index);
//用于生成当前状态对应的唯一数字，用于eightFigureFramework中visited判断当前节点状态是否访问过。
int visitedNum(PUZZLE_NODE puzzleNode);
eightFigurePuzzles.cpp 代码
#include "eightFigurePuzzles.h"
#include <time.h>
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
//找到 空格 0 所在的位置
int* findZeroPosition(PUZZLE_NODE puzzleNode) {
int* res = new int[2]{0, 0};
for (int i = 0; i < puzzleNum + 1; i++) {
if (puzzleNode.puzzle[i].puzzleId == 0) {
res[0] = puzzleNode.puzzle[i].xPosition;
res[1] = puzzleNode.puzzle[i].yPosition;
return res;
}
}
return res;
}
//更新puzzleNode的后继可操作动作状态，其中 （1，0）代表空格向上移动，（-1，0）代表空格向下移动，（0，1）代表空格向左移动，（0，-1）代表空格向右移动。
PUZZLE_NODE updatePuzzleNodeActionList(PUZZLE_NODE puzzleNode) {
int* xyPosition = findZeroPosition(puzzleNode);
int x = xyPosition[0];
int y = xyPosition[1];
delete [] xyPosition;
if (x >= 1) {
vector<int> actionUp;
actionUp.push_back(1);
actionUp.push_back(0);
puzzleNode.nextActionList.push_back(actionUp);
}
if (x <= 1) {
vector<int> actionDown;
actionDown.push_back(-1);
actionDown.push_back(0);
puzzleNode.nextActionList.push_back(actionDown);
}
if (y >= 1) {
vector<int> actionLeft;
actionLeft.push_back(0);
actionLeft.push_back(1);
puzzleNode.nextActionList.push_back(actionLeft);
}
if (y <= 1) {
vector<int> actionRight;
actionRight.push_back(0);
actionRight.push_back(-1);
puzzleNode.nextActionList.push_back(actionRight);
}
return puzzleNode;
}
void outputAction(vector<int> action, int index) {
/*cout << action[0] << " " << action[1] << endl;*/
if (action[0] == 1 && action[1] == 0) {
cout << "步数 " << index << ":向上移动" << endl;
cout << endl;
} else if (action[0] == -1 && action[1] == 0) {
cout << "步数 " << index << "向下移动" << endl;
cout << endl;
} else if (action[0] == 0 && action[1] == 1) {
cout << "步数 " << index << "向左移动" << endl;
cout << endl;
} else {
cout << "步数 " << index << "向右移动" << endl;
cout << endl;
}
}
// 给定动作action（action为二维数组）和puzzleNode,返回执行该动作后新的节点
PUZZLE_NODE moveToPuzzleNode(vector<int> action, PUZZLE_NODE puzzleNode) {
//cout << action[0] << " " << action[1] << endl;
//if (action[0] == 1 && action[1] == 0) {
// cout << "向上移动" << endl;
//}
//else if (action[0] == -1 && action[1] == 0) {
// cout << "向下移动" << endl;
//}
//else if (action[0] == 0 && action[1] == 1) {
// cout << "向左移动" << endl;
//}
//else {
// cout << "向右移动" << endl;
//}
int* xyPosition = findZeroPosition(puzzleNode);
int x = xyPosition[0];
int y = xyPosition[1];
delete [] xyPosition;
PUZZLE_NODE nextPuzzleNode;
for (int xPos = 0; xPos < 3; xPos++) {
for (int yPos = 0; yPos < 3; yPos++) {
nextPuzzleNode.puzzle[xPos * 3 + yPos].xPosition = xPos;
nextPuzzleNode.puzzle[xPos * 3 + yPos].yPosition = yPos;
if (xPos == x && yPos == y) {
nextPuzzleNode.puzzle[xPos * 3 + yPos].puzzleId = puzzleNode.puzzle[((x - action[0]) * 3 + (y - action[1]))].puzzleId;
} else if (xPos == (x - action[0]) && yPos == (y - action[1])) {
nextPuzzleNode.puzzle[xPos * 3 + yPos].puzzleId = puzzleNode.puzzle[(x * 3 + y)].puzzleId;
} else {
nextPuzzleNode.puzzle[xPos * 3 + yPos].puzzleId = puzzleNode.puzzle[xPos * 3 + yPos].puzzleId;
}
}
}
return nextPuzzleNode;
}
// 用于生成PuzzleNode中随机动作索引
int getRandomNumber(int actionSize) {
return rand() % actionSize;
}
//给定回退步数，返回初始状态
PUZZLE_NODE initialPuzzleNode(int backwordSteps) {
PUZZLE_NODE objNode;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
objNode.puzzle[i * 3 + j].puzzleId = i * 3 + j;
objNode.puzzle[i * 3 + j].xPosition = i;
objNode.puzzle[i * 3 + j].yPosition = j;
}
}
PUZZLE_NODE initialPuzzleNode = updatePuzzleNodeActionList(objNode);
srand((unsigned)time(0)); //time()用系统时间初始化种。为rand()生成不同的随机种子。
for (int i = 0; i < backwordSteps; i++) {
PUZZLE_NODE precedePuzzleNode = initialPuzzleNode;
int action = getRandomNumber(initialPuzzleNode.nextActionList.size());
initialPuzzleNode = moveToPuzzleNode(initialPuzzleNode.nextActionList[action], initialPuzzleNode);
initialPuzzleNode = updatePuzzleNodeActionList(initialPuzzleNode);
}
initialPuzzleNode = updatePuzzleNodeActionList(initialPuzzleNode);
return initialPuzzleNode;
}
//判断两个8数码状态是否相同
bool isEqual(PUZZLE puzzle1, PUZZLE puzzle2) {
if (puzzle1.xPosition == puzzle2.xPosition && puzzle1.yPosition == puzzle2.yPosition && puzzle1.puzzleId == puzzle2.puzzleId)
return true;
else
return false;
}
//检测当前节点和目标节点状态是否相同
bool checkObject(PUZZLE_NODE currentNode, PUZZLE_NODE objNode) {
for (int i = 0; i < puzzleNum + 1; i++) {
if (!isEqual(currentNode.puzzle[i], objNode.puzzle[i]))
return false;
}
return true;
}
//判断当前节点状态是否被访问过。
int visitedNum(PUZZLE_NODE puzzleNode) {
int mapValue = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
mapValue = mapValue * 10 + puzzleNode.puzzle[i * 3 + j].puzzleId;
}
}
return mapValue;
}
eightFigurePuzzlesFramework.cpp 代码
#include <time.h>
#include <windows.h>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include "eightFigurePuzzles.h"
using namespace std;
//用于记录当前状态是否被访问过。
map<int, int> visited;
//深度有限搜索，用于限制深度。
#define MAX_DEPTH 20
//openList与closeList用于A*搜索。
vector<PUZZLE_NODE> closeList;
vector<PUZZLE_NODE> openList;
//广度优先搜索
int* binaryFirstSearch(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode) {
//result[0] 1:correct;0:wrong
//result[1] 步数 steps
int* result = new int[2]{0, 0};
/*
请在该位置完成广度优先搜索。
*/
if (checkObject(initialNode, objPuzzleNode)) {
result[0] = 1;
} else {
result[0] = 0;
}
return result;
}
//深度有限搜索
int* depthFirstSearch(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode) {
//result[0] 1:correct;0:wrong
//result[1] 步数 steps
int* result = new int[2]{0, 0};
/*
请在该位置完成深度有限搜索，最大深度限度为25。
*/
if (checkObject(initialNode, objPuzzleNode) && initialNode.depth < MAX_DEPTH) {
result[0] = 1;
} else {
result[0] = 0;
}
return result;
}
//启发式搜索1
int* heuristicSearchInformedByIncorrectNum(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode) {
//result[0] 1:correct;0:wrong
//result[1] 步数 steps
int* result = new int[2]{0, 0};
/*
请在该位置完成启发式搜索，启发式函数使用不正确位置的数码个数。
*/
if (checkObject(initialNode, objPuzzleNode)) {
result[0] = 1;
} else {
result[0] = 0;
}
return result;
}
//启发式搜素2
int* heuristicSearchInformedByManhattonDis(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode) {
//result[0] 1:correct;0:wrong
//result[1] 步数 steps
int* result = new int[2]{0, 0};
/*
请在该位置完成启发式搜索，启发式函数采用到目标位置的曼哈顿距离。
*/
if (checkObject(initialNode, objPuzzleNode)) {
result[0] = 1;
} else {
result[0] = 0;
}
return result;
}
//广度优先搜索
int* binaryFirstSearchDemo(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode) {
//result[0] 1:correct;0:wrong
//result[1] 步数 steps
int* result = new int[2]{0, 0};
cout << "初始节点状态：" << endl;
for (int i = 0; i < 3; i++) {
cout << " " << initialNode.puzzle[i * 3 + 0].puzzleId << " " << initialNode.puzzle[i * 3 + 1].puzzleId << " " << initialNode.puzzle[i * 3 + 2].puzzleId << endl;
}
cout << endl;
/*
请在该位置完成广度优先搜索函数。
*/
PUZZLE_NODE puzzleNode = initialNode;
queue<PUZZLE_NODE> puzzleNodeQueue;
puzzleNode.depth = 0;
int depth = 0;
puzzleNodeQueue.push(puzzleNode);
while (puzzleNodeQueue.size()) {
PUZZLE_NODE currentPuzzleNode = puzzleNodeQueue.front();
if (checkObject(currentPuzzleNode, objPuzzleNode)) {
for (int i = 0; i < currentPuzzleNode.precedeActionList.size(); i++) {
outputAction(currentPuzzleNode.precedeActionList[i], i + 1);
}
cout << "找到正确结果:" << endl;
for (int i = 0; i < 3; i++) {
cout << " " << currentPuzzleNode.puzzle[i * 3 + 0].puzzleId << " " << currentPuzzleNode.puzzle[i * 3 + 1].puzzleId << " " << currentPuzzleNode.puzzle[i * 3 + 2].puzzleId << endl;
}
cout << endl;
result[0] = 1;
result[1] = currentPuzzleNode.depth;
return result;
} else {
visited[visitedNum(currentPuzzleNode)] = 1;
if (currentPuzzleNode.nextActionList.size() == 0) {
currentPuzzleNode = updatePuzzleNodeActionList(currentPuzzleNode);
}
puzzleNodeQueue.pop();
for (int i = 0; i < currentPuzzleNode.nextActionList.size(); i++) {
PUZZLE_NODE nextPuzzleNode = moveToPuzzleNode(currentPuzzleNode.nextActionList[i], currentPuzzleNode);
if (!currentPuzzleNode.precedeActionList.empty()) {
for (int actionIndex = 0; actionIndex < currentPuzzleNode.precedeActionList.size(); actionIndex++) {
nextPuzzleNode.precedeActionList.push_back(currentPuzzleNode.precedeActionList[actionIndex]);
}
}
nextPuzzleNode.precedeActionList.push_back(currentPuzzleNode.nextActionList[i]);
if (visited[visitedNum(nextPuzzleNode)] == 1) {
continue;
}
nextPuzzleNode.depth = currentPuzzleNode.depth + 1;
puzzleNodeQueue.push(nextPuzzleNode);
}
}
}
return result;
}
int main() {
PUZZLE_NODE objPuzzleNode;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
objPuzzleNode.puzzle[i * 3 + j].puzzleId = i * 3 + j;
objPuzzleNode.puzzle[i * 3 + j].xPosition = i;
objPuzzleNode.puzzle[i * 3 + j].yPosition = j;
}
}
objPuzzleNode = updatePuzzleNodeActionList(objPuzzleNode);
int setup = 0;
while (setup != -1) {
visited.clear();
cout << "请输入调试设置(-1:退出; 0:广度优先搜索示例;1:广度优先搜索;2：深度有限搜索;3:启发式搜索1;4:启发式搜索2):" << endl;
cin >> setup;
int backwardSteps;
cout << "请输入大于等于5小于等于20的回退步数" << endl;
cin >> backwardSteps;
while (backwardSteps < 5 || backwardSteps > 20) {
cout << "输入错误，请输入大于等于5小于等于20的回退步数" << endl;
cin >> backwardSteps;
}
PUZZLE_NODE initialNode = initialPuzzleNode(backwardSteps);
int* result;
if (setup == 1) {
result = binaryFirstSearch(initialNode, objPuzzleNode);
} else if (setup == 2) {
result = depthFirstSearch(initialNode, objPuzzleNode);
} else if (setup == 3) {
result = heuristicSearchInformedByIncorrectNum(initialNode, objPuzzleNode);
} else if (setup == 4) {
result = heuristicSearchInformedByManhattonDis(initialNode, objPuzzleNode);
} else if (setup == 0) {
cout << "广度优先搜索示例程序" << endl;
result = binaryFirstSearchDemo(initialNode, objPuzzleNode);
} else {
cout << "输入设置有误，请重新运行" << endl;
return 0;
}
if (result[0] == 1) {
cout << "结果为correct,步数为" << result[1] << endl;
} else {
cout << "结果为wrong" << endl;
}
delete [] result;
}
return 0;
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
8
0- 0
已为社区贡献15条内容
所有评论(0)