人工智能幻灯片-搜索问题-2

《人工智能幻灯片-搜索问题-2》由会员分享，可在线阅读，更多相关《人工智能幻灯片-搜索问题-2（70页珍藏版）》请在金锄头文库上搜索。

1、第一部分 问题求解,用搜索法对问题求解 问题求解算法描述： 问题实例 ：玩具世界与现实世界问题 搜索求解性能的度量 *无信息的搜索策略 *有信息的搜索和探索 *对抗搜索（与或图搜索） 高级搜索,第二部分 知识表示与推理,谓词逻辑与归结原理 命题逻辑 谓词逻辑 *归结原理 Herbrand定理 知识表示 知识概述 *产生式表示 语义网络表示 框架表示 其他表示方法,第三部分 人工智能高级专题,基于模型的诊断 配置问题 智能规划 调度,搜索算法把问题作为输入，并以行动序列的形式返回问题的解。一旦找到一个解，那么它所建议的行动就可以付诸实施，这被称为执行阶段。因而我们可以对问题求解算法进行设计，即“

2、形式化、搜索、执行” 问题的形式化：一个问题可以形式化地定义为四个组成部分： 初始状态； 可能的行动的描述。最常见的形式化是使用一个后继函数。给定一个特殊的状态x，Successor(x)返回一个由有序对（行动，后继）组成的集合，其中每个行动都是状态x下的合法行动之一，每个后继都是行动后从状态x能够达到的状态。,定义明确的问题及解,总之，初始状态和它的后继函数隐含的定义了问题的状态空间-即从初始状态可以达到的所有状态的集合。状态空间形成一个图，其中节点是状态，节点之间的弧就是行动，状态空间中的一条路径就是通过行动序列连接起来的一个状态序列。 目标测试，用来确定当前状态是不是目标状态。 路径耗散

3、函数为每条路径分配一个数值化的耗散值。问题求解算法选择能反映它自己性能度量的耗散函数。 上述四个元素定义了一个问题，可以把它们集合在一起成为一个单一的数据结构，作为问题求解算法的输入。问题的解就是从初始状态到目标状态的路径。解的优劣由路径耗散函数度量，而最优解是所有的解里路径耗散值最小的解。,前面用初始状态、后继函数、目标测试和路径耗散来表示问题，这种形式化表示是合理的，不过它忽略了现实世界的许多方面，去除表示中细节的过程被称为抽象化，而去除表示中细节的描述称为问题形式化。,问题实例,玩具世界与现实世界问题 我们首先来看一个八数码游戏,初始状态,目标状态,它包括一个3X3的棋盘，棋盘上摆放着8

4、个写有数字的棋子，留下一个空位。与空位相邻的棋子可以滑入到空位中。游戏的目的是要达到一个特定的目标状态。,初始状态,搜索和执行,标准的形式化如下： 状态；描述了指定8个棋子中的每一个以及空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为初始状态。 后继函数：用来产生通过四个行动（把空位向Left，right,Up或Down)能够达到的合法状态。 目标测试：用来检测状态是否是目标状态。 路径耗散：设每一步的耗散值是1因此整个路径的耗散值是路径中的步数。 这里的抽象化只保留了游戏规则相关的描述，而忽略所有物理操

5、作的细节。,八数码游戏属于滑快问题家族，这类问题经常被用作AI中新的搜索算法的测试问题。这类一般问题已知为NP完全问题，因此对这类问题不要期望在最坏情况下找到好于我们后面要讲述的算法。八数码游戏共有9！/2=181440个可达到的状态，这是很容易求解的。15数码问题则大约有1.3万亿个状态，用最好的搜索算法最优化地求解一个随机的实例需要几毫秒。24数码游戏则大约有1025个状态，用目前的机器和最优化算法求解随机的实例仍是相当困难的。 四皇后问题在一个44的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。如图其中a，b满足目标

