《人工智能通识与进阶》 第三章 搜索与问题求解

第三章

搜索与问题求解1问题与导读2如果说智能系统的终极目标是“学会解决问题”，那么搜索便是实现这一目标最原始、最根基的能力。在智能体能够学习与归纳之前，它首先必须拥有探索可能、评估结果、并在复杂环境中找到路径的能力——这正是早期人工智能的核心命题：如何让机器自己“想办法”？问题与导读3对人类而言，规划路线或推演棋局似乎自然而简单。但对计算机来说，每一个决策都面对着一个巨大的状态空间。问题与导读4无信息搜索核心原理：仅依靠问题初始状态、目标状态与固定遍历规则盲目拓展节点，不借助任何额外领域知识与偏向性引导完成搜索。典型方法：广度优先搜索、深度优先搜索、深度受限搜索。启发式搜索局部搜索元启发式算法核心原理：引入自定义启发函数评估节点优劣，优先拓展更接近目标的优质节点，以减少无效搜索、提升求解效率。典型方法：贪婪最佳优先搜索、A*搜索、递归最佳优先搜索。核心原理：从单个初始解出发，仅在当前解的邻域内迭代寻找更优解，聚焦局部空间快速优化，不遍历完整解空间。典型方法：爬山法、模拟退火算法、禁忌搜索。核心原理：不依赖特定问题结构，通过全局探索与局部开发结合的通用策略，在大规模解空间中高效逼近最优或近似最优解。典型方法：遗传算法、粒子群优化算法、鲸鱼优化算法。本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法5本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法673.1无信息搜索问题求解与形式化问题求解是智能体实现目标的核心能力。一个基于目标的智能代理通过感知环境信息，规划并执行一系列动作以达到期望的目标状态。问题形式化是将现实世界问题抽象为一个形式化搜索问题的基石，它决定了搜索过程的状态空间和可行路径。一个问题的完整形式化表述必须精确定义以下五个组成部分：（1）状态空间：涵盖了问题在抽象过程中所有可能出现的状态。（2）初始状态：搜索代理开始进行搜索的起点。（3）动作（或后继函数）：该函数定义了在任何一个给定状态下，代理可以执行的所有可能动作，以及每个动作所导致的后继状态。（4）目标测试：这是一个用于检验某个给定状态是否满足目标条件的函数。（5）路径代价：每一个动作或状态转移需要分配一个代价（用数值表示，通常要求≥0），整个解决方案的路径代价是所有步骤代价的累加和。83.1无信息搜索问题求解与形式化例：八数码问题状态：指定了每个方格上的滑块编号，空格看作一个特殊的滑块；初始状态：任意给定的滑块排列；动作：将空格与相邻的滑块交换位置（即向左、向右、向上、向下移动滑块）；目标测试：是否与给定的方块布局一致；路径代价：每移动一次计为1步。玩家的目标是通过反复滑动与空白格相邻的滑块，将棋盘重新排列成一个特定的目标状态。93.1无信息搜索问题求解与形式化例：过河问题一名农夫需要将狼、羊和卷心菜从河的一岸运送到另一岸，船每次只能由农夫驾驶，并且最多只能再携带一个物体。在任意时刻，如果狼与羊单独留在同一岸，则羊会被狼吃掉；如果羊与菜单独留在同一岸，则菜会被羊吃掉。目标是在不违反上述约束的前提下，将所有对象安全运送至对岸。

