八个数字问题实验报告
. 《八数码问题》实验报告
首先，实验的目的:
熟悉启发式搜索算法。
二、实验内容:
启发式搜索算法用于解决8位数问题。
编制了程序，实现了解决8位数问题的算法。
采用评估功能，其中:
是搜索树中节点的深度；
在节点数据库中放错位置的件数；
这是每个棋子与其在节点数据库中的目标位置之间距离的总和。
三、实验原理:
1.问题描述:
八位数问题也被称为九宫问题。
在3×3的棋盘上，有八个棋子，每一个棋子都标有一定的1到8的数字，不同棋子上标的数字是不同的。
棋盘上还有一个空格(用数字0表示)，与空格相邻的棋子可以移动到空格中。
要解决的问题是: 给定初始状态和目标状态，找出从初始状态到目标状态移动次数最少的移动步骤。
所谓问题的一种状态是棋盘上棋子的排列。
解决八位数问题实际上是找出一系列从初始状态到目标状态的中间过渡状态。
2.原则描述:
启发式搜索(1)原理启发式搜索是评估每个搜索在状态空间中的位置以获得最佳位置，然后从这个位置搜索到目标。
这样，可以省略大量不必要的搜索路径，并且提高了效率。
在启发式搜索中，位置的评估非常重要。
不同的评估会产生不同的效果。
(2)评估函数计算节点的评估函数，可分为两部分:
1.成本已经支付(从开始节点到当前节点)；
2.要支付的价格(当前节点到目标节点)。
节点n的评估函数被定义为从初始节点通过n到目标节点的路径的最小成本的估计值，即=。
是从初始节点到达当前节点n的实际成本；
是从节点n到目标节点的最佳路径的估计开销。
比例越大，它越倾向于先搜索宽度或同等成本。
相反，比例越大，启发式性能越强。
(3)算法描述:
(1)将起始节点S放入OPEN表中，计算节点S的值；
(2)如果OPEN为空表，则无法退出且没有解决方案；
(3)从OPEN表中选择具有最小值的节点。
如果多个节点具有相同的值，当其中一个节点是目标节点时，选择目标节点；
否则，任意一个节点被选为节点；
(4)从OPEN表中移除节点，并将其放入CLOSED扩展节点表中；
(5)如果它是目标节点，它成功退出并获得解决方案；
⑥扩展节点以生成其所有后续节点。
对于以下每个后续节点:
计算；
如果它既不在“打开”表中，也不在“时钟”表中，则通过评估功能将其添加到“打开”表中。
在中添加指向其父节点的指针，以便在找到目标节点后记住解决方案路径；
如果它已经在OPEN表或CLOSED表中，则比较表中刚刚计算的和先前计算的节点值。
如果新值较小，(I)用新值替换旧值。
(二)从其父节点指向，而不是指向其父节点。
(三)如果节点在封闭表中，将其移回开放表。
⑦转向②，即GOTO②。
(3)算法流程图:
四、实验结果输入矩阵:
目标矩阵:
283123145804760765
5.通过这个实验，我对启发式搜索有了更深的理解。
在实验中，通过两次启发式搜索扩展的节点数，似乎比启发式搜索更有效，并且在复杂情况下可以获得更好的解，避免不必要的节点扩展。
因此，如何更好地定义一个评价函数还需要进一步讨论。
源代码: #include'stdio.h'#define num 3 //宏定义编号的行数和列数为3/*以显示当前要调整的数字矩阵*/void show (intbed-
首先，实验的目的:
熟悉启发式搜索算法。
二、实验内容:
启发式搜索算法用于解决8位数问题。
编制了程序，实现了解决8位数问题的算法。
采用评估功能，其中:
是搜索树中节点的深度；
在节点数据库中放错位置的件数；
这是每个棋子与其在节点数据库中的目标位置之间距离的总和。
三、实验原理:
1.问题描述:
八位数问题也被称为九宫问题。
在3×3的棋盘上，有八个棋子，每一个棋子都标有一定的1到8的数字，不同棋子上标的数字是不同的。
棋盘上还有一个空格(用数字0表示)，与空格相邻的棋子可以移动到空格中。
要解决的问题是: 给定初始状态和目标状态，找出从初始状态到目标状态移动次数最少的移动步骤。
所谓问题的一种状态是棋盘上棋子的排列。
解决八位数问题实际上是找出一系列从初始状态到目标状态的中间过渡状态。
2.原则描述:
启发式搜索(1)原理启发式搜索是评估每个搜索在状态空间中的位置以获得最佳位置，然后从这个位置搜索到目标。
这样，可以省略大量不必要的搜索路径，并且提高了效率。
在启发式搜索中，位置的评估非常重要。
不同的评估会产生不同的效果。
(2)评估函数计算节点的评估函数，可分为两部分:
1.成本已经支付(从开始节点到当前节点)；
2.要支付的价格(当前节点到目标节点)。
节点n的评估函数被定义为从初始节点通过n到目标节点的路径的最小成本的估计值，即=。
是从初始节点到达当前节点n的实际成本；
是从节点n到目标节点的最佳路径的估计开销。
比例越大，它越倾向于先搜索宽度或同等成本。
相反，比例越大，启发式性能越强。
(3)算法描述:
(1)将起始节点S放入OPEN表中，计算节点S的值；
(2)如果OPEN为空表，则无法退出且没有解决方案；
(3)从OPEN表中选择具有最小值的节点。
如果多个节点具有相同的值，当其中一个节点是目标节点时，选择目标节点；
否则，任意一个节点被选为节点；
(4)从OPEN表中移除节点，并将其放入CLOSED扩展节点表中；
(5)如果它是目标节点，它成功退出并获得解决方案；
⑥扩展节点以生成其所有后续节点。
对于以下每个后续节点:
计算；
如果它既不在“打开”表中，也不在“时钟”表中，则通过评估功能将其添加到“打开”表中。
在中添加指向其父节点的指针，以便在找到目标节点后记住解决方案路径；
如果它已经在OPEN表或CLOSED表中，则比较表中刚刚计算的和先前计算的节点值。
如果新值较小，(I)用新值替换旧值。
(二)从其父节点指向，而不是指向其父节点。
(三)如果节点在封闭表中，将其移回开放表。
⑦转向②，即GOTO②。
(3)算法流程图:
四、实验结果输入矩阵:
目标矩阵:
283123145804760765
5.通过这个实验，我对启发式搜索有了更深的理解。
在实验中，通过两次启发式搜索扩展的节点数，似乎比启发式搜索更有效，并且在复杂情况下可以获得更好的解，避免不必要的节点扩展。
因此，如何更好地定义一个评价函数还需要进一步讨论。
源代码:
# include ' stdio . h ' # define num 3//宏定义编号的行数和列数为3/*以显示要调整的当前数字矩阵*/void show (intbed:'，i1，J1)；scanf(“% d”，temp)；对于(int q=0；q=i节点==1；Q) //当输入值重复时，提示重新输入(int w=0；w . j .w)如果(temp==begin[q][w]) {printf('重复输入，请重新输入\ n ')；节点=0；j-；休息；}如果(temp num*num-1) //当输入的值不在数字范围内时，提示重新输入{printf('请输入一个从%d到%d \n '的数字，零，num*num-1 );节点=0；j-；}如果(node==1) //如果输入满足条件{如果(temp==0) //如果输入值为零，行号由空白[0记录]，列号由空白[1记录]{空白[0]=I；空白[1]=j；开始[I][j]=temp；//存储满足条件的值}}} intmain () {intjishu=0，Ji _ Shu[50][3][3]；//姬叔存储已遍历的八个数字图形的数量，姬叔[][][] []存储已遍历的八个数字图形的形状int行；//存储数字零的列中的行数；//存储数字零整数[数][数]，空白[2]，计数=1的列数；整数结束[数][数]={1，2，3，8，0，4，7，6，5 }；//在最终状态下将PRINTF(-% d)分配给数字矩阵。
数字游戏开始了！- \n '，num)；shuru(开始，空白)；//输入具有调整状态的数字矩阵的值行=空白[0]；栏=空白[1]；如果(idong(开始，结束，判断(开始，结束)，姬叔，ji _ shu，4，行，列)==0)printf(' \ n 8
位数问题可能无法解决！)；否则显示(开始)；getchar()；getchar()；返回0；}文字模型。