人工智能：2-4启发式搜索.pdf

### 人工智能：2-4启发式搜索 #### 一、启发式搜索概述 启发式搜索是一种在解决问题时利用启发信息来指导搜索方向的方法。相比于无信息搜索（也称盲目搜索），启发式搜索能够更快地找到解决方案，尤其是在面对复杂的问题空间时。 **无信息搜索**： - 定义：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。 - 特点：不考虑具体问题的信息，仅依赖于搜索算法本身的规则。 - 示例：广度优先搜索、深度优先搜索等。 **启发式搜索**： - 定义：在搜索过程中利用与问题相关的启发性信息，指导搜索向最有希望的方向前进，以加速求解过程。 - 特点：能够显著提高搜索效率，特别是在解决复杂问题时更为有效。 - 示例：A*算法、局部择优A算法等。 #### 二、启发性信息与评估函数 **启发性信息**是指与特定问题相关的知识或经验，这些信息可以用来评估当前状态距离目标状态的距离。 **评估函数**是用来估计节点重要性的函数，通常形式为`f(x) = g(x) + h(x)`： - `g(x)`：从初始节点到当前节点的实际路径成本。 - `h(x)`：从当前节点到目标节点的最佳路径估计成本，这是一种启发式估计。 #### 三、不同类型的启发式搜索 1. **代价树的广度优先搜索**： - 方法：按照节点的成本（而非层次）排序，依次访问节点。 - 步骤： 1. 将初始节点放入OPEN表，设置其成本为0。 2. 如果OPEN表为空，则无解。 3. 取出OPEN表中成本最低的节点放入CLOSED表。 4. 若此节点为目标节点，则找到了解；否则，扩展该节点并将子节点放入OPEN表，并更新成本。 - 示例：通过给出的交通图寻找从S到T的最小交通费用。 2. **动态规划法（改进的代价树广度优先搜索）**： - 目的：解决重复节点问题，避免多次访问同一节点导致的资源浪费。 - 方法：对于到达同一节点的不同路径，仅保留成本最低的一条路径。 3. **代价树的深度优先搜索**： - 方法：类似于普通深度优先搜索，但增加了成本作为选择依据。 - 特点：可能会错过最优解，但在某些情况下可以快速找到可行解。 4. **代价树有界深度优先搜索**： - 方法：限制搜索深度，以避免陷入无限递归或无法终止的情况。 - 特点：可以在有限时间内找到较优解。 5. **局部择优A算法**： - 方法：结合了启发式搜索和局部搜索的特点，主要用于解决特定类型的问题。 - 特点：适用于解决局部最优解即可满足需求的问题。 6. **A算法（全局优先搜索）**： - 方法：基于启发式搜索，采用全局优先策略来选择下一个节点。 - 特点：能够在保证找到最优解的同时，尽可能减少搜索时间。 #### 四、案例分析 **案例：八城市间的交通图** 假设我们有一个包含八个城市的交通图，每个城市之间的连接代表交通线路，线路上标注的数字代表从一个城市到另一个城市的交通费用。目标是从城市S出发，到达城市T，找出总交通费用最小的路线。 **步骤**： 1. 初始化：将起始城市S放入OPEN表，并设置其成本为0。 2. 不断重复以下步骤，直到找到目标城市T或OPEN表为空： - 从OPEN表中选取成本最低的城市。 - 检查该城市是否为目标城市T。如果是，则停止搜索；如果不是，则继续。 - 扩展该城市，将所有未被访问过的相邻城市加入OPEN表，并计算它们的成本。 3. 更新节点成本，并根据成本重新排序OPEN表中的城市。 4. 当找到目标城市T时，搜索结束。 **结果**：通过不断迭代和扩展，最终找到从S到T的最小交通费用路径，并计算出该路径的具体费用。 通过上述案例，我们可以看到启发式搜索如何有效地利用启发性信息来优化搜索过程，从而更快地找到问题的解决方案。