隐式图的搜索问题（解法二：C++代码实现）

柔情只为你懂 2023-10-04 08:07 12阅读 0赞

### 文章目录 ###

*   *  一、实验任务
     *  二、实验要求
     *  三、A\*算法介绍
     *  四、实践操作
     *  五、C++代码实现
     *  六、结果展示
     *  七、附录
     *   *  1.参考文献
         *  2.解法一（Java代码实现）链接

## 一、实验任务 ##

1、对九宫重排问题，建立图的启发式搜索求解方法。

2、用A\*算法求解九宫重排问题。

## 二、实验要求 ##

3х3九宫棋盘，放置数码为1~8的8个棋子，棋盘中留有一个空格，空格周围的棋子可以移动到空格中，从而改变棋盘的布局。根据给定初始布局和目标布局，移动棋子从初始布局到达目标布局，求解移动步骤并输出。请设计算法，使用合适的搜索策略，在较少的空间和时间代价下找到最短路径。

## 三、A\*算法介绍 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]

## 四、实践操作 ##

A算法又称为启发式搜索算法。对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。

在全局择优搜索中，每当需要扩展节点时，总是从 Open 表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下：

把初始节点 S0 放入 Open 表中， f(S0)=g(S0)+h(S0) ；  
如果 Open 表为空，则问题无解，失败退出；  
把 Open 表的第一个节点取出放入 Closed 表，并记该节点为 n ；  
考察节点 n 是否为目标节点。若是，则找到了问题的解，成功退出；  
若节点 n 不可扩展，则转到第 (2) 步；  
扩展节点 n ，生成子节点 ni ( i =1,2, …… ) ，计算每一个子节点的估价值 f( ni ) ( i =1,2, …… ) ，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入 Open 表中；  
根据各节点的估价函数值，对 Open 表中的全部节点按从小到大的顺序重新进行排序；  
转第 (2) 步。  
这里采用的启发式策略为：f(n) = g(n) + h(n)，其中g(n)为从初始节点到当前节点的步数(层数)，h(n)为 当前节点 “不在位 ”的方块数（也就是说不在位的方块数越少，那么临目标状态越近）例如下图中的h(n)=5，有的讲解的是不包含空格，我这里是包含了的，经测试只要前后标准一致，包不包含空格都一样。  
g(n)为已经消耗的实际代价，即已经走了的步数。  
h(n)为预测路径，即还有几个数字待走。

此时：h(n)=5  
启发式策略工作扩展顺序如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]

## 五、C++代码实现 ##

