人工智能第二讲new课件.ppt

1、卢锦玲卢锦玲 Email:人工智能及其在电力系统人工智能及其在电力系统中的应用中的应用 问题表示问题表示:所谓问题表示就是把所要解决所谓问题表示就是把所要解决的问题用一个恰当的方式来表示与描述。的问题用一个恰当的方式来表示与描述。一切问题都由三个要素构成：问题的状态，一切问题都由三个要素构成：问题的状态，操作（或称算符、走步）和目标。操作（或称算符、走步）和目标。有初始状态、当前状态以及可能出现的状有初始状态、当前状态以及可能出现的状态。一旦明确了问题的状态，就可以用态。一旦明确了问题的状态，就可以用恰当的方式来描述，进行在计算机中用恰当的方式来描述，进行在计算机中用相应的数据结构，即用符号、

2、字符串、相应的数据结构，即用符号、字符串、向量、数组、树和表等来描述。向量、数组、树和表等来描述。图的概念与术语图的概念与术语 状态空间表示状态空间表示 n问题求解过程就是要找出一组操作序列，使问问题求解过程就是要找出一组操作序列，使问题从初始状态最终达到目标状态题从初始状态最终达到目标状态CISICCISICCISICCISICCISICCISICCISICCISICCISIC123123123312312312初始棋局目标棋局123845671 2384567（目标状态）（初始状态）123845671238456712384567123845671238456723451238412384

3、5674123856712 3841238456712384567123845676789101112131238456756756712384567123845671 238456712 38456712384567123845671238456714151617181920211238456713456123845671238456712384567123845671 2384567232425262712367822推销员旅行问题问题：问题：右图为一旅行地图，其中A、B、C、D、E分别表示五个城市，城市之间连线上的数字表示城市间的距离现有一推销员要从城市A出发，且不得重复访问任一城市，最

4、终回到城市A，要求一条最短的旅行路径。AEDC77101013965106分析：分析：这一问题的状态可用字符串表示。例如用ABC表示已先后的城市A，B，C，字符的的顺序反映了访问的先后次序。因此，字符串A代表了初始状态，即从城市A出发；而目标状态则有六个字符AA，头尾的字符均为A，表示从A出发，必须回到A，可分别用B，C,D,E表示，次序的不同代表不同的旅行路线，但它们只能出现一次。同时要求该次序达到最短旅行距离。该问题同样可以用状态图解决图中的弧线表示从一个城市到另一个城市的操作，弧线的数字表示了相应城市间的距离。问题：在一个房间内有一只猴子和一张桌子分别在位置a与b，另有一串香蕉悬挂在房顶

