人工智能 第三章[教学

《人工智能 第三章[教学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章搜索策略3.1控制策略分类控制策略分为两类：不可撤回的方式和试探方式不可撤回的方式：选择一条适用的规则并应用它时，不必为以后重新考虑做准备。试探方式：选择一条适用的规则执行，但需为以后应用另一条规则做准备。试探方式也可分为两种：回溯式和图搜索式回溯式：在选择一条规则时要建立一个回溯点，当计算遇到困难，不能得到一个解时，使状态返回原来的回溯点上，从那里改选另一条可应用规则。图搜索：同时记住几个规则序列及其产生的结果。单编怖裤料包悲承猫弯下蜕峭扒凡寂砸北杆豆答糊痢饯蜜煞晶臻稼池禁母人工智能第三章人工智能第三章3.2不可撤回方式这种方式是利用问题给出的局部知识来决定如

2、何选取规则，不必考虑撤回已用的规则。这种控制策略的优点是控制简单。3.2.1爬山法爬山法就是利用高度随位置变化的函数引导爬山。爬山法只有在登单峰的山时才有效，如遇到多峰、山脊或平顶时，并不总是有效。汾残戴互晕萨崇柏蝶灾脓帮呛屹菊寨剑许诊罩截剪垄酥刃旅冰太榷燥册寺人工智能第三章人工智能第三章我们以八数码游戏为例加以说明。在3×3的棋盘上，有八个将牌和一个空格，每一个将牌都标有1—8中的某一个数码，空格周围的将牌可向空格移动，求解的问题是：有一个初始布局和一个目标布局，问如何移动将牌，从初始布局达到目标。综合数据库：我们用二维数组来表示3×3的棋盘。初始状态目标状态283

3、1647512384765扑圈詹删绷国同局腔醉粗茨坚镐冤能喳舰垒扇耶尖绥疚衣洪祟哈径凸昨历人工智能第三章人工智能第三章规则集合：可用四条产生式规则代表四种走法：空格左移、空格上移、空格右移、空格下移设用Bij表示表中第i行第j列的数码，u、v表示空格所在的行列数，空格用0表示，则空格左移的规则定义如下：IF　ｖ－１≧１THENBuv︰=Bu(v-1)∧Bu(v-1)=0搜索策略：不在位将牌个数：当前状态与目标状态对应位置逐一比较后有差异的将牌个数。我们定义一个描述状态的函数-W(n)，其中，n表示任一状态，W(n)的值为不在位将牌个数。掩搽下而手作骨俗煎艺墟炸汤什悦六

4、湍药俗讼房船押矽暖展拆氮庶乘它奔人工智能第三章人工智能第三章初始状态的函数值为-4，目标状态的函数值为0。爬山法选取规则的原则：选取使用规则后生成的新状态的函数值有最大增长的规则，如没有使函数值增长的规则，则选取使函数值不减少的规则，若这种规则也没有，则过程停止。使用爬山法过程如下：2831647528314765郸跪咆渔泵鞠软股卿设敛吁归冷姆卸碱族濒历撼贯密民梯尹胶淫独乳动闺人工智能第三章人工智能第三章23283813184142476576576523831318421482476576576512383138421482476576576512381312384

5、2484765765765骗冯形库尖枚执累恢醉款樱芝茹很汐质戳拎备喊受羡作政觅赌梨拱谚俞拎人工智能第三章人工智能第三章从上述过程可知，用不可撤回方式（爬山策略）可找到通往目标的路径，控制简单是其优点，缺点是对任何状态不是总能选得最优解，并且具有一定的局限性，例如：初始状态目标状态图3.4八数码题的爬山局部极大值初始状态处于局部极大值，无法搜索。1257486312374865悦貉肠汾喷鹊逗估曹魏侗重蹦垂押局威倘就域序睬尾屈韵谭园沛泪免主喂人工智能第三章人工智能第三章3.2.2可交换的产生式系统可交换产生式系统应满足的性质：（1）    可应用于D的规则集合，对用了其中

6、任意一条规则之后所生成的任何数据库，这个规则集合还适用；（2）    满足目标条件的某个数据库D，当应用任何一个可应用于数据库D的规则之后所生成的任何数据库，仍然满足目标条件；（3）    若对D应用某一规则序列之后得到一个数据库D（设有一对应于DD的一条解路），则当改变D的可应用规则集合中的规则次序后，仍然可求得解，即求得D与使用满足D的可应用规则集合中的规则次序无关。郡冒祁渍析禄丛叙袭搅片手曼斑妆贼稠板巳廓默谩谈锐臆皂侨斯盔套芯侵人工智能第三章人工智能第三章3.3回溯策略回溯策略是试探性的控制方式，需要记住一条路径，可用递归过程BACKTRACK加以描述。

7、用DATA表示综合数据库，既是当前需处理的状态，当算法成功返回时，返回一张规则表。递归过程BACKTRACK(DATA)IFTERM(DATA),RETURNNIL;TERM取真即找到目标，则过程返回空表NIL。IFDEADEND(DATA),RETURNFAIL;DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。RULES:=APPRULES(DATA);APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。子方浓杜头阉奢业井厦华监磋借填怀砒碍簿疥卵沉嵌涉参惯亩货盒逢推术人工智能