第二章人工智能系统的基本结构第二章人工智能系统结构2.1产生式系统概述2.1.1产生式系统的基本结构3、控制器是规则的解释程序或执行程序，它规定选择一条可用规则的原则和规则使用的方式(推理方向)，并根据综合数据库的信息，控制求解问题的过程（控制策略,推理引擎）。通常从选择规则到执行操作分三步：匹配。判断规则的前件是否成立?可能有多条规则的前件能够与综合数据库中的事实匹配!冲突解决，选择可调用的规则。从匹配满足的规则集中选择一条规则。执行规则，并在满足结束条件时终止产生式系统的运行。如果规则的后件是结论，把该结论加入综合数据库；如果规则的后件是动作，执行该动作；4、产生式系统的特点：数据、知识和控制相互独立。知识具有相对固定的格式：均由左、右两部分组成。知识无序性与模块化：知识的补充和修改非常容易。控制系统与问题无关。2.1.2产生式系统的基本过程2.2问题的表示2.2.1状态空间法2.2.2问题归约法2.2.3产生式系统举例1．综合数据库：选择一种数据结构表示将牌布局。本例选用二维数组来表示布局较直观，其数组元素用表示，其中且互不相等。这样每个具体取值矩阵就代表了一个棋局状态。显然，该问题有个状态。2.规则集：移动一块将牌（即走一步）就使状态发生一次转变。有四种走法：空格左移、空格上移、空格右移、空格下移。记数组第i行第j列的元素为空格所在的行、列分别记为，则则空格左移一格、空格上移一格、空格右移一格、空格下移一格可用如下4条规则来描述：规则1:（空格左移一格）规则2:（空格上移一格）规则3:（空格右移一格）规则4:（空格下移一格）3.控制策略：从规则集中选择规则并作用于状态的一种广义选取函数。确定某一策略后，可以用算法的形式给出程序。使用该策略从初始状态出发，通过不断寻求满足一定条件的问题状态，最后到达目标状态。2.3控制策略分类对当前的状态，只要某一条规则作用之后能生成合法的新状态，那么，这条规则就是可用规则。产生式系统的运行表现出一种搜索过程，在每一个循环中选一条规则试用，直到找到某一个序列能产生满足结束条件的状态为止。不同的控制策略产生不同的解，高效率的控制策略能够走较少的步骤达到目标，但需要问题求解的足够知识。控制策略分为两类：不可撤回方式（Irrevocable）和试探方式（Tentative）。1）不可撤回方式：利用H(P)可以计算朝不同方向迈出一步后高度的变化情况。即向东：△z1=H（P0+△x）-H(P0)向西：△z2=H（P0-△x）-H(P0)向北：△z3=H（P0+△y）-H(P0)向南：△z4=H（P0-△y）-H(P0)选择△z变化最大的那一步攀登，到达新的位置P；从P开始重复这一过程，直到到达山顶。爬山算法1.开始状态作为一个可能状态。2.从一个可能状态，应用可用规则集生成所有新的可能状态集。3.对该状态集中每一状态：（1）进行状态测试，检查其是否为目标：（2）如果是目标则程序停止。（3）如果不是目标，计算该状态的好坏或者比较各状态的好坏。4.取状态集中最好状态，作为下一个可能状态。5.回到第2步。爬山算法缺点：有时到达某一状态后，尽管它不是目标状态，但在测试过中又找不到比该状态更好的状态，如图2-3。⑴局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。⑵平顶：它与全部邻居状态都有同一个值。⑶山脊：如果搜索方向与山脊的走向不一致，则有可能会停留在山脊处。所以，用不可撤回方式来求解登山问题，需要对状态测试函数进行选择：这个函数应具有单极值，且这个极值对应目标状态值。测试函数例：以8数码为例，统计“不在位”将牌个数（逐一比较当前状态与目标状态对应位置,有差异的将牌总个数），并取其负值作为状态描述的函数.-W(n)（n为测试状态）基于该定义，下图所示状态的函数值为-4。显然，目标状态的函数值为0。12384765爬山法的策略执行使新状态的测试函数值有最大增长的规则；所有规则都不能使新状态的测试函数值增长时，执行使测试函数值不减少的规则；如果以上两种规则都不存在，则过程停止。2）试探方式2）试探方式28316475图搜索方式:对任一状态，应用其所有可应用规则，并把状态变化过程用图结构记录下来，一直到得到解为止。图搜索策略求解问题是一种穷举方式。图2-7是5个城市旅行商问题的地图，求从A出发经B、C、D、E再回到A的最短路径。问题的表示：若每个城市用一个字母表示，则综合数据库可用字母组成的表或字符串来表示，如（A）表示初始状态，（A****A）表示目标状态，（A**）表示访问两个城市后的当前状态。规则集：1）下一步走向城市A；2）下一步走向