与或图（AND-OR Graph）搜索是一种用于求解**具有子问题依赖关系的复杂问题**（尤其是**可分解为多个子问题且存在“与”“或”逻辑关系**的问题）的搜索方法

与或图（AND-OR Graph）搜索是一种用于求解具有子问题依赖关系的复杂问题（尤其是可分解为多个子问题且存在“与”“或”逻辑关系的问题）的搜索方法，广泛应用于人工智能中的问题求解、规划、定理证明、博弈树分析等领域。

🔹 核心概念：

• “或节点”（OR node）：表示该节点可通过任一子节点的成功求解而成功（选择关系），对应传统搜索树中的分支（如：走A路或B路，任一可行即可）。
• “与节点”（AND node）：表示该节点需所有子节点均被成功求解才能成功（协同关系），常用于任务分解（如：“做一顿饭”需同时完成“买菜” AND “洗菜” AND “烹饪”）。
• 与或图是有向无环图（DAG）或一般有向图，允许共享子问题（避免重复计算），比普通搜索树更紧凑高效。

🔹 典型算法：

• AO 算法（And-Or A）**：启发式搜索算法，是A*在与或图上的推广。
  • 维护一个待扩展的与或图子图；
  • 使用启发式函数 ( h(n) ) 估计从节点 ( n ) 到解图的最小代价；
  • 对每个节点，计算其最优解图代价（OR节点取子节点最小值；AND节点取子节点代价之和）；
  • 通过标记（marking） 和回溯更新传播解图信息，逐步构建最小代价解图。

🔹 关键特点：
✅ 支持问题分解与组合逻辑（AND/OR）；
✅ 可处理不确定性与多路径依赖；
✅ 利用启发式信息提高效率；
❌ 实现较复杂（需维护图结构、标记状态、代价传播）；
❌ 完备性与最优性依赖于启发函数的可采纳性（admissibility）和一致性（consistency）。

# 简化示意：AO* 中节点类型与代价更新逻辑（伪代码片段）
def update_cost(node):
if node.is_or_node():
node.cost = min(child.cost for child in node.children)
elif node.is_and_node():
node.cost = sum(child.cost for child in node.children)
# 若cost变化，向上回溯更新父节点

AO* 与 A* 虽同属启发式图搜索算法，且都使用评估函数 ( f(n) = g(n) + h(n) )，但二者在问题建模本质、数据结构、搜索策略、解的结构及更新机制上存在根本性区别：

🔹 1. 建模对象与图结构不同

• A*：在普通有向图（或树） 上搜索，节点代表状态，边代表单步操作；每个节点仅需找到一条通往目标的路径（“或”关系隐含在分支选择中，但无显式“与”逻辑）。
• AO*：在与或图（AND-OR Graph） 上搜索，节点分为两类：
  • OR节点：对应“选择一个子方案”（如：从路口选左/右/直行）；
  • AND节点：对应“必须同时解决所有子问题”（如：“组装电脑”需“装CPU” AND “装内存” AND “装硬盘”）。
    → AO* 天然支持任务分解与协同求解，而 A* 无法直接表达“全都要”的依赖。

🔹 2. 数据结构差异

🔹 3. 搜索策略与更新机制本质不同

• A*：单向前向扩展，每次从 open 中取 f(n) 最小节点扩展其后继，一旦目标节点出队即终止（最优性由可采纳启发式保证）。
• AO*：双向迭代式局部优化：
  ① 自顶向下：从初始节点出发，沿当前最优解图（按 cost[n] 推导）向下展开未完全求解的叶节点（类似A*的扩展）；
  ② 自底向上：对新生成或更新的叶节点计算 h(n)，然后回溯更新所有祖先节点的 cost[n]：
  • OR节点：cost[n] = min{ cost[c] for c in children }
  • AND节点：cost[n] = sum{ cost[c] for c in children }
    ③ 标记传播：当某节点所有子节点被标记为“已解”，且其 cost[n] 收敛，则标记该节点为解图一部分。
    → AO* 是增量式、图重用、代价重估驱动的，而非简单路径扩展。

🔹 4. 解的性质与终止条件

• A* 终止于首次访问目标节点（若 h 可采纳），返回单条最优路径。
• AO* 终止于初始节点被标记为“已解”且其 cost[start] 不再变化，返回的是整个最小代价解图（可能包含多支并行子解）。

✅ 总结一句话本质区别：

A 求“一条最优路径”，AO 求“一个最优解图”；前者是路径搜索，后者是结构化问题求解——它不是在找“怎么走”，而是在构造“怎么做（含分工与协同）”。**