1.搜索问题

考试方式：解决八数码问题，解题要求出从初态->目态的路径，有如下考查算法：

1.1 爬山算法

例题：

解析：根据题意，为八数码问题，要求设计产生式系统，且控制策略为爬山算法

答题技巧：对于产生式系统，离不开三大部分：综合数据库、规则库以及控制策略，接下来介绍套路模板

（1）综合数据库：由于是针对于八数码问题，即3×3的方阵（可以当作九宫格）。此时我们要做的是：定义两个方向的单位向量i,j，以及列出所有可能出现在九宫格中的数字（0~8，其中0表示空格），集合记为Sij。

（2）规则库：对八数码来说，规则无非是左移、右移、上移和下移，因此我们呢需要用数学表达式来表达出这四个操作即可。

（3）控制策略:题目要求什么算法，就填什么策略。

理解以上，再理解爬山算法是什么。

形象说明，爬山算法就像是在爬山一样，面对前方的山有平坦点的、也有很陡峭的，而我们的依据就是每当面临一座山，择优选择最平坦的，以此迭代。在爬山算法中，我们用评价函数W（n）来表示“山的陡峭程度”。

在八数码问题中，W（n）=-（不在位的数码的个数） 不在位的意思是当前状态与目态相比而言,因此我们的目标是找到W（n）=0时停止

题目答案：

 

 注意：控制策略为爬山算法时，也要假设一个评价函数W（n）进行说明。

1.2 回溯算法

例题：

 解析：对于回溯算法，我们要有两个基本规则：回溯的深度、每走一步要确保比上一步好或至少相等，对于八数码而言，W（n）越小，即不在位的个数越少，意味着越接近目标解。

答题技巧：类似于爬山算法，产生式系统中的综合数据库和规则库的填写是一样的，不同的是在控制策略那里修改为回溯策略，并标明回溯的深度。

题目答案：

1.3 A算法

例题：

 解析：A算法相比于上述两种，稍微复杂一点，思路不难，但体现在写的步骤较多。特别是要用到评价函数f（n）=d（n）+w（n）来写出OEPN表和CLOSE表，基于此画出搜索树。（d（n）代表当前数的深度，w（n）是不在位数）。

答题技巧：将OPEN表和CLOSE表看成是两个栈，其中OPEN存放当前已经展开的九宫格状态，CLOSE表存放每一次从OPEN表中弹出的那个九宫格状态。OPEN选择弹出的依据是找到其中f（n）最小的进行弹出，并扩展该状态的下一状态，然后放在CLOSE表（这里文字叙述有点绕，等会看答案可以便于理解）。结束标志是找到f（n)=0时为止。

答案：