但并非所有状态都是合法状态103.1无信息搜索问题求解与形式化例：机器人装配问题一台工业机械臂需要将多个分散的零件组装成目标部件。机械臂可通过关节的连续运动控制末端执行器的位置与姿态，每次动作可抓取一个零件并将其移动到指定位置，但过程中需避免机械臂与工作台、未装配零件发生碰撞。在任意时刻，若零件的装配姿态偏差超过阈值，或机械臂施力过大，会导致零件损坏或装配失败。目标是在不出现碰撞、零件损坏的前提下，通过机械臂的动作完成所有零件的组装。113.1无信息搜索问题求解与形式化例：机器人装配问题状态：机器人关节的实数值坐标（如机械臂各关节的角度）与待装配零件的空间位置与姿态（如零件的三维坐标、朝向）。初始状态：机器人处于初始待机位姿，待装配零件分散摆放在工作台（未组装状态）。动作规则：机器人关节的连续运动（如机械臂的平移、旋转），或末端执行器的抓取/释放操作；每次动作对应关节/零件的状态变化。目标测试：待装配零件完成指定的拼接组合，形成目标产品/子部件的结构。状态约束：需避免一些非法状态，如机器人关节运动超出物理极限；零件/机械臂与工作台、其他物体发生碰撞；零件装配时受力过大导致损坏。路径代价：通常以执行时间为准（也可定义为能耗、装配精度误差等），目标是最小化代价完成装配。123.1无信息搜索搜索树与图搜索在问题被形式化表述之后，搜索算法的核心任务是在庞大的状态空间中寻找解决方案。为了实现这一目标，算法通常不会直接操作原始的状态空间图，而是显式或隐式地构建并探索一棵搜索树。搜索树是搜索过程的一种抽象表示，其构建遵循以下基本思想：（1）根节点：对应于问题的初始状态。（2）节点扩展：为了探索一个节点（即一个状态），算法需要应用问题的后继函数。该函数会生成该节点（状态）的所有合法后继状态，并在搜索树中为每一个后继状态创建一个新的子节点。连接父节点与子节点的边则代表了导致状态转换的动作。（3）叶节点（即没有后继的节点）：分为两类：一是待探索的节点（位于搜索前沿，或称为fringe集合）；二是无法继续扩展的节点（如达到深度限制或没有合法动作的状态）。（4）解路径：在搜索树中，从根节点（初始状态）到任何一个满足目标测试的节点（目标状态）的路径，就构成了问题的一个解。133.1无信息搜索搜索树与图搜索树搜索算法的基本流程如下：步骤1：初始化，将搜索树的根节点（初始状态）加入待探索集。步骤2：根据特定的搜索策略（如广度优先、深度优先等），从待探索集中选择一个节点并将其移除。步骤3：对该节点进行目标测试。如果它是目标状态，则成功返回找到的解决方案路径。步骤4：如果该节点不是目标状态，则对其进行扩展：将其所有不在树中的后继状态作为子节点加入搜索树，并将这些新生成的节点加入到待探索集中。步骤5：如果待探索集为空，则搜索失败，返回无解；否则返回步骤2。然而，树搜索可能会探索重复状态，导致计算效率急剧下降，甚至陷入死循环！例143.1无信息搜索搜索树与图搜索为了解决重复状态的问题，引入图搜索的思想。图搜索在树搜索框架的基础上，增加了一个已探索集，用于记录所有已经扩展过的状态。图搜索算法的基本流程如下：步骤1：初始化，将根节点加入边集，已探索集初始化为空。步骤2：根据策略从边集中选择并移除一个节点。步骤3：将该节点对应的状态加入已探索集。步骤4：进行目标测试，如果是目标则返回解。步骤5：扩展该节点，但仅将那些对应的状态既不在待探索集中也不在已探索集中的后继节点加入待探索集和搜索树。步骤6：如果待探索集为空，则搜索失败；否则继续步骤2。153.1无信息搜索无信息搜索算法无信息搜索也称为盲目搜索，是指在进行搜索时，除了问题本身定义（状态空间、后继函数、目标测试等）提供的信息外，不使用任何关于状态优劣的额外领域知识来指导搜索方向。几类经典的无信息搜索算法如下：（1）广度优先搜索；（2）深度优先搜索；（3）深度受限搜索；（4）迭代加深搜索；（5）双向搜索。163.1无信息搜索无信息搜索算法（1）广度优先搜索广度优先搜索的策略是优先扩展深度最浅的未扩展节点。即先扩展所有深度为0的节点，然后是所有深度为1的节点，依此类推。173.1无信息搜索无信息搜索算法（2）深度优先搜索深度优先搜索的策略是扩展深度最深的未扩展节点。即沿着一条路径一直深入，直到无法继续为止，再回溯。183.1无信息搜索无信息搜索算法（3）深度受限搜索深度受限搜索的策略是深度优先搜索的改进，引入一个搜索深度的限制L。节点深度超过L时，被视为无后继节点，不予扩展。（4）迭代加深搜索迭代加深搜索的策略结合了广度优先搜索的完备性、最优性与深度优先搜索的空间效率。它通过反复调用深度受限搜索来实现，每次迭代的深度限制逐次增加，直到找到目标。每次深度限制的增加，都意味着一次完整的深度优先搜索，但只探索到当前限制的深度。（5）双向搜索双向搜索的策略是同时运行两个搜索过程——一个从初始状态向前搜索，另一个从目标状态向后搜索（假设动作可逆）。当两个搜索在中间某处“相遇”时，即当前向搜索的待探索节点状态出现在后向搜索的已探索集中（或反之），则找到一个解。无信息搜索算法为问题求解提供了基础工具，它们构成了人工智能问题求解的基础工具箱。本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法19203.2启发式搜索无信息搜索的局限性组合爆炸、效率低下•算法探索的节点数量随问题规模呈指数级增长。缺乏问题导向性•搜索过程与问题无关，无法区分节点的“潜力”。