5、，其位置为c。猴子只有在香蕉下面并站在桌子上才能摘到香蕉。问题是要找到一个行动步骤，使猴子达到目的。解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态.这个问题的操作（算符）如下：vgoto（U）表示猴子走到水平位置U v或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）climbbox猴子爬上箱顶，即有(W，0，W，z）climbbox （W，1，W，z）vgrasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）v该初始状态变换为目标状态

6、的操作序列为 goto(b),pushbox(c),climbbox,grasp据说在印度的贝那勒斯的圣庙中，安放着一块黄铜板，据说在印度的贝那勒斯的圣庙中，安放着一块黄铜板，板上插着三根宝针，细如韭叶，高约腕尺梵天在创造板上插着三根宝针，细如韭叶，高约腕尺梵天在创造世界的时候，在其中的一根针上，从下到上串上由大到世界的时候，在其中的一根针上，从下到上串上由大到小的小的64片金片这就是所谓梵塔当时梵天授言：不片金片这就是所谓梵塔当时梵天授言：不论黑夜白天，都要有一个值班的僧侣，按照梵天不渝的论黑夜白天，都要有一个值班的僧侣，按照梵天不渝的法则，把这些金片在三根针上移来移去，一次只能移一法则，把

7、这些金片在三根针上移来移去，一次只能移一片，并且要求不管在哪根针上，小片永远在大片上片，并且要求不管在哪根针上，小片永远在大片上面当所有的面当所有的64片，都从梵天创造世界时所放的那根片，都从梵天创造世界时所放的那根针，移到另外一根针上时，世界就将在一声霹雳中消针，移到另外一根针上时，世界就将在一声霹雳中消灭梵塔、庙宇和众生，都将同归于尽！灭梵塔、庙宇和众生，都将同归于尽！n阶梵塔移动次数阶梵塔移动次数:设金片数为设金片数为n，则移动次数，则移动次数=2n-1,123123123123123123123123取四张牌一张A(1)，一张2，一张3，一张4 谜题的目的是将空间A的牌放到空间C去，但

8、要遵从以下的规则：一张点数大的牌决不能放在一张点数较小牌的上面，例如，你不能把“2”放在“A”的顶上，但可以把“A”放在“2”，“3”或“4”顶上你每次只能移动一张牌到新的空间n翻动钱币的操作可以抽象为改变上述状态的算子，共有3个，即F=f1，f2，f3n其中f1：把钱币q1翻转一次；nf2：把钱币q2翻转一次；nf3：把钱币q3翻转一次。n问题的状态空间可写成nQ6，f1，f2，f3，Q1，Q8。n状态空间如图所示：n从图中可以清楚地看出，从Q6不可能经过三步到达Q1，即不存在从Q6到达Q1的解。但从Q6出发到达Q8的解有7个。0 0 0Q11 0 00 0 11 0 11 1 11 1 0

9、0 1 00 1 1Q2Q5Q3Q4Q6Q8Q7f1f1f1f1f2f2f2f2f3f3f3f3n基于状态空间的问题求解就是从问题的初始状态基于状态空间的问题求解就是从问题的初始状态找到问题的目标状态，相当于在状态图中得到一找到问题的目标状态，相当于在状态图中得到一条从初始节点到目标节点的路径。条从初始节点到目标节点的路径。n对于某一具体问题，它的可能的状态有无数个。对于某一具体问题，它的可能的状态有无数个。例如，例如，“八数码难题八数码难题”，它总共有，它总共有3262880（9！）个状态，即使每个状态是一个小小的矩！）个状态，即使每个状态是一个小小的矩阵，要把所有的状态都在计算机中存起来也

10、要占阵，要把所有的状态都在计算机中存起来也要占去相当可观的存储空间，显然这是不必要的，对去相当可观的存储空间，显然这是不必要的，对于某些复杂问题这甚至是不可能的。而实际上我于某些复杂问题这甚至是不可能的。而实际上我们并不关心问题的所有状态，我们所关心的是如们并不关心问题的所有状态，我们所关心的是如何从初始状态到达目标状态，它仅仅占去状态空何从初始状态到达目标状态，它仅仅占去状态空间的一小部分。间的一小部分。那么，如何从初始状态找到目标状态？那就是搜索。那么，如何从初始状态找到目标状态？那就是搜索。什么是搜索？先介绍一个概念什么是搜索？先介绍一个概念“扩展节点扩展节点”。状态空间某一节点状态空间

11、某一节点ni 一个操作一个操作 nj nj是是ni 的后继节点的后继节点 M个操作个操作 m个后继节点个后继节点 扩展节点扩展节点ni 即：把一组操作应用于某个节点，从而产生后继节即：把一组操作应用于某个节点，从而产生后继节点的过程称为扩展节点。点的过程称为扩展节点。所谓搜索，就是从起始节点开始，不断扩展节点，所谓搜索，就是从起始节点开始，不断扩展节点，直到找到目标节点。直到找到目标节点。搜索图：搜索过程中形成的状态图。搜索树：特殊的搜索图：搜索过程中形成的状态图。搜索树：特殊的图。图。那么在搜索过程中如何选择扩展节点的次序？搜索那么在搜索过程中如何选择扩展节点的次序？搜索策略。策略。QPFFNFSLMFO把S放入OPEN表取OPEN表的第1个节点n,并把它放入CLOSED表n为目标节点?OPEN为空表?失败No开始成功YesNo扩展n,把它的后继节点放入OPEN的末端,提供返回n的指针YesQPFFSLMFONF把S放入OPEN表取OPEN表的第1个节点n,并把它放入CLOSED表OPEN为空表?失败No开始成功No扩展n,把它的后继节点放入OPEN的前头,提供返回n的指针n为目标节点?YesYes