#include <iostream>
    #include <time.h>
    using namespace std;
    
    
    /*
    定义结构体
    */
    struct EightDigital
    {    //存储八数码
    	int status[9];
    	//存储走的是第几步(层数)
    	int G;
    	//存储不在位的格数(作为启发式函数）
    	int H;
    	//存储估价函数的值
    	int F;
    	//存储0数码的位置
    	int Zero;
    	//存储操作符（1左2右3上4下）
    	int step;
    	//父指针
    	EightDigital* Parent;
    };
    
    
    #define MAXLISTSIZE 10000
    #define MAXSTEPSIZE 100
    //声明最终状态
    int FinalStatus[9];
    //定义OPEN表和CLOSE表,open和close是表中最后一个内容的下一位序号
    EightDigital OPEN[MAXLISTSIZE];
    EightDigital CLOSE[MAXLISTSIZE];
    int open = 0;
    int close = 0;
    
    EightDigital* Node;
    
    
    
    
    
    
    /*
    计算不在位的字格数H
    返回 H
    */
    int CountH(int* status)
    {
    	int H = 0;
    	int i;
    	for (i = 0; i <= 8; i++)
    	{
    		if (FinalStatus[i] != status[i])
    		{
    			H++;
    		}
    	}
    	return H;
    }
    
    /*
    判断新生成的节点是否已经存在于OPEN表或CLOSE表中
    返回 表征是否存在于OPEN或CLOSE的值，值为0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表，|值|-1表示所在列表中的位置
    */
    int Exist(EightDigital* N)
    {
    	int i, j;
    	//计算不在位的字格数，如果为0，则证明给函数的节点在表中已存在
    	int H = 0;
    	int status[9];
    
    	Node = new EightDigital;
    	Node = N;
    
    	for (i = 0; i <= 8; i++)
    	{
    		status[i] = Node->status[i];
    	}
    	//判断是否在OPEN表
    	for (i = 0; i <= open - 1; i++)
    	{
    		for (j = 0; j <= 8; j++)
    		{
    			if (status[j] != OPEN[i].status[j])
    			{
    				H++;
    			}
    		}
    		//H=0证明在表中找到该节点
    		if (H == 0)
    		{
    			//如果在OPEN表中，返回i（节点在OPEN的位置）+ 1（在OPEN找到该节点）
    			return i + 1;
    		}
    		//扫描完一个节点后重置H
    		H = 0;
    	}
    	//判断是否在CLOSE表
    	for (i = 0; i <= close - 1; i++)
    	{
    		for (j = 0; j <= 8; j++)
    		{
    			if (status[j] != CLOSE[i].status[j])
    			{
    				H++;
    			}
    		}
    		//H=0证明在表中找到该节点
    		if (H == 0)
    		{
    			//如果在CLOSE表中，返回-i（i为节点在CLOSE的位置）- 1（在CLOSE找到该节点）
    			return (-i) - 1;
    		}
    		//扫描完一个节点后重置H
    		H = 0;
    	}
    
    	return 0;
    }
    
    /*
    初始化节点
    返回 初始化后的节点Node
    */
    EightDigital* EightDigitalInit(int status[10], int zero, int g, EightDigital* parent, int step)
    {
    	int i;
    	Node = new EightDigital;
    	for (i = 0; i <= 8; i++)
    	{
    		Node->status[i] = status[i];
    	}
    	Node->Zero = zero;
    	Node->G = g;
    	Node->H = CountH(Node->status);
    	Node->F = Node->G + Node->H;
    	Node->Parent = parent;
    	Node->step = step;
    	return Node;
    }
    
    /*
    左移后的变化
    返回 左移后的状态
    */
    int* Left(int* s, int z)
    {
    	int temp, i;
    	static int status[9];
    	for (i = 0; i <= 8; i++)
    	{
    		status[i] = s[i];
    	}
    	//左移则是下标减1，需要与前一个位置进行值的交换
    	temp = status[z - 1];
    	status[z - 1] = 0;
    	status[z] = temp;
    	return status;
    }
    
    /*
    右移后的变化
    返回 右移后的状态
    */
    int* Right(int* s, int z)
    {
    	int temp, i;
    	static int status[9];
    	for (i = 0; i <= 8; i++)
    	{
    		status[i] = s[i];
    	}
    	temp = status[z + 1];
    	status[z + 1] = 0;
    	status[z] = temp;
    	return status;
    }
    
    /*
    上移后的变化
    返回 上移后的状态
    */
    int* Up(int* s, int z)
    {
    	int temp, i;
    	static int status[9];
    	for (i = 0; i <= 8; i++)
    	{
    		status[i] = s[i];
    	}
    	temp = status[z - 3];
    	status[z - 3] = 0;
    	status[z] = temp;
    	return status;
    }
    
    /*
    下移后的变化
    返回 下移后的状态
    */
    int* Down(int* s, int z)
    {
    	int temp, i;
    	static int status[9];
    	for (i = 0; i <= 8; i++)
    	{
    		status[i] = s[i];
    	}
    	temp = status[z + 3];
    	status[z + 3] = 0;
    	status[z] = temp;
    	return status;
    }
    
    /*
    判断子节点是否在OPEN或CLOSE中，并进行对应的操作
    返回值 NULL
    */
    void ExistAndOperate(EightDigital* N)
    {
    	int i;
    	//定义表示新生成节点是否在OPEN表或CLOSE表中, 值为0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表
    	int inList;
    	Node = new EightDigital;
    	Node = N;
    	//如果是第一步的节点，直接加入OPEN中，返回
    	if (Node->G == 1)
    	{
    		OPEN[open] = *Node;
    		open++;
    		return;
    	}
    	//判断新节点是否在OPEN或CLOSE中
    	inList = Exist(Node);
    	//如果均不在两个表中，将节点加入OPEN表中
    	if (inList == 0)
    	{
    		//将拓展出的新结点加入到OPEN表中
    		OPEN[open] = *Node;
    		open++;
    	}
    	//如果在OPEN中，说明从初始节点到该节点找到了不同路径，保留耗散值短的那条路径
    	else if (inList > 0)
    	{//如果表内节点F值大于新节点F值，用新节点代替表内节点
    		if (OPEN[inList - 1].F > Node->F)
    		{
    			OPEN[inList - 1] = *Node;
    		}
    	}
    	//如果在CLOSE中，说明初始节点到该节点有两条路径，如果新找到的路径耗散值大，什么都不做，如果较小，将其从CLOSE中取出放入OPEN中    
    	else if (inList < 0)
    	{
    		inList = -inList;
    		//如果较小
    		if (CLOSE[inList - 1].F > Node->F)
    		{//将其取出放入OPEN
    			OPEN[open] = *Node;
    			open++;
    		}
    		//将其在CLOSE中释放
    		for (i = inList - 1; i <= close - 1; i++)
    		{
    			CLOSE[i] = CLOSE[i + 1];
    		}
    		close--;
    	}
    }
    
    /*
    寻找最佳路径函数
    返回 最后的节点Node
    */
    EightDigital* Search()
    {
    	int* status;
    	int i, j;
    
    	EightDigital* Temp;
    	//一直循环知道找到解结束
    	while (1)
    	{
    		Temp = new EightDigital;
    		//用冒泡排序给OPEN表里面的节点按耗散值进行排序
    		for (i = open - 1; i > 0; i--)
    		{
    			for (j = 0; j < i; j++)
    			{//从小到大进行排序
    				if (OPEN[j].F > OPEN[j + 1].F)
    				{//交换值
    					*Temp = OPEN[j + 1];
    					OPEN[j + 1] = OPEN[j];
    					OPEN[j] = *Temp;
    				}
    			}
    		}
    
    		Node = new EightDigital;
    		//从OPEN表中取出第一个元素（F值最小）
    		*Node = OPEN[0];
    		//判断该节点是否是目标节点，若是，则不在位的格数为0，算法结束，若不是，则将该结点进行扩展
    		if (!CountH(Node->status))
    		{
    			break;
    		}
    
    		Temp = Node;
    		//将扩展过的节点放入CLOSE 
    		CLOSE[close] = *Node;
    		close++;
    		//将扩展的节点从OPEN中释放
    		for (i = 0; i <= open - 1; i++)
    		{//相当于是出栈
    			OPEN[i] = OPEN[i + 1];
    		}
    		open--;
    		//如果能左移，则进行左移创造新结点，下标为0，3，6则不能进行左移
    		if ((Temp->Zero) % 3 >= 1)
    		{//创造新结点
    			Node = new EightDigital;
    			//得到新的状态
    			status = Left(Temp->status, Temp->Zero);
    			//初始化新结点
    			Node = EightDigitalInit(status, Temp->Zero - 1, (Temp->G) + 1, Temp, 1);
    			//判断子节点是否在OPEN或CLOSE中，并进行对应的操作
    			ExistAndOperate(Node);
    		}
    		//如果能右移，则进行右移创造新结点 ，下标为2，5，8则不能
    		if ((Temp->Zero) % 3 <= 1)
    		{  //创造新结点
    			Node = new EightDigital;
    			//得到新的状态
    			status = Right(Temp->status, Temp->Zero);
    			//初始化新结点
    			Node = EightDigitalInit(status, Temp->Zero + 1, (Temp->G) + 1, Temp, 2);
    			//判断子节点是否在OPEN或CLOSE中，并进行对应的操作
    			ExistAndOperate(Node);
    		}
    		//如果能上移，则进行上移创造新结点  ，下标为0，1，2则不可以
    		if (Temp->Zero >= 3)
    		{
    			Node = new EightDigital;
    			//得到新的状态
    			status = Up(Temp->status, Temp->Zero);
    			//初始化新结点
    			Node = EightDigitalInit(status, Temp->Zero - 3, (Temp->G) + 1, Temp, 3);
    			//判断子节点是否在OPEN或CLOSE中，并进行对应的操作
    			ExistAndOperate(Node);
    		}
    		//如果能下移，则进行下移创造新结点 ，下标为6，7，8则不可以
    		if (Temp->Zero <= 5)
    		{
    			Node = new EightDigital;                                           //创造新结点
    			status = Down(Temp->status, Temp->Zero);                   //得到新的状态
    			Node = EightDigitalInit(status, Temp->Zero + 3, (Temp->G) + 1, Temp, 4);    //初始化新结点
    			ExistAndOperate(Node);      //判断子节点是否在OPEN或CLOSE中，并进行对应的操作
    		}
    		//如果open=0， 证明算法失败， 没有解
    		if (open == 0)
    			return NULL;
    	}
    	return Node;
    }
    
    /*
    展示具体步骤
    返回 NULL
    */
    void ShowStep(EightDigital* Node)
    {
    	int STEP[MAXSTEPSIZE];
    	int STATUS[MAXSTEPSIZE][9];
    	int step = 0;
    	int i, j;
    	int totalStep = Node->G;
    	while (Node)
    	{
    		STEP[step] = Node->step;
    		for (i = 0; i <= 8; i++)
    		{
    			STATUS[step][i] = Node->status[i];
    		}
    		step++;
    		Node = Node->Parent;
    	} 
    	cout << "                               " << endl;
    	cout << "****总步数为****：" << totalStep << endl;
    	cout << "                               " << endl;
    	for (i = step - 1; i >= 0; i--)
    	{
    		if (STEP[i] == 1)
    			cout << "应向左移动一步" << endl;
    		else if (STEP[i] == 2)
    			cout << "应向右移动一步" << endl;
    		else if (STEP[i] == 3)
    			cout << "应向上移动一步" << endl;
    		else if (STEP[i] == 4)
    			cout << "应向下移动一步" << endl;
    		else if (STEP[i] == 0)
    			cout << "已启动：" << endl;
    		for (j = 0; j <= 8; j++)
    		{
    			cout << STATUS[i][j] << " ";
    			//换行输出
    			if (j == 2 || j == 5 || j == 8)
    				cout << endl;
    		}
    		cout << "                   " << endl;
    	}
    }
    /*
    主函数
    */
    int main()
    {
    	int fstatus[9];
    	int i, beginTime, endTime;
    	EightDigital* FNode;
    	EightDigital* EndNode;
    	//输入初始状态
    	cout << "请输入初始状态：" << endl;
    	for (i = 0; i <= 8; i++)
    	{
    		cin >> fstatus[i];
    	}
    	cout << endl;
    	//输入最终状态
    	cout << "请输入目标状态：" << endl;
    	for (i = 0; i <= 8; i++)
    	{
    		cin >> FinalStatus[i];
    	}
    	beginTime = clock();
    	//判断0数码的位置
    	for (i = 0; i <= 8; i++)
    	{
    		if (fstatus[i] == 0)
    			break;
    	}
    	//获得初始节点
    	FNode = EightDigitalInit(fstatus, i, 0, NULL, 0);
    	//将初始节点放入OPEN中
    	OPEN[open] = *FNode;
    	open++;
    	//寻找最佳路径
    	EndNode = Search();
    
    	if (!EndNode)
    		cout << "抱歉，该目标无法实现!" << endl;
    	else
    		ShowStep(EndNode);                      //展示步骤
    
    	endTime = clock();
    	cout << "本次运行:" << endTime - beginTime << "ms" << endl;
    
    	return 0;
    }

## 六、结果展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 3]

## 七、附录 ##

### 1.参考文献 ###

<1>A*算法的详解一  
[https://www.sogou.com/link?url=hedJjaC291OB0PrGj\_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A…][https_www.sogou.com_link_url_hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A]  
<2>A*算法的详解二  
[https://zhuanlan.zhihu.com/p/45663817][https_zhuanlan.zhihu.com_p_45663817]

### 2.解法一（Java代码实现）链接 ###

[跳转到Java代码实现][Java]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210312182634762.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210312182825712.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210312192809549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210312192856786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[https_www.sogou.com_link_url_hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A]: https://www.sogou.com/link?url=hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A..
[https_zhuanlan.zhihu.com_p_45663817]: https://zhuanlan.zhihu.com/p/45663817
[Java]: https://blog.csdn.net/m0_48170265/article/details/114684274?spm=1001.2014.3001.5501%EF%BC%89