隐式图的搜索问题

悠悠 2023-10-05 00:56 4阅读 0赞

#  #

### 文章目录 ###

*  
 *   *  一、实验任务：
     *  二、实验要求：
     *  三、A\*算法介绍
     *  四、实践操作

## 一、实验任务： ##

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)为预测路径，即还有几个数字待走。

![在这里插入图片描述][20210303171534677.png]  
此时：h(n)=5  
启发式策略工作扩展顺序如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210303171849469.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[20210303171534677.png]: https://img-blog.csdnimg.cn/20210303171534677.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021030317204772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70