第三章_搜索策略1.pptx

在智能系统中，问题求解通常涉及两种主要的系统类型：知识贫乏系统和知识丰富系统。知识贫乏系统依赖于搜索技术来解决问题，由于缺乏特定知识，它们的效率相对较低。相反，知识丰富系统利用推理技术，基于丰富的知识库，能更直接地找到解决方案，效率较高。 搜索策略是问题求解的核心，主要分为两类：一般图搜索和启发式搜索。一般图搜索不考虑问题的具体特性，而启发式搜索则利用与问题相关的启发式信息来引导搜索，以提高效率并寻找最优解。这两种搜索策略又可以根据是否使用启发式信息细分为盲目搜索和启发式搜索。盲目搜索仅能区分目标状态，按照预设的策略进行，效率不高。启发式搜索则在搜索过程中结合问题特征，使搜索方向更有针对性。 在人工智能中，问题的搜索空间通常是未知的，需要在求解过程中逐步生成。搜索问题包含两个关键要素：搜索目标和搜索空间。状态空间搜索和与或图搜索是两种常见的搜索方法。状态空间搜索基于状态空间法，而与或图搜索则采用问题规约的方法。 状态空间搜索通常涉及宽度优先搜索（BFS）和深度优先搜索（DFS）。BFS首先扩展最近的节点，DFS则深入探索树的分支。这两种搜索都是确定性的，即节点的遍历顺序在搜索空间确定后是固定的。启发式搜索则更具不确定性，因为它根据启发式函数动态选择扩展的节点。 评价搜索策略的标准包括完备性（是否存在解答时策略能否找到）、时间复杂性（找到解答所需时间）、空间复杂性（执行搜索所需的存储空间）以及最优性（是否能找到最高质量的解答）。这些标准用于评估和比较不同的搜索算法。 状态空间搜索在解决各种问题中扮演着重要角色，例如梵塔问题、旅行商问题、八皇后问题和农夫过河问题，以及实际问题如路径规划和机器人行动规划。状态空间表示为二元组（S，O），其中S是所有可能状态的集合，O是导致状态变化的操作算子集合。状态可以抽象为矢量形式，每个状态分量代表问题的一个方面，组合这些分量就构成了具体的状态。 搜索策略是智能系统解决问题的关键技术，它涉及到如何有效地在状态空间中寻找目标状态，以及如何利用信息来优化这一过程。通过理解这些基本概念和技术，我们可以设计出更高效的问题求解系统。