启发式搜索8/15数码问题c++源码

1、实验环境 Visual Studio 2019 2、实验目的和要求 ①实验目的：熟悉掌握启发式搜索算法A*及其可采纳性 ②实验要求：编写程序实现8数码和15数码问题，采用至少两种估价函数，分析估价函数求解问题时候的效率差别，分析估价函数对搜索算法的影响 3、解题思路 ①首先，定义一个open表和一个close表用于后续搜索，再定义一个搜索图G，并将初始状态节点放入open表，图G中。 ②其次，对open表按照估价函数进行排序（首次排序其实无意义），由排序后的open表得到最接近目标状态的结点，将该节点取出，若该节点与目标状态一致，则跳转第④步。 ③对由②中找到的结点进行扩展（本题中具体实现为将“0”码向上、下、左、右四个方向移动），并将扩展得到的新节点放入open表和图G中，将扩展结束的结点放入close表中避免再次对其扩展。而后返回第②步。 ④根据每一次扩展后在子节点的结构体中留下的父节点信息（close数组下标），由最终得到的目标状态结点一步步往前回溯，可得到最终解图。