实际应用受限•由于效率瓶颈，无信息搜索在较复杂的问题中，往往无法在合理时间内返回解，缺乏实用价值。无信息搜索的局限性启发式搜索算法的研究213.2启发式搜索启发式与评价函数

启发式函数的质量直接决定了启发式搜索的效率。223.2启发式搜索启发式搜索算法路径搜索问题：在地图上，从城市A出发，找到到达目标城市J的最短路径。233.2启发式搜索启发式搜索算法

243.2启发式搜索启发式搜索算法（2）A*搜索A*搜索是一种最著名、应用最广泛的启发式图搜索算法，它结合了统一代价搜索的最优性保证和贪婪最佳优先搜索的导向性。253.2启发式搜索启发式搜索算法

263.2启发式搜索启发式搜索算法RBFS求解路径搜索问题示例图（1）273.2启发式搜索启发式搜索算法RBFS求解路径搜索问题示例图（2）283.2启发式搜索启发式搜索算法RBFS求解路径搜索问题示例图（3）293.2启发式搜索启发式搜索算法

本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法30313.3局部搜索局部搜索思想与特点局部搜索是一类直接对完整候选解进行迭代优化的启发式方法，其核心在于通过逐步改进当前解来逼近最优或可行解。其状态空间由所有完整的候选解构成，而非部分解（如N皇后问题中完整的棋盘布局）。其搜索机制是从初始解出发，在其邻域（通过微小扰动得到的一组邻近解）中选择更优解进行移动，实现迭代优化。局部搜索的主要特点：（1）高效利用内存；（2）融合启发式与随机性；（3）适用于优化与约束满足问题；（4）路径不可追溯；（5）不完备且易陷局部最优。323.3局部搜索爬山法（1）爬山法爬山法是一种简单而直观的局部搜索算法，它采用贪心策略，从一个随机生成的初始状态（一个完整的候选解）开始，不断向当前状态的邻域中寻找一个能提升解质量的后继状态进行移动。爬山法的流程如下：步骤1：初始化，随机选择一个初始状态current。步骤2：生成current的所有邻近后继状态。步骤3：计算所有后继状态的评估函数值。步骤4：从所有后继状态中，选出评估函数值最优的状态记为neighbor。步骤5：如果neighbor优于current，则将current设置为neighbor（即“移动”到该更优状态）。否则，算法终止，返回current作为解（局部最优解）。爬山法最主要的缺陷之一是经常容易陷入局部最优。333.3局部搜索模拟退火（2）模拟退火模拟退火算法是受冶金学中退火过程启发而设计的一种随机优化算法。其核心思想在于：在搜索初期，算法以较高的概率接受比当前状态更差的移动，以此来跳出局部最优的“陷阱”；随着搜索的进行，这一接受差解的概率逐渐降低，算法最终收敛于一个稳定的（希望是全局最优的）状态。模拟退火算法的流程如下：

343.3局部搜索禁忌搜索（3）禁忌搜索禁忌搜索是一种通过引入短期记忆机制来避免循环和逃离局部最优的智能局部搜索算法。其核心思想是：明确禁止搜索过程在近期内重新访问已经探索过的区域，从而强制探索新的、有希望的方向。禁忌搜索的核心在于主动地禁止搜索过程在短期内回到最近访问过的状态。这是通过维护一个“禁忌表”的记忆结构来实现的。在基本的局部搜索（如爬山法）中，算法可能会在两个或多个状态之间来回震荡，或者围绕一个局部最优解打转，无法有效逃离。禁忌搜索通过记录最近的搜索历史，临时性地将某些移动或状态标记为“禁忌”，从而打破这种循环，驱使搜索走向新的区域。禁忌搜索通过暂时性地排除近期访问过的状态，求解器能够从当前已探索的区域中移开，从而在原则上避免了陷入局部最小值，并促进对解空间更广泛的探索。禁忌搜索通常和其他局部搜索方法进行结合，为其增加避免重复访问的能力。353.3局部搜索局部束搜索

本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法363.4路径搜索算法路径搜索算法基于离散状态空间的启发式搜索与局部搜索可以处理诸如八皇后、八数码等逻辑问题。如何处理连续、高维的状态空间路径搜索算法！离散状态空间连续状态空间373.4路径搜索算法RRT38

3.4路径搜索算法RRT*39（2）渐近最优的快速搜索随机树渐近最优的快速搜索随机树RRT*是RRT算法的改进版本，在保留快速探索特性的同时，通过引入“重选父节点”和“重布线”两个优化机制，使算法具备渐近最优性。RRT*在每次扩展新节点后，会在其邻域内寻找潜在更优的父节点，以降低从起点到新节点的路径代价。3.4路径搜索算法RRT*40（2）渐近最优的快速搜索随机树同时，RRT*还会检查新节点是否能为邻域内已有节点提供更优路径，并进行重连接优化。随着采样次数增加，RRT*生成的路径代价会逐渐收敛至理论最优解，从而在概率完备的基础上实现了渐近最优性，特别适用于对路径质量有要求的机器人运动规划和自主导航任务。3.4路径搜索算法RRT*41

3.4路径搜索算法RRT*42

本章目录3.1无信息搜索3.2启发式搜索3.3局部搜索3.4路径搜索算法3.5扩展方法433.5扩展方法遗传算法44元启发式算法可视为一类引入随机性的高级启发式方法，结合了随机性和确定性策略来寻找优化问题的近似解。本节将以遗传算法（GeneticAlgorithm,GA）作为元启发式的经典范例进行剖析。遗传算法的核心思想是通过选择、交叉、变异等遗传操作迭代优化种群，最终逼近最优解。3.5扩展方法遗传算法45遗传算法整体流程可描述如下：步骤1：根据问题的解空间，随机生成

N个个体，每个个体用特定的编码方式表示，形成初始种群。步骤2：定义适应度函数，计算种群中每个个体的适应度值。步骤3：根据适应度值，从当前种群中选择若干个体作为父本，用于产生下一代。步骤4：将选中的父代个体两两配对，以一定的交叉概率对每对父代的编码串进行交换，生成新的子代个体。步骤5：对交叉后得到的子代个体，以一定的变异概率随机改变其编码串中的部分基因位，生成变异后的个体。步骤6：用交叉和变异后得到的子代个体，替换原种群中的部分或全部个体，形成新一代种群。步骤7：判断是否满足终止条件，若满足则停止并输出当前最优个体；否则返回步骤2，进入下一轮迭代。3.5扩展方法遗传算法46以八皇后问题为例，下图展示了用遗传算法求解八皇后问题的过程。种群初始化阶段：此阶段随机生成由4个初始候选解组成的初始种群，每个个体以8位数字串表示，每一位数字对应八皇后问题中“某一列的皇后所在的行号”，例如个体A