3问题求解及搜索技术要点-copy 北航6系人工智能课件.pptx

《3问题求解及搜索技术要点》 在人工智能领域，问题求解与搜索技术是核心研究内容之一。问题求解是指在给定条件下，寻找一个能够有效解决特定问题的算法，这一过程通常需要在有限的步骤内完成。问题求解在传统软件与AI软件之间存在显著差异。传统软件侧重于解决可以通过数学精确描述的良结构问题，如解方程，而AI软件则致力于处理那些难以直接用数学模型描述的不良结构问题，如几何证明、逻辑推理等，这些问题往往需要通过搜索策略来求解。 一、问题求解的基本方法 1. 基于状态空间的问题求解方法：这种方法将问题表示为一系列的状态，通过定义状态之间的合法变换规则来寻找从初始状态到目标状态的路径。例如，经典的汉诺塔问题就是一个典型的状态空间问题。在汉诺塔问题中，需要通过一系列的移动操作，把所有盘子从一根柱子移到另一根柱子，且任何时候大盘子都不能放在小盘子之上。每一步操作都是从一个状态转换到另一个状态，直到达到目标状态。 2. 基于问题空间的问题求解方法：这种方法强调问题分解，通过解决子问题来解决整个问题。以3个柱子上的盘子为例，要将所有盘子从A柱移动到C柱，可以先将A柱上的盘子移至B柱，再移至C柱，最后将A柱上的剩余盘子通过B柱逐个移至C柱。问题空间法通过递归地定义子问题，构建与或图，以解决问题。 3. 基于博弈搜索的问题求解方法：在游戏策略中，通过分析不同决策可能带来的结果，选择最优的行动路径。这种方法广泛应用于棋类游戏，如围棋、国际象棋等，通过评估每一步可能的走法对胜负的影响，来决定最佳的下一步。 二、搜索技术 搜索技术是问题求解的关键，它在状态空间或问题空间中寻找解决方案。搜索算法分为两类：盲目搜索和启发式搜索。盲目搜索如深度优先搜索（DFS）、广度优先搜索（BFS）等，它们仅依据搜索路径进行决策，而不考虑问题的具体特性。而启发式搜索如A*搜索，结合了问题的评估函数，以更有效地找到目标状态。 状态空间法和问题空间法中的搜索技术都涉及到状态空间的构建和搜索空间的探索。状态空间由所有可能的状态组成，而搜索空间则包括在解决问题过程中遇到的所有状态。问题的解径是连接初始状态到目标状态的路径，搜索的目标就是找到这条路径。 问题空间法中的与或图是一种有效的表示工具，它反映了问题的分解结构。"与"节点表示问题的解决需要其所有子问题的解决，而"或"节点则表示问题的解决只需其子问题中的任意一个得到解决。 总结来说，问题求解与搜索技术是人工智能的重要组成部分，它们通过状态空间和问题空间的概念，以及各种搜索策略，帮助计算机解决复杂的问题。无论是基于状态的转换还是问题的分解，这些方法都在不断地推动人工智能领域的发展，使其在处理实际问题时展现出越来越强的能力。