与或树（and–or tree）是一种用于人工智能（AI）和计算机科学的图形化形式体系，用于表示问题求解过程和决策结构。它是一种树数据结构，其中每个节点被标记为与节点（AND node）或或节点（OR node）。在与节点中，必须求解所有子问题才能满足父目标；在或节点中，求解任意一个子问题即可。这种区分使得与或树能够建模分解为合取和析取子任务的复杂问题，使其成为自动规划、博弈和逻辑编程等领域的基础工具。
该概念源于早期人工智能关于问题求解和搜索算法的研究。它与博弈树和决策树密切相关，但在对与关系的显式处理上有所不同。与或树通常与深度优先搜索、广度优先搜索和启发式搜索等搜索策略结合使用，并构成AO*（一种用于与或图的最佳优先搜索）等算法的基础。
结构与语义
与或树是一棵有根树，其中每个内部节点具有以下两种类型之一：
- 与节点：仅当所有子节点都满足时，该节点才被满足。这表示子目标的合取。例如，要建造房屋，必须完成地基、墙壁和屋顶（全部必需）。
- 或节点：如果至少一个子节点被满足，则该节点被满足。这表示备选方案的析取。例如，要前往某城市，可以乘坐火车、公共汽车或汽车（任意一种即可）。
叶节点通常是原始目标或终态，其值为真或假。根节点表示整体问题或目标。问题的解对应于满足根的子树，这意味着对于子树中的每个与节点，包含所有子节点；对于每个或节点，恰好包含一个子节点。
历史背景
与或树形式体系在20世纪60年代和70年代于人工智能领域获得 prominence。早期AI系统，如由艾伦·纽厄尔和赫伯特·A·西蒙开发的通用问题求解器（GPS），使用了手段-目的分析，这隐含涉及与或分解。然而，与或树的显式表示在问题求解的教科书和研究中成为标准。值得注意的是，AO算法于20世纪70年代引入，扩展了A搜索算法以处理与或图，从而在具有合取子目标的问题中找到最优解。
在人工智能中的应用
与或树在AI中被广泛用于：
- 自动规划：将计划表示为任务的层次分解。例如，机器人导航计划可能需要移动到某位置（与：避开障碍物、到达目标）或在多条路线中选择（或）。
- 博弈：建模游戏状态，其中玩家必须做出移动（或），并考虑对手的响应（与）。用于国际象棋等游戏的极小极大算法可视为与或搜索的特例。
- 逻辑编程：在Prolog中，解析过程可可视化为与或树，其中目标进行与操作，子句提供或备选方案。
- 专家系统：基于规则的推理通常使用与或结构从前提出发推断结论。
用于与或树的搜索算法
有几种算法在与或树上操作以找到解：
- 深度优先搜索（DFS）：在回溯前尽可能深入地探索一个分支。对于与节点，必须探索所有子节点；对于或节点，第一个成功的子节点可能就足够。
- 广度优先搜索（BFS）：逐层探索节点，确保找到最浅的解。
- AO*：一种最佳优先搜索算法，基于成本估计扩展节点，同时考虑与分支和或分支。它维护一个解图并递归更新成本。
- 带Alpha-Beta剪枝的极小极大算法：用于博弈树，博弈树是与或树的子集，其中玩家和对手交替行动。
这些算法是AI课程中的基础内容，并在许多AI系统中实现。
与其他形式体系的关系
与或树与其他结构密切相关：
- 决策树：在决策树中，每个内部节点表示对属性的测试，分支表示结果。它们用于分类和回归，但通常不具有与节点；它们在某种意义上纯粹是或式的，因为遵循单一路径。
- 博弈树：博弈树表示所有可能的移动和响应。它可视为与或树，其中玩家的移动是或节点（选择移动），对手的移动是与节点（必须考虑所有响应）。
- 与或图：与树不同，图允许共享子问题，避免重复。与或图更通用，用于问题归约。
扩展与变体
基本与或树已有几种扩展：
- 加权与或树：为节点或边分配成本，支持基于成本的优化。
- 概率与或树：纳入不确定结果的概率，用于决策分析和博弈论。
- 带约束的与或树：添加跨子树必须满足的约束，常见于约束满足问题。
这些变体增强了形式体系在现实应用中的表达能力。
当前相关性与研究
虽然现代AI已转向机器学习和深度学习方法，但与或树在符号AI和混合系统中仍然相关。它们用于可解释AI以提供透明的推理结构，并在结合结构化表示的神经网络架构中使用。神经符号AI的研究通常将神经网络与与或树推理相结合，以提高泛化性和可解释性。此外，与或树用于自然语言理解中解析句子为层次结构，以及计算机视觉中的场景理解。
参见
参考文献
- Nilsson, N. J. (1980). Principles of Artificial Intelligence. Tioga Publishing.
- Rich, E., & Knight, K. (1991). Artificial Intelligence. McGraw-Hill.
- Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson.