1、第六章第六章 搜索策略搜索策略 搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关 系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个 核心问题之一。核心问题之一。5.1 基本概念基本概念 1.什么是搜索什么是搜索 人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的 问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步问题一般不存在成熟的求解
2、算法可供利用，而只能是利用已有的知识一步步 摸索着前进。摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。使其付出的代价尽可能的少，而问题又能得到较好的解决。如：在正向推理中，如：在正向推理中，对已知的初始事实，需要在知识库中寻找可使用的知识，这就对已知的初始事实，需要在知识库中寻找可使用的知识，这就 存在按何种线路进行寻找的问题。存在按何种线路进行寻找的问题。另外，可能存在多条线路都可实现对问题的求解，这就又出现另外，可能存在多条线路都可实现对问题的求解，
3、这就又出现 按哪一条线路进行求解以获得较高的运行效率的问题。按哪一条线路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。的推理路线，使问题得到圆满解决的过程称为搜索。2.搜索分类搜索分类 搜索分为盲目搜索和启发式搜索。搜索分为盲目搜索和启发式搜索。盲目搜索盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信按预定的控制策略进行搜索，在搜索过程中获得的中间信 息不用来改进控制策略。这种搜索具有盲目性，效率不高，息不用来改进控制
4、策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。不便于复杂问题的求解。启发式搜索启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜在搜索中加入了与问题有关的启发性信息，用以指导搜 索朝着最有希望的方向前进，加速问题的求解过程并索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。找到最优解。5.2 求解问题的表示方法求解问题的表示方法 用搜索策略求解问题，首先要解决的问题也是：用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来用什么样的形式把问题表示出来.一般来说，有两种方法：一般来说，有两种方法：1.状态空间表示法状态空间表示法状态空间表示法是用来
5、表示问题及其搜索过程的一种方法，它是人工智能中最状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最 基本的形式化方法。基本的形式化方法。状态空间表示法是用状态空间表示法是用“状态状态”和和“算符算符”来表示问题的一种方法。其中，来表示问题的一种方法。其中，“状态状态”用以描述问题求解过程中不同时刻的状况；用以描述问题求解过程中不同时刻的状况；“算符算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换表示对状态的操作，算符的每一次使用就使问题由一种状态变换为为 另一种状态另一种状态;解解 当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题当到达目标状态时，由
6、初始状态到目标状态所用算符的序列就是问题 的一个解。的一个解。状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK(SK0,SK1,)当给每一个分量以确定的值时，就得到了一个具体的状态当给每一个分量以确定的值时，就得到了一个具体的状态。引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。符。在产生式系统中，每一条产生式规则就是一个算符。由问题的
7、全部状态及一切可用算符所构成的集合称为问题的状态空间，由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，般用般用个三元个三元组表示：组表示：(S，F，G)其中其中,S是问题的所有初始状态构成的集合；是问题的所有初始状态构成的集合；F是算符的集合；是算符的集合；G是目标状态的集合。是目标状态的集合。状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边(弧弧)表示算符。表示算符。例例1：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反），：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反），允许每次
8、翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达 到目标状态？（正正正）到目标状态？（正正正）或（反反反）？或（反反反）？正正反反正正正正正正反反反反反反反反 设用设用 Sk=(s1,s2,s3)表示问题的状态，表示问题的状态，s=0 表示钱币正面，表示钱币正面，s=1表示钱币反面。表示钱币反面。则钱币可能出现的状态有八种：则钱币可能出现的状态有八种：S0=(0,0,0),S1=(0,0,1),S2=(0,1,0),S3=(0,1,1)S4=(1,0,0),S5=(1,0,1),S6=(1,1,0),S7=(1,1,1
9、)问题的初始状态集合问题的初始状态集合：S=S5 目标状态集合：目标状态集合：G=S0,S7 算符：算符：f1 把把s1翻一面；翻一面；f2 把把s2翻一面；翻一面；f3 把把s3翻一面；翻一面；上述问题的状态空间上述问题的状态空间“三元组三元组”为：为：（S5,f1,f2,f3,s0,s7）相应的状态空间图：相应的状态空间图：0 0 01 0 00 0 11 0 11 1 10 1 11 1 00 1 0S0S4S1S5S7S3S6S2从图中看出：从从图中看出：从S5不可能经三次翻转到达不可能经三次翻转到达S0,从从S5 可经三次翻转到达可经三次翻转到达S7,且有七种操作方式。且有七种操作方
10、式。f1f1f1f1f2f2f2f2f3f3f3f32.与与/或树表示法或树表示法 与与/或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较 复杂问题的求解。复杂问题的求解。对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：(1)分解：分解：“与与”树树 把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问 题分别进行求解，最后把各子问题的解复合起来就得到了原问
11、题的解。题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。这是这是“与与”的问题。的问题。PP1P2P3P1,P2,P3 为子节点，子问题对应子节点。为子节点，子问题对应子节点。P为为“与与”节点，只有当三个子问题都有解时，节点，只有当三个子问题都有解时，P才可解。才可解。如图所示，称为如图所示，称为“与与”树。树。(2)等价变换：等价变换：“或或”树树 利用等价变换，把它变换为若干个较容易求解的新问题。利用等价变换，把它变换为若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。若新问题中有一个可求解，则就得到了原问题的解。这是这是“或或”的问题。的问题。如图所
12、示，称为如图所示，称为“或或”树。树。PP1P2P3与与/或树：或树：将上述两种方法也可结合起来使用，此时的图称为将上述两种方法也可结合起来使用，此时的图称为“与与/或树或树”，其中既有，其中既有“与与”节点，节点，也也 有有“或或”节点。在此统称为子节点。节点。在此统称为子节点。P1P11P12P3P31P32P33PP2(3)几个基本概念：几个基本概念：不能再分解或变换，而且直接可解的子问题称为本原问题。不能再分解或变换，而且直接可解的子问题称为本原问题。在与在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。或树中，没有子节点的节点称为端节点；本原问题所对应的节点
13、称为终止节点。显然终止节点一定是端节点，但端节点不一定是终止节点。显然终止节点一定是端节点，但端节点不一定是终止节点。在与在与/或树中，满足下列条件之一者，称为可解节点：或树中，满足下列条件之一者，称为可解节点：它是一个终止节点。它是一个终止节点。它是一个它是一个“或或”节点，且其子节点中至少有一个是可解节点。节点，且其子节点中至少有一个是可解节点。它是一个它是一个“与与”节点，且其子节点全部是可解节点。节点，且其子节点全部是可解节点。关于可解节点的三个条件全部不满足的节点称为不可解节点。关于可解节点的三个条件全部不满足的节点称为不可解节点。由可解节点所构成，并且由这些可解节点可推出初始节点由
14、可解节点所构成，并且由这些可解节点可推出初始节点(它对应于原始问题它对应于原始问题)为可解为可解 节点的节点的子树子树称为解树。在解树中一定包含初始节点。称为解树。在解树中一定包含初始节点。例如：例如：t t标出的节点是终止节点，标出的节点是终止节点，根据可解节点的定义，根据可解节点的定义，原始问题原始问题P P是可解的。是可解的。t tP例：三阶汉诺塔问题。设有例：三阶汉诺塔问题。设有A，B，C三个金片以及三根钢针，三个金片按自上而三个金片以及三根钢针，三个金片按自上而下从小到大的顺序穿在下从小到大的顺序穿在1号钢针上，要求把它们全部移到号钢针上，要求把它们全部移到3号钢针上，而且每次号钢针
15、上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。首先进行问题分析：首先进行问题分析：(1)为了把三个金片全部移到为了把三个金片全部移到3号针上，必须先把金片号针上，必须先把金片C移到移到3号针上。号针上。(2)为了移金片为了移金片C，必须先把金片必须先把金片A及及B移到移到2号针上。号针上。(3)当把金片当把金片c移到移到3号针上后，就可把号针上后，就可把A，B从从2号移到号移到3号针上，这样就可完成问题的求解。号针上，这样就可完成问题的求解。由此分析，得到了原问题的三个子问题：由此分析，得
16、到了原问题的三个子问题：(1)把金片把金片A及及B移到移到2号针的双金片问题。号针的双金片问题。(2)把金片把金片C移到移到3号针的单金片问题。号针的单金片问题。(3)把金片把金片A及及B移到移到3号针的双金片问题。号针的双金片问题。其中，子问题其中，子问题(1)与子问题与子问题(3)又分别可分解为三个子问题。又分别可分解为三个子问题。A BCA B C 设仍用状态表示问题在任一时刻的状况；设仍用状态表示问题在任一时刻的状况；用三元组用三元组 (i，j，k)表示状态：表示状态：i代表金片代表金片C所在的钢针号；所在的钢针号；j代表金片代表金片B所在的钢针号所在的钢针号;k代表金片代表金片A所在
17、的钢针号。所在的钢针号。用用“”表示状态的变换；表示状态的变换；这样原始问题就可表示为：这样原始问题就可表示为：(1,1,1)(3，3，3)用与用与/或树把分解过程表示出来。或树把分解过程表示出来。(1,1,1)(3,3,3)(1,2,2)(3,2,2)(1,1,1)(1,2,2)(3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)若把这些本原问题的解按从左至右的顺序排列，就得到了原始问题的解：若把这些本原问题的解按从左至右的顺序排列，就得到了原始问题
18、的解：(1,1,1)(1,l,3)，(1,1,3)(1,2,3)，(1,2,3)(1,2,2)，(1,2,2)(3,2,2)，(3,2,2)(3,2,1)，(3,2,1)(3,3,1)，(3,3,1)(3,3,3)它指出了移动金片的次序。它指出了移动金片的次序。此图共有七个终止节点，此图共有七个终止节点，对应于七个本原问题，它对应于七个本原问题，它们是通过们是通过“分解分解”得到的。得到的。5.3 状态空间搜索策略状态空间搜索策略 1.概述概述 (1)显式图与隐式图显式图与隐式图 为了求解问题，需要把知识存储在计算机的知识库中，有下列两种存储方式：为了求解问题，需要把知识存储在计算机的知识库中
19、，有下列两种存储方式：把与问题有关的全部状态空间图，即相应的全部知识（事实性知识、过程性把与问题有关的全部状态空间图，即相应的全部知识（事实性知识、过程性知识，控制性知识）都直接存入知识库，称为知识，控制性知识）都直接存入知识库，称为“显式存储显式存储”或或“显式图显式图”。只存储与问题有关的部分知识，在求解过程中，又初始状态出发，运用相只存储与问题有关的部分知识，在求解过程中，又初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，找到所求目标。应的知识，逐步生成所需的部分状态空间图，通过搜索推理，找到所求目标。这样只需在知识库中存储局部状态空间图，称为这样只需在知识库中
20、存储局部状态空间图，称为“隐式图隐式图”。通常，为了节约计算机的存储容量，提高搜索推理效率，采用隐式存储方通常，为了节约计算机的存储容量，提高搜索推理效率，采用隐式存储方法，进行隐士图搜索推理。法，进行隐士图搜索推理。(2)(2)搜索方法搜索方法 .运用事实性知识，给出问题的部分状态描述，包括：初始状态运用事实性知识，给出问题的部分状态描述，包括：初始状态S S0 0，目标状态目标状态 S Sg g，和某些中间状态和某些中间状态S Sh h；.运用过程性知识，给出由状态空间图运用过程性知识，给出由状态空间图“父节点父节点”生成生成“子节点子节点”的操作的操作“算算符符”；.运用控制性知识（在此
21、为搜索策略），选取适当的节点，控制继续搜索的方运用控制性知识（在此为搜索策略），选取适当的节点，控制继续搜索的方 向。向。(3)(3)搜索过程搜索过程 .给出初始状态（初始节点）；给出初始状态（初始节点）；.选择选择适用的算符对其进行操作，生成一组子状态选择选择适用的算符对其进行操作，生成一组子状态(或称后继状态、后继或称后继状态、后继 节点、子节点节点、子节点)；.检查目标状态是否在其中出现。若出现检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若则搜索成功，找到了问题的解；若 不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。不出现，则按某种搜索策略从已生成
22、的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。(4)(4)搜索过程中要用到的两个数据结构搜索过程中要用到的两个数据结构 用于存放刚生成的节点。对于不同的搜索策略，节点在用于存放刚生成的节点。对于不同的搜索策略，节点在OPENOPEN表中的排列顺序表中的排列顺序是不同的。是不同的。用于存放将要扩展或者已扩展的节点，所谓对节点进行用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展扩展”是指：用是指：用合适的算符对该节点进行操作，生成一组子节点。合适的算符对该节点进行操作，
23、生成一组子节点。状态节状态节点点父节父节点点OPEN表表编号编号状态节状态节点点父节父节点点CLOSED表表(5)状态空间法搜索策略状态空间法搜索策略 广度优先搜索广度优先搜索 深度优先搜索深度优先搜索 有界深度优先搜索有界深度优先搜索 代价树的广度优先搜索代价树的广度优先搜索 代价树的深度优先搜索代价树的深度优先搜索 （以上属于盲目搜索策略）（以上属于盲目搜索策略）局部择优搜索局部择优搜索 全局择优搜索全局择优搜索 （以上搜索属于启发式搜索）（以上搜索属于启发式搜索）2.2.广度优先搜索法（广度优先搜索法（Breadth-First Search)Breadth-First Search)(
24、1)(1)基本思想基本思想 从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节点，从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节点，顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该级全部节点中沿广度进行级全部节点中沿广度进行“横向横向”扫描，即：沿扫描，即：沿“广度广度”遍历所有节点，故称遍历所有节点，故称“广度优先搜索法广度优先搜索法”。(2)(2)广度优先搜索法搜索过程广度优先搜索法搜索过程 .把初始节点把初始节点S S0 0放人放人OPENOPEN表，若表，若S S0 0为目标
25、节点，则得到问题的解，退出；为目标节点，则得到问题的解，退出；.如果如果OPENOPEN表为空，则问题无解，退出；表为空，则问题无解，退出；.把把OPENOPEN表的第一个节点表的第一个节点(记为节点记为节点n)n)取出放入取出放入CLOSEDCLOSED表；表；.考察节点考察节点n n，若节点若节点n n不可扩展，则转第不可扩展，则转第步；步；.扩展节点扩展节点n n，将其子节点放入将其子节点放入0PEN0PEN表的尾部表的尾部，并为每一个子节点都配置指向父节点，并为每一个子节点都配置指向父节点 的指针；的指针；.如果如果n n的任一个后继节点是目标节点，则找到问题的解，成功退出，否则转向第
26、的任一个后继节点是目标节点，则找到问题的解，成功退出，否则转向第步。步。开始开始把把S0送入送入OPEN表表 把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n)从表中移出，放入从表中移出，放入CLOSED表表 OPEN表为空？表为空？扩展节点扩展节点n,将其子节点放入将其子节点放入，并为每个子节点配置指向节点并为每个子节点配置指向节点n的指针。的指针。是否有任何后继是否有任何后继 节点为目标节点？节点为目标节点？节点节点n可扩展？可扩展？失败，退出失败，退出成功，退出成功，退出YNYNYNS0为目标节点？为目标节点？成功，退出成功，退出YN状态节状态节点点父节父节点点OPEN表表编
27、号编号状态节状态节点点父节父节点点CLOSED表表S012S012634 5S012634 5789(a)(b)(c)(d)S0S01121200034203356789411112233445S010203141Sg(9)S0491例：例：重排九宫问题。在重排九宫问题。在3X3的方格棋盘上放置分别标有数字的方格棋盘上放置分别标有数字1，2，3，4，5，6，7，8的八张牌，初始状态为的八张牌，初始状态为50，目标状态为，目标状态为S，如下图所示。如下图所示。可使用的算符有：可使用的算符有：空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移 即，它们只允许把位于空格左，
28、上，右，下边的牌移入空格。即，它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目标状态的路径。要求寻找从初始状态到目标状态的路径。应用广度优先搜索，可得到如图所示的搜索树。应用广度优先搜索，可得到如图所示的搜索树。2 8 31 47 6 51 2 38 47 6 5 由图可以看出，解的路径是由图可以看出，解的路径是:S03 8 16 26(Sg)广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许 多无用节点，搜索效率低，这是它的缺点。多无用节点，搜索效率低，这是它的缺点。只要问题有解，用广度优先
29、搜索总可以得到解，而且得到的是路径最短的只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的 解，这是它的优点。解，这是它的优点。3.深度优先搜索深度优先搜索 (1)基本思想基本思想 从初始节点从初始节点S0开始，按生成规则生成下一级各子节点，若目标节点未出现，开始，按生成规则生成下一级各子节点，若目标节点未出现，则按则按“最晚生成的子节点优先扩展最晚生成的子节点优先扩展”的原则，生成再下一级的子节点，如此下去，的原则，生成再下一级的子节点，如此下去，沿着最晚生成的子节点分支，逐级向沿着最晚生成的子节点分支，逐级向“纵向纵向”深入发展，故称为深入发展，故称为“深度优先搜索深度优先搜
30、索法法”。(2)深度优先搜索法搜索过程深度优先搜索法搜索过程 广度优先搜索是将节点广度优先搜索是将节点n n的子节点放入到的子节点放入到OPENOPEN表的尾部，表的尾部，而深度优先搜索是而深度优先搜索是 把节点把节点n n的子节点放入到的子节点放入到OPENOPEN表的首部。表的首部。仅此一点不同，就使得搜索的路线完全不一样。仅此一点不同，就使得搜索的路线完全不一样。开始开始把把S0送入送入OPEN表表 把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n)从表中移出，放入从表中移出，放入CLOSED表表 OPEN表为空？表为空？扩展节点扩展节点n,将其子节点放入将其子节点放入，并为每个子节点配置指向节点并为每个子节点配置指向节点n的指针。的指针。是否有任何后继是否有任何后继 节点为目标节点？节点为目标节点？节点节点n可扩展？可扩展？失败，退出失败，退出成功，退出成功，退出YNYNYNS0为目标节点？为目标节点？成功，退出成功，退出YN状态节状态节点点父节父节点点OPEN表表编号编号状态节状态节点点父节父节点点CLOSED表表S012S01234(a)(b)(c)S0S012345S0123465S012346578(d)020222032424254646476861Sg(8)S02468(e)