6、条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间势态。,四皇后问题的几个状态,尽管对于这个问题和整个n皇后问题家族存在有效的专用算法，这类问题对于搜索算法仍然是个有趣的测试问题。形式化主要有两类：一类是增量形式化，包括了增加状态描述的算符，从空状态开始：对于四皇后问题意味着每次行动添加一个皇后到状态中去。另一类是完全状态形式化，4个皇后都在棋盘上开始，然后移动它们。,增量形式化如下： 状态：把0到4个皇后放棋盘上的任何安排都是一个状态。 初始状态；棋盘上没有皇后。 后继函数；把一个皇后添加到棋盘上的任何空格。 目标测试：4个皇后都在棋盘上，并且互相攻击不到。 在这个形式化中，我们需

7、要调查16X15X14X13个可能的序列。更好的形式化方法是禁止把一个皇后放到任何可能被攻击的格子里： 状态：摆放n个皇后(0n4)的安排，要求最左侧n列里每一列一个皇后，保证没有一个皇后能攻击另一个。 后继函数：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从4万多降到3。,如果是八皇后呢？ 在这个形式化中，需要调查64X63XX57 3X1014个状态 状态：摆放n个皇后(0n8)的安排，要求最左侧n列里每一列一个皇后，保证没有一个皇后能攻击另一个。 后继函数：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的

8、形式化把四皇后问题的状态空间从3X1014降到2057，解就容易找到了。对于100个皇后，初始的形式化约有10400个状态，而用改进的形式化方法约有1052个状态这是一个相当大的缩减，但是仍然太大。我们以后将给出一个简单算法，可以处理百万皇后问题。,现实世界问题,我们已经看到寻径问题是如何根据特定的位置和沿它们之间的连接进行转移而定义的。寻径问题在实际中有许多应用。诸如计算机网络的路由、军事行动的规划、生产调度问题、排课问题，以及飞机航线旅行规划系统等等。这些问题都是典型的描述起来复杂的问题。,考虑一个飞机航线旅行问题的简化例子，设定如下： 状态：每个状态由位置（例如机场）和当前的时间来表示。

9、 初始状态：由具体问题而定。 后继函数：返回的状态是下列因素的结果：乘坐的航班，起飞时刻距当前时刻的时间差加上从当前机场到另一个机场所需要的飞行时间。 目标测试：我们是否在某个预定的时刻到达目的地？ 路径耗散：取决于金钱的花费、等待的时间、飞行时间、过海关和入境的过程、座位的质量、一天中的哪个时间段、飞机类型、飞行常客的里程奖等。,商业旅行建议系统使用了这种问题形式化的方法，同时要考虑很多附加的复杂因素以应付航空公司强加的繁复的收费结构。然而，任何经常作飞机的乘客都知道并不是所有的飞行旅行都能够按计划顺利进行。好的系统应该包括应急计划。 旅行问题与寻径问题有很近的关系，但是有很重要的不同。例如

10、多个城市之间的旅行问题，从长春出发到其他19个城市中的每一个至少一次最后在回到出发地这样一个问题。如寻径一样，行动还是对应临近城市之间的旅行。然而，状态空间就不一样了。每个状态不仅必须包括当前所在的位置，还必须包括已经访问过的城市。因此初始状态可能是“in长春;visited长春，一个中间状态可能是”in上海； visited长春，沈阳、上海“，而目标测试应该是检测是否在长春并且已经访问过所有的20个城市。其他实际问题,解的搜索,在对一些问题形式化之后，我们现在开始考虑如何对它们求解，这是通过在状态空间中的搜索完成的。下面讨论的搜索技术使用显式的搜索树，搜索树是由初始状态和后继函数共同生成的，

11、同时也定义了状态空间。下图是一个简化的罗马尼亚道路图,Hirsova,86,Eforic,一个简化的罗马尼亚道路图,下图显示了为寻找从Arad到Bucharest的路径对搜索树进行的某些扩展,初始状态,扩展Arad之后,扩展Sibiu之后,非形式化算法Tree-Search,1.根据问题初始状态初始化搜索树； 2.While(不满足结束条件时) 2.1 If(没有可扩展的结点) 返回失败信息； 2.2 根据某种策略选择一个可扩展叶子结点； 2.3 If（当前结点满足目标状态）返回解的信息； Else 将该结点（可扩展结点）加入到搜索树中； ,该算法如何进行优化？,搜索树中节点的表示有多种方式，

