单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,卢锦玲,人工智能及其在电力系统中的应用,第2章 人工智能基本原理,2.1,问题,求解与问题表示,2.2,搜索策略,2.3,问题规约,2.1,问题,求解与问题表示,问题表示的三要素,问题表示:所谓问题表示就是把所要解决的问题用一个恰当的方式来表示与描述。一切问题都由三个要素构成：问题的状态，操作（或称算符、走步）和目标。,状态,有初始状态、当前状态以及可能出现的状态。一旦明确了问题的状态，就可以用恰当的方式来描述，进行在计算机中用相应的数据结构，即用符号、字符串、向量、数组、树和表等来描述。,操作,操作是使问题从一个状态转换成另一个状态。一个问题求解系统可以有一组操作，根据求解的需要，可以选择适合于当前状态的操作（一个或几个），进而执行它，使这一状态转移到需要的状态（一个或几个）。,这种操作在许多场合下以一种规则的形式出现，即满足一定条件时就对当前状态作用以达到新的状态。,目标,即目标状态，也就是问题求解需达到的最终状态。,状态空间表示法,图的概念与术语,状态空间表示,图的概念与术语,（1）,图,：由节点的集合（有限个，甚至无限个）构成。节点与节点之间可以由弧线连接。当图中所有弧线有指向时，即从一个节点指向另一个节点，则此图称为有向图。,（2）,父辈节点与后继节点,：如果一条弧线从节点,ni,指向,nj,，那么节点,ni,称为,nj,的父辈节点，而,nj,叫做,ni,的后继节点。,根结点：没有父辈的节点,叶节点：没有后继节点的节点。,（3）,路径,：从一个节点经过若干个节点后到达另一个节点，其相邻节点顺次都有有向弧线相连，那么就构成了一条从一个节点到另一个节点的路径。,在一条路径上，任一节点,ni,其后继节点，以及后继节点的后继统称为,ni,的后裔，反之，前者是后者的祖先。,（4）,树,：如果在图中，除根节点之外，所有的节点都只有一个父辈节点，那么该图就成为树。,树是图的特殊情况，或者是图的一个部分。,状态空间表示,一个问题求解系统，问题的状态可以由节点来代表，它的所有可能的状态就成为一个节点的集合，构成了状态空间，或称为状态图。状态图中的有向弧线相应地代表了操作，反映了状态转移地关系。这就是状态空间表示法。它能完整地反映与表达问题表示地三要素，且问题求解过程就相当于在状态图上从根节点（起始节点）寻找一条路径（即一组操作序列）最终达到目标节点（叶节点）。,问题表示确定的三件事,确定状态描述的方式，特别是初始状态的描述；,确定操作的集合及它们对状态的作用；,确定目标状态以及目标状态描述的特征，以便于进行目标测试。,问题求解过程就是要找出一组操作序列，使问题从初始状态最终达到目标状态,实例简介,:三数码难题,CISIC,CISIC,CISIC,1,2,3,1,2,3,1,2,3,3,1,2,3,1,2,3,1,2,初始棋局,目标棋局,八数码难题”（重排九宫问题）,问题：在,3,3,的方格棋盘上，放置,8,个标有数码,1,8,的棋子，并留有一个空格。现在要移动棋子（每次只允许把空格上、下、左、右的棋子移入空格，而该棋子原有位置位新的空格），使棋盘从初始状态到达目标状态。,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,分析：这个问题，若用状态空间表示，则棋局的每个状态对应状态图上的一个节点，若用计算机求解，其状态可用数组表示。,移动棋子可使状态转移，棋子的移动可看成是空格的移动，所有空格的移动就是该问题的操作（走步）。,操作规则：,（,1,）如果空格能左移，则左移一格；,（,2,）如果空格能上移，则上移一格；,（,3,）如果空格能右移，则右移一格；,（,4,）如果空格能下移，则下移一格；,以上规则对于任一状态并非所有操作都适用,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,2,3,4,5,1,2,3,8,4,1,2,3,8,4,5,6,7,4,1,2,3,8,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,6,7,8,9,10,11,12,13,1,2,3,8,4,5,6,7,5,6,7,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,14,15,16,17,18,19,20,21,1,2,3,8,4,5,6,7,1,3,4,5,6,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,23,24,25,26,27,1,2,3,6,7,8,22,推销员旅行问题,问题：,右图为一旅行地图，其中A、B、C、D、E分别表示五个城市，,城市之间连线上的数字表示城市间的距离现有一推销员要从城市A出发，且不得重复访问任一城市，最终回到城市A，要求一条最短的旅行路径。,A,E,D,C,7,7,10,10,13,9,6,5,10,6,分析：,这一问题的状态可用字符串表示。例如用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,）,pushbox（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，则移动次数=2,n,-1,S,0,=（1，1）,S,1,=（1，2）,S,2,=（1，3）,S,3,=（2，1）,S,4,=（2，2）,S,5,=（2，3）,S,6,=（3，1）,S,7,=（3，2）,S,8,=（3，3）,二阶梵塔问题状态表示,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,取四张牌一张,A(1),，一张,2,，一张,3,，一张,4,谜题的目的是将空间,A,的牌放到空间,C,去，但要遵从以下的规则：,一张点数大的牌决不能放在一张点数较小牌的上面，例如，你不能把“,2,”放在“,A,”的顶上，但可以把“,A,”放在“,2,”，“,3,”或“,4,”顶上,你每次只能移动一张牌到新的空间,三枚钱币问题,设有三枚钱币，处在“反、正、反”状态，每次只允许翻动一枚钱币（但不允许一枚都不翻），问连翻三次后是否可以出现“正、正、正”或“反、反、反”状态？,为解这个问题，应首先将它形式化。设钱币正面为0，反面为1，引入一个三元数组Q=(,q,1，,q,2，,q,3)来描述这三枚钱币的总状态。全部可能的状态有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：把钱币,q,1翻转一次；,f2：把钱币,q,2翻转一次；,f3：把钱币,q,3翻转一次。,问题的状态空间可写成,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,、,图搜索策略,：,盲目的图搜索策略（无信息图搜索策略）,启发的图搜索策略（有信息图搜索策略）,回溯,所谓回溯是一种可以往返试探的搜索策略，当选择一个搜索（或一组操作）达到一个新的状态后，若发现此状态达不到目标状态，或者在前面搜索过程中曾出现过此状态，那么可以回到前一状态，或回到前面曾出现过该状态的地方重新搜索，这就是回溯。通俗地讲，回溯就是回头重新找。这种回溯地策略适用于搜索量较少或有一定信息引导来帮助选择操作地问题，它可以达到较高的效率，且比图搜索策略要求较少的计算机内存。,盲目搜索技术,盲目搜索也叫无信息图搜索。最常用的两种盲目搜索技术是广度优先搜索技术和深度优先搜索技术，它们在选择操作时是盲目的，且采用穷举的方法。,广度优先搜索,