人工智能基础-高济-25282AI-3本

人工智能的基础，浙江大学计算机学院高济，实现4启发式检索的关键因素是启发式检索有助于提高检索效率和解决组合爆炸问题，相关研究成为人工智能形成和长期的重要议题之一，产生了许多成熟的研究成果，至今仍然是启发式检索1 )搜索算法的可采用性定义：在搜索图中存在从初始状态节点到目标状态节点的解答路径的情况下，如果一个搜索算法始终找到最短(成本最小)的解答路径，则该算法有可能被采用。 宽度优先的检索算法可以采用，但检索效率差。 发现通过评估函数f*(n)=g*(n) h*(n)f*(n)节点n的最短(成本最小)解答路径时的实际路径成本(长度)。 g*(n)此路径之前(从初始状态节点到节点n )的成本。 h*(n)在此路径之后(从节点n到目标状态节点)的成本。 在存在多个目标状态的情况下，设h*(n )在h*(n，ngi )中最小。 将评价函数f与f*进行比较，f(n )、g(n )、h(n )分别是f*(n )、g*(n )、h*(n )近似值. 1 )可采用搜索算法，理想情况： g(n)=g*(n )，h(n)=h*(n )，在搜索过程中每次正确选择，不扩展相关节点。 由于g*(n )和h*(n )是未知的直到找到最短解答路径，因此设计该理想的评价函数几乎是不可能的，而且在复杂的应用领域中，设计接近f*的f往往是困难的。 一般来说，g(n )的值容易根据至今为止生成的搜索树进行计算，因此不需要对计算式进行特别定义。 例如，假定节点深度d(n )为g(n )，则g(n)g*(n )。 但h(n )的设计依赖于启发式知识的应用。 如何挖掘适当的启发式知识是设计评价函数或算法a的关键。 w(n)不适合，因此错误地选择节点d进行扩展。 p(n)是h*(n )的接近h(n )的值，其是如果假定与目标状态节点相比，节点n没有被阻止用于每个位置偏移量棋牌，则移动到与目标状态对应的位置所需的行走的总和。 p(n )比w(n )更接近h*(n )。 这是因为p(n )不仅考虑位置偏移的原因，还考虑位置偏移的距离(移动次数)。 应用了启发式函数p (n ) (不是w (n ) )的八数字问题搜索图：参照图2.10。 如果算法a的可采用性确保h(n)h*(n )，那么a可被采用且被称为A*。 宽度优先算法h(n)0h*(n )确保搜索最短路径。 在八数字游戏采用w(n )和p(n )作为启发式函数的情况下，所有算法a都能够采用。 4、实现启发式搜索的重要因素，2 )测量启发式函数的强弱及其影响h(n )接近h*(n )的程度启发式函数的强弱。 h(n)h*(n )，差大时，h(n )过弱，开放表中节点排序的误差大，生成大的搜索图的h(n )-h * (n )，h (n )过强，算法a失去了可接受性，无法确保最短解答路径。 h(n )始终等于h*(n )是理想的，但无法设计。 设计接近，h*(n )的h(n)始终应用A*算法寻找问题解答的关键。 当总是存在h1(n)h2(n)h*(n )时，算法A1和A2得到t(A2)t(A1)。 采用在w(n)p(n)h*(n )、p(n )扩展后的节点的总数t(w(n ) )。 宽度优先法解决八数字问题，h(n)0，搜索树庞大。 3 )设计h(n )的实用思路与设计相近，经常问题h * (n )的h(n )问题：随着问题解决任务的复杂性增加，设计变得更加困难，h(n )的计算量往往变得庞大。 对于搜索成本过高的路由选择成本，h(n )的计算成本增加。 3 )设计h(n )的实用思路，消除h(n)h*(n )的约束，使h(n )的设计变得容易，但失去可采用性：通过牺牲在许多实用情况下找到最佳答案(最短解答路径)所不需要的容许性，使h(n )设计简化和计算h(n )的工作量减少。分析评估函数f(n)=g(n) h(n ) :优先考虑先进入到h(n)0的开放表中的节点，先进入的节点n具有较小的g(n )值，倾向于接近宽度优先搜索策略g (n )=0，之后进入到开放表中的节点具有优先级评估函数f(n)=g(n) wh(n )，w用作权重：搜索图的浅层(上部) 对w取较大值，减小g(n )所占的比例，强调启发式函数的作用，对加速向深度方向的搜索的深层3354进行搜索，使w为较小值，从而求出g(n )的常数5回溯策略和爬山法，简单的搜索策略： g(n)0，f(n)=h(n )，局部顺序可简单地只对新扩展的子节点排序，适用于不寻求最佳答案的问题解决任务。 1 )登山法实现启发式搜索的最简单方法。 像人攀登那样，如果爬得好，总是选择最陡的地方，爬得快。 求函数极大值问题非数值解法，依赖启发式知识，探究性地接近峰值。 适用于逐步精简的问题。 登山法的特征：从只能向上、不能向后退、简化搜索算法的当前状态节点开始扩展的子节点中，将h(n )最小的子节点(对应于最接近顶点的登山路径)作为下一个考察和扩展的节点，其馀子节点全部被废弃。 由于不需要保存扩展的节点，因此不需要设置OPEN表和CLOSE表。登山方法对于单极值问题(登上单峰)有效且简便，对于极值多的问题，无力达不到上次峰值：达不到峰值。 5回溯策略和登山方法；2 )回溯策略有效地克服登山方法所面临的困难，每次保存扩展后的子节点，按照h(n )的值从小到大的顺序进行排序。 相当于在登山中记住了路径的分岔路径的路径搜索失败时上溯(后退)，向其他路径方向搜索(参照图2.11 )。 递归进程3354实现回路策略的一种有效方法：该算法被称为BACKTRACK(n )，并且参数n是当前扩展的节点，并且初始调用时间点n将被分成两部分： *确定当前节点n的状态，*检索工作3354 三种失败状态：错误状态(如传教士和野人的问题所述)、旧状态的再现(八数字游戏的板布局的再现导致搜索算法的死亡)、状态节点的深度超过预定极限(例如，在八数字游戏中，解答路径不超过六步)。 2 )回溯策略、回溯条件检索进入“闭路”，在该算法的第(4)节中定义。 失败状态由算法的第(2)句指示，在第(7)句中执行回溯。 解答路径生成器从对应于目标状态节点的空表递归地返回PATH。 2 )影响背光策略、背光算法效率的因素背光次数：背光3354在搜索失败状态时的一种互补行为可以精确地选择节点3354以进行下一次搜索，从而显着减少背光。 所设计的启发式函数h(n )很重要。 四皇后问题例：在棋盘的44个区域放置4个皇后棋子，满足制约：各行、各列、对角线只允许女王出现1人。 避免女王之间的冲突。 问题状态在列表l中指示，其中l的元素是盘中女王的位置ij(1i，j4 )。 为了简化解答的检索，限定按照从盘上到下的顺序在盘的4行放置女王。 空的表l在表示初始状态的表l中包含满足制约的4个女王位置的情况下，如果到达目标状态的女王的位置发生冲突，则意味着成为不正当的状态(失败状态)。 在设计D(n )中，作为启发式函数h(n)，具有在状态n下最新的皇后位置(棋盘格子)所处的长对角线的长度(对角线上的格子的数量)的值。 四皇后问题检索图：见图2.12和图2.13。2 )背光策略，减少背光次数： d (n )应用背光次数3次，深度优先级3354每次以随机或固定次序(网格在相同行中的次序)对新产生的子节点进行排序，这种盲搜索面临许多背光。 6状态空间抽象和生成-支持测试法、高效搜索大型状态空间。 1 )减少状态空间抽象化探索量的重要技术适合于寻找令人满意的解答，将状态空间按子问题分为个子问题，构成抽象空间。 抽象空间中的搜索步骤与实际状态空间之间的对应关系：图2.14因为前者的一个搜索步骤(一个子问题)对应于后者的许多步骤，所以抽象空间非常小并且搜索非常快。 驾驶汽车长途旅行的例子：大致路线通过全国交通图，大致路线的详细路线3354决定通过沿道城市的交通详情。 状态空间抽象的本质将搜索注意力集中到解决问题的关键因素上。 复杂的问题可以采用多层次的抽象化。 6状态空间抽象化和生成-测试法，2 )生成-测试法检索过程由两个部件协作完成：可能解的生成器，不正确的测试生成器的性能依赖于不完整性和冗馀性，可以生成所有可能的解，只生成一次。 生成器和测试器的工作往往交替进行。 关键问题在生成器和测试器之间分配知识。 知识丰富的生成器提供了高搜索效率。 层次的生成-测试方法：参照图2.15的整个问题解决过程，可以看作是连续搜索部分解答的过程，各层次的生成-测试方法服务为搜索部分解答、解答分类、分类树的层次化目的设计了强大的测试器，尽快删除不适当的候补解答(在搜索树层)，大幅减少搜索量7、启发式搜索的适用性研究、启发式搜索的评价函数均可设计为全局或局部评价器。 启发式检索很少被应用于作为人工智能系统的顶层控制结构。 启发式检索技术的应用面临三个重要选择：搜索确定性或非确定性检索方式目标状态本身，或者达到目标状态的解答路径(通常表现为状态或操作符序列)。 查找一个或全部或最佳答案。 追溯最优优先和深度优先，效率也非常低。 避免倒退是人工智能研究的重要课题，研究明显倾向于确定的方式。 2.2问题是约定事项，问题是约定事项是人们解决问题的常用策略：转化为需要同时处理复杂问题的比较简单的子问题后分别解决：只有在这些子问题全部解决时才解决问题，问题的解答由子问题的解答联合构成。 问题的汇总可以递归进行，把问题转换成原来的问题集合。 原始问题不能或不需要转换简单的“原子”问题。 主要内容：问题摘要的描述和图搜索和图搜索的启发式搜索，2.2.1问题摘要的描述，广义的状态空间搜索技术，状态空间同样可以表示为二项组： SP=(S，o )问题状态可以表示为子问题状态的联合，操作算子的执行会导致问题的转换， 在三种情况下：状态转换333-54可以将问题从先前状态转换到下一状态，其中问题分解器333-54可以将问题分解为可以同时处理的子问题，但是不改变问题状态。 基于状态变化的问题分解首先引起状态变化，实现问题的分解，其实际上是前两个操作的协同执行。 字符改写问题例：初始状态是字母列表(ABC )，目标状态是只包含字母x、y、z的字母列表，为问题提供Split(n )，为状态的变迁提供字母列表的改写规则。2.2.1问题的摘要描述和应用图问题的摘要策略得到的状态空间图：参照图2.16逻辑“与”关系，用圆弧连接若干节点之间的关联弧，指示问题分解为子问题，所有子问题解决后才联系到问题的解决，子问题的状态描述联系到逻辑“或”关系：问题的分解有各种各样的方法，如果有能够对应问题(子问题)激活多个改写规则的分解方式或激活规则，则导致最终解