12、不过我们可以假设节点是一个包含五个要素的数据结构： 状态：状态空间中与该方法相对应的格局； 父节点：搜索树中生成该节点的节点； 行动：由父节点产生该节点所采取的操作； 路径耗散（成本）：从初始状态到该节点的路径耗散，一般记为g(n)，路径有父指针表示； 深度：从根节点到该节点所经路径上的步数。,节点与状态的区别？,父节点,节点,状态,行动=Right,深度=3,路径耗散=3,节点产生构造搜索树的数据结构，每个节点都具有父节点，状态和各种记录域，图中箭头是由子节点指向父节点的指针。,度量问题求解的性能,完备性：当问题有解时，这个算法是否能保证找到一个解？,空间复杂度：执行搜索的过程中需要多少内存

13、？,时间复杂度：找到一个解需要花费多少长时间？,最优性：该搜索策略是否能找到最优解？,时间和空间的复杂性度量往往要与问题难度的某种度量一起考虑，在理论计算机科学中，一个典型的度量是状态空间的大小。因为状态空间图被视为要输入到搜索程序的显示数据结构。在AI 中，状态空间图是由初始状态和后继函数隐含地表示的，经常是无限的，它的复杂度根据下列三个值来表达：,B，分支因子；d，最浅的目标节点的深度；m，状态空间中任何路径的最大长度。 时间复杂度一般根据搜索过程中产生的节点数目来度量，而空间复杂度则根据在内存中存储的最大节点个数来度量。,无信息搜索,无信息搜索算法是经典计算机科学(Horowitz和Sa

14、hni,1978)和运筹学（Dreyfus,1969)的一个中心话题，1988年Gallo和Pallottino给出了相关问题的综述文章。 搜索问题 回溯策略 图搜索策略 无信息图搜索：广度优先、代价一致搜索、深度优先、深度有限搜索、迭代深入深度优先搜索、双向搜索、无信息搜索策略的比较、避免重复状态。,人类的思维过程，可以看作是一个搜索的过程。从小学到现在，你也许遇到过很多种智力游戏问题，比如说传教士和野人问题：有3个传教士和3个野人来到河边准备过河，河岸有一条船，每次至多可供2人乘坐。问传教士为安全起见，应如何规划摆渡方案，使得任何时候，在船上与河的两岸野人数目总是不超过传教士数目（但允许在

15、河的某一侧只有野人而没有传教士）？如果要做这个智力游戏，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？这就是搜索问题。,搜索问题,经过反复努力和试探，你终于找到了一种解决方法。在你高兴之余，你可能马上会想到，这个办法所用的步骤是否最少？也就是说，它是最优的吗？如果不是，如何才能找到最优的办法？你是学过计算机程序设计的学生，你考虑过在计算机上又如何实现这样的搜索？这些问题就是我们要学习的内容。,一般而言，很多问题求解过程可以转化为状态空间的搜索问题。比如，前面讲过的传教士与野人问题，当用在河左岸的传教士人数、野人人数和船的情况表示问题时

16、，该问题的初始状态可以用三元组表示为（3，3，1），结束状态可以表示为（0，0，0），而中间状态可以表示为（2，2，0）、（3，2，1）、（3，0，0）等，每个三元组对应了三维空间上的一个点。而问题的解，则是一个合法状态的序列，其中序列的第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态，介于它们之间的是中间状态。除了第一个状态外，该序列中任何状态都可以通过一条规则由与它相邻的前一个状态转换得到。下页的图给出了一个搜索问题的示意图。含义是如何在一个比较大的问题空间中，只通过搜索比较小的范围，就找到问题的解。寻找这样的序列过程称为搜索。,搜索方法,从搜索方式上来讲，搜索可以划分为两大类，即盲目搜索和启发式搜索。 所谓盲目搜索，就是未利用问题的知识，采用固定的方式生成状态的方法。显然这种方法的搜索效率是低下的，但方法具有通用性。当一时难以找到求解问题的有效知识时，是一种不得不采用的方法。 所谓启发式搜索，与盲目搜索正好相反，它利用问题的知识，缩小问题的搜索范围，选择那些最有可能在（最优）解路径上的状态优先搜