人工智能课件搜索问题.ppt

《人工智能课件搜索问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、棋子可以滑入到空位中。游戏的目的是要达到一个特定的目标状态。72456831123567847245683172456831724568317245683172456831初始状态行动描述12356784目标测试和计算路径消耗搜索和执行标准的形式化如下：状态；描述了指定8个棋子中的每一个以及空位在棋盘的9个方格上的分布。初始状态：任何状态都可以指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为初始状态。后继函数：用来产生通过四个行动（把空位向Left，right,Up或Down)能够达到的合法状态。目标测试：用来检测状态是否是目标状态。路径耗散：设每一步的耗散值

5、是1因此整个路径的耗散值是路径中的步数。这里的抽象化只保留了游戏规则相关的描述，而忽略所有物理操作的细节。八数码游戏属于滑快问题家族，这类问题经常被用作AI中新的搜索算法的测试问题。这类一般问题已知为NP完全问题，因此对这类问题不要期望在最坏情况下找到好于我们后面要讲述的算法。八数码游戏共有9！/2=181440个可达到的状态，这是很容易求解的。15数码问题则大约有1.3万亿个状态，用最好的搜索算法最优化地求解一个随机的实例需要几毫秒。24数码游戏则大约有1025个状态，用目前的机器和最优化算法求解随机的实例仍是相当困难的。四皇后问题在一个4×4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆

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

7、何空格。目标测试：4个皇后都在棋盘上，并且互相攻击不到。在这个形式化中，我们需要调查16X15X14X13个可能的序列。更好的形式化方法是禁止把一个皇后放到任何可能被攻击的格子里：状态：摆放n个皇后(0n4)的安排，要求最左侧n列里每一列一个皇后，保证没有一个皇后能攻击另一个。后继函数：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从4万