启发式搜索--八数码问题_针对八数码问题,采用不同的启发函数,如下计算结果描述正确的() 若初始状态s0的八

今日看笔记，发现--->

---

• 什么是启发式搜索？ChatGPT给出回答

启发是一种解决问题的方法，这种方法通过尝试来证明结果，是“凭经验”或“试错法”的一种学习方式。好的启发式方法不能保证获得解，但是它们经常有助于引导人们达到解的路径。

• 如何用启发式搜素解决问题？

利用启发式信息提供线索来帮助自己搜索方向，启发式信息按照形式有两种：估计函数和规则

表示为估计函数

确定一个启发式函数f(n),n 为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径

---

• 八数码问题

问题描述：在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，可以实现从初始布局到目标布局的转变。如图表示：

注：左边为初始布局，右边为目标布局

• 第一步构造一个启发式函数，构造的函数能够估计已找到的状态与达到目标之间的有利程度，假设启发式函数为f1=数字放错位置的个数 ；若f1=0，则表示达到目标

• 第二步判断有那些位置可以移动到空格，计算启发式函数值，选择最小值的路径，直到达到目标

1. 解析：由初始状态知到，可以移动的数字有5 6 7 ，由此得到三个函数值，通过比较，发现移动6的时候函数值最少，即数字在正确的位置个数最多，因此选择移动6；

2. 到达第二步之后，我们发现可以移动的数字有1 4 6 8四个，分别计算启发式函数值，结果发现移动8和移动1二者的函数值相同，那怎么办呢？

3. 起初我们定义了一个启发式函数f1,接下来我们定义f2=所有数字在当前位置以最短路径走到正确位置的步数之和；在当前状态下，计算所有数字的启发式函数值，如下：

数码 1 2 3 4 5 6 7 8

函数值 f2(S0）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5

f2(S1）= 1 + 1 +0 +0 + 0 + 0 +0 + 2 =4

f2(S2）= 1 + 1 +0 +0 + 0 + 1 +1 + 2 =6

f2(S3）= 1 + 1 +0 +0 + 1 + 1 +0 + 2 =6

f2(S4）= 1 + 1 +0 +0 + 0 + 0 +0 + 1 =3

f2(S5）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5

f2(S6）= 1 + 2 +0 +0 + 0 + 0 +0 + 2 =5

4. 通过计算，虽然f1(S4)=f1(S6)=3,但是f2(S4)<f2(S6),所以下一步搜索从S4出发，重复这个过程，直到达到目标布局