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

卢锦玲 Email: ,人工智能及其在电力系统中的应用,第2章 人工智能基本原理 2.1 问题求解与问题表示 2.2 搜索策略 2.3 问题规约,2.1问题求解与问题表示2.1.1问题表示的三要素 问题表示:所谓问题表示就是把所要解决的问题用一个恰当的方式来表示与描述。一切问题都由三个要素构成：问题的状态，操作（或称算符、走步）和目标。,状态 有初始状态、当前状态以及可能出现的状态。一旦明确了问题的状态，就可以用恰当的方式来描述，进行在计算机中用相应的数据结构，即用符号、字符串、向量、数组、树和表等来描述。,操作操作是使问题从一个状态转换成另一个状态。一个问题求解系统可以有一组操作，根据求解的需要，可以选择适合于当前状态的操作（一个或几个），进而执行它，使这一状态转移到需要的状态（一个或几个）。 这种操作在许多场合下以一种规则的形式出现，即满足一定条件时就对当前状态作用以达到新的状态。,目标即目标状态，也就是问题求解需达到的最终状态。,2.1.2状态空间表示法,图的概念与术语 状态空间表示,图的概念与术语 （1） 图：由节点的集合（有限个，甚至无限个）构成。节点与节点之间可以由弧线连接。当图中所有弧线有指向时，即从一个节点指向另一个节点，则此图称为有向图。（2） 父辈节点与后继节点：如果一条弧线从节点ni指向nj，那么节点ni称为nj的父辈节点，而nj叫做ni的后继节点。根结点：没有父辈的节点叶节点：没有后继节点的节点。,（3） 路径：从一个节点经过若干个节点后到达另一个节点，其相邻节点顺次都有有向弧线相连，那么就构成了一条从一个节点到另一个节点的路径。 在一条路径上，任一节点ni其后继节点，以及后继节点的后继统称为ni的后裔，反之，前者是后者的祖先。（4） 树：如果在图中，除根节点之外，所有的节点都只有一个父辈节点，那么该图就成为树。树是图的特殊情况，或者是图的一个部分。,状态空间表示一个问题求解系统，问题的状态可以由节点来代表，它的所有可能的状态就成为一个节点的集合，构成了状态空间，或称为状态图。状态图中的有向弧线相应地代表了操作，反映了状态转移地关系。这就是状态空间表示法。它能完整地反映与表达问题表示地三要素，且问题求解过程就相当于在状态图上从根节点（起始节点）寻找一条路径（即一组操作序列）最终达到目标节点（叶节点）。,问题表示确定的三件事确定状态描述的方式，特别是初始状态的描述；确定操作的集合及它们对状态的作用；确定目标状态以及目标状态描述的特征，以便于进行目标测试。问题求解过程就是要找出一组操作序列，使问题从初始状态最终达到目标状态,实例简介:三数码难题,八数码难题”（重排九宫问题）问题：在33的方格棋盘上，放置8个标有数码18的棋子，并留有一个空格。现在要移动棋子（每次只允许把空格上、下、左、右的棋子移入空格，而该棋子原有位置位新的空格），使棋盘从初始状态到达目标状态。,（初始状态）,分析：这个问题，若用状态空间表示，则棋局的每个状态对应状态图上的一个节点，若用计算机求解，其状态可用数组表示。移动棋子可使状态转移，棋子的移动可看成是空格的移动，所有空格的移动就是该问题的操作（走步）。操作规则：（1）如果空格能左移，则左移一格；（2）如果空格能上移，则上移一格；（3）如果空格能右移，则右移一格；（4）如果空格能下移，则下移一格；以上规则对于任一状态并非所有操作都适用,推销员旅行问题,问题：右图为一旅行地图，其中A、B、C、D、E分别表示五个城市，城市之间连线上的数字表示城市间的距离现有一推销员要从城市A出发，且不得重复访问任一城市，最终回到城市A，要求一条最短的旅行路径。,分析：这一问题的状态可用字符串表示。例如用ABC表示已先后的城市A，B，C，字符的的顺序反映了访问的先后次序。因此，字符串A代表了初始状态，即从城市A出发；而目标状态则有六个字符AA，头尾的字符均为A，表示从A出发，必须回到A，可分别用B，C,D,E表示，次序的不同代表不同的旅行路线，但它们只能出现一次。同时要求该次序达到最短旅行距离。该问题同样可以用状态图解决图中的弧线表示从一个城市到另一个城市的操作，弧线的数字表示了相应城市间的距离。,例：猴子和香蕉问题,问题：在一个房间内有一只猴子和一张桌子分别在位置a与b，另有一串香蕉悬挂在房顶，其位置为c。猴子只有在香蕉下面并站在桌子上才能摘到香蕉。问题是要找到一个行动步骤，使猴子达到目的。,解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态.这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置U 或者用产生式规则表示为（W，0，Y，z） goto（U） （U，0，Y，z）,ushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V）（V，0，V，z）,climbbox猴子爬上箱顶，即有(W，0，W，z） climbbox （W，1，W，z）,grasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1）该初始状态变换为目标状态的操作序列为 goto(b),pushbox(c),climbbox,grasp,据说在印度的贝那勒斯的圣庙中，安放着一块黄铜板，板上插着三根宝针，细如韭叶，高约腕尺梵天在创造世界的时候，在其中的一根针上，从下到上串上由大到小的64片金片这就是所谓梵塔当时梵天授言：不论黑夜白天，都要有一个值班的僧侣，按照梵天不渝的法则，把这些金片在三根针上移来移去，一次只能移一片，并且要求不管在哪根针上，小片永远在大片上面当所有的64片，都从梵天创造世界时所放的那根针，移到另外一根针上时，世界就将在一声霹雳中消灭梵塔、庙宇和众生，都将同归于尽！ n阶梵塔移动次数:设金片数为n，则移动次数=2n-1,取四张牌一张A(1)，一张2，一张3，一张4 谜题的目的是将空间A的牌放到空间C去，但要遵从以下的规则：一张点数大的牌决不能放在一张点数较小牌的上面，例如，你不能把“2”放在“A”的顶上，但可以把“A”放在“2”，“3”或“4”顶上你每次只能移动一张牌到新的空间,三枚钱币问题设有三枚钱币，处在“反、正、反”状态，每次只允许翻动一枚钱币（但不允许一枚都不翻），问连翻三次后是否可以出现“正、正、正”或“反、反、反”状态？为解这个问题，应首先将它形式化。设钱币正面为0，反面为1，引入一个三元数组Q=(q1，q2，q3)来描述这三枚钱币的总状态。全部可能的状态有8种：Q1=(0，0，0)； Q2=(0，0，1)； Q3=(0，1，0)； Q4=(0，1，1)；Q5=(1，0，0)； Q6=(1，0，1)； Q7=(1，1，0)； Q8=(1，1，1)。,翻动钱币的操作可以抽象为改变上述状态的算子，共有3个，即F=f1，f2，f3其中f1：把钱币q1翻转一次；f2：把钱币q2翻转一次；f3：把钱币q3翻转一次。问题的状态空间可写成Q6，f1，f2，f3，Q1，Q8。状态空间如图所示：从图中可以清楚地看出，从Q6不可能经过三步到达Q1，即不存在从Q6到达Q1的解。但从Q6出发到达Q8的解有7个。,问题的求解与问题表示小结说明：这些简单实例帮助我们理解一个问题如何转化为状态、操作、目标3个要素来表示。当问题的状态描述被确定后，就可以用状态图表示，为问题的解决提供了基础。 实际生活中的许多问题求解远比这些例子复杂的多。面对一个复杂问题，如何辨认它的初始状态和可能出现的各种状态，从而用一定的数据结构充分有效的表示它；如何列出和确定一系列的操作，并加以正确的表达，这是首先需要加以解决的。其次就是后面要介绍的问题求解策略。,问题求解：1、问题表示方法：问题表示三要素、状态空间表示法。2、问题求解策略：搜索逐步探索的过程,基于状态空间的问题求解就是从问题的初始状态找到问题的目标状态，相当于在状态图中得到一条从初始节点到目标节点的路径。对于某一具体问题，它的可能的状态有无数个。例如，“八数码难题”，它总共有3262880（9！）个状态，即使每个状态是一个小小的矩阵，要把所有的状态都在计算机中存起来也要占去相当可观的存储空间，显然这是不必要的，对于某些复杂问题这甚至是不可能的。而实际上我们并不关心问题的所有状态，我们所关心的是如何从初始状态到达目标状态，它仅仅占去状态空间的一小部分。,那么，如何从初始状态找到目标状态？那就是搜索。什么是搜索？先介绍一个概念“扩展节点”。 状态空间某一节点ni 一个操作 nj nj是ni 的后继节点 M个操作 m个后继节点 扩展节点ni 即：把一组操作应用于某个节点，从而产生后继节点的过程称为扩展节点。 所谓搜索，就是从起始节点开始，不断扩展节点，直到找到目标节点。 搜索图：搜索过程中形成的状态图。搜索树：特殊的图。 那么在搜索过程中如何选择扩展节点的次序？搜索策略。,搜索策略：1、回溯策略2、图搜索策略：盲目的图搜索策略（无信息图搜索策略）启发的图搜索策略（有信息图搜索策略）,回溯,所谓回溯是一种可以往返试探的搜索策略，当选择一个搜索（或一组操作）达到一个新的状态后，若发现此状态达不到目标状态，或者在前面搜索过程中曾出现过此状态，那么可以回到前一状态，或回到前面曾出现过该状态的地方重新搜索，这就是回溯。通俗地讲，回溯就是回头重新找。这种回溯地策略适用于搜索量较少或有一定信息引导来帮助选择操作地问题，它可以达到较高的效率，且比图搜索策略要求较少的计算机内存。,盲目搜索技术,盲目搜索也叫无信息图搜索。最常用的两种盲目搜索技术是广度优先搜索技术和深度优先搜索技术，它们在选择操作时是盲目的，且采用穷举的方法。广度优先搜索深度优先搜索,广度优先搜索,基本原理广度优先搜索方法是以接近起始节点的程度依次扩展节点的，如图2所示。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,为了说明广度优先搜索方法的搜索过程，先定义两个表：OPEN表和CLOSED表。OPEN表用于存放尚未被扩展的起始节点和被扩展而得到的本身尚未被扩展的新节点。CLOSED表用于存放已被扩展过的节点。广度优先搜索方法的流程图如图3所示。搜索过程如下：(1) 把起始节点放到OPEN表中。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把OPEN表的第一个节点(节点n)移出，并把它放入CLOSED表中。(4) 如果n是目标节点，则找到一个解答，成功退出；否则继续。(5) 扩展n，将其所有后继节点依此放到OPEN表的末端，并提供指向n的返回指针，然后转向第(2)步；如果n没有后继节点，则直接转向第(2)步。只要问题有解，即存在目标节点，用广度优先搜索方法一定能在有限的深度内，经过有限的操作序列（搜索步数），搜索到目标节点。所以，广度优先搜索方法是完备的，是一种推理算法。,广度优先搜索示意图,广度优先搜索算法框图,广度优先搜索特点优点：只要问题有解，即存在目标节点，用广度优先搜索方法一定能在有限的深度内，经过有限的操作序列（搜索步数），搜索到目标节点。所以，广度优先搜索方法是完备的，是一种推理算法。缺点：搜索过程长。,深度优先搜索技术基本原理在深度优先搜索中，首先扩展最晚生成的(即最深的)节点，如图4所示。首先扩展最深的节点的结果使得搜索沿着状态空间的某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。,深度优先搜索过程,深度优先搜索方法的流程图如图5所示。搜索过程如下：(1) 把起始节点放到OPEN表中。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把OPEN表的第一个节点(节点n)移出，并把它放入CLOSED表中。(4) 如果n是目标节点，则找到一个解答，成功退出；否则继续。(5) 扩展n，将其所有后继节点依此放到OPEN表的前头，并提供指向n的返回指针，然后转向第(2)步；如果n没有后继节点，则直接转向第(2)步。,深度优先搜索示意图,深度优先搜索算法框图,深度优先搜索特点,若目标节点恰好处在最晚生成的子节点分支中，则可以较快地求得问题的解，效率比广度优先搜索方法高。若目标节点不在最晚生成的子节点分支中，且该分支为无穷分支，则搜索过程无限循环，无法停止，不能找到目标节点。因此，深度优先搜索方法是不完备的，是一种推理步骤，不是推理算法，不能保证推理过程的收敛性。即使问题有解，也不一定能保证搜索到目标节点，可能陷入无穷分支的死循环里。,为了改进深度优先搜索方法，以免搜索过程沿着无益的路径扩展下去，可以给出节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么都将它们作为没有后继节点处理。深度界限如何选择也是需要考虑的问题，如果选得过小，就有可能找不到目标节点，导致搜索失败；如果选得过大，将生成许多无用的子节点，降低搜索效率。优点：只要存在解，就能保证找到解，且是最短路径的解，是完备的。缺点：搜索过程很长。,深度优先搜索的实例，解“八数码难题”,1）深度优先搜索深度优先搜索是从根节点（起始节点）开始，首先扩展最新产生的节点，即根据搜索树的深度发展下去，一直到没有后继节点再返回，换一条路径走下去。深度优先搜索算法的步骤和流程图。缺点：如果搜索树的深度可能非常深，甚至是无限的，那么搜索时间很长，搜索路径很长，或找不到解，走入 死胡同。解决的办法是采用有界深度优先搜索，即定出一个深度界限，在搜索到达这一深度，而且尚未找到目标时，即返回重找。实例解八数码难题，并定义深度界线为5，参见图211。,