宽度优先搜索：与或树的解树构造与判定

本资源主要讨论了在人工智能领域中的一种算法分析——3-2020年的第三章-21，专注于"与或图"和"与或树"的搜索策略。与或图和与或树是逻辑操作的图形表示，用于解决逻辑问题和决策树中的搜索问题。 首先，章节中提到了"问题规约和与或图"，这是将复杂的问题简化为逻辑操作的图形结构，以便于搜索。在这个框架下，搜索的目标不再是找到一条从起始节点到目标节点的路径，而是寻找一个能够证明初始节点可解的解树。搜索过程中会通过执行"可解节点标志"和"不可解节点标志"来判断节点的状态。 "与或树"的特性是除初始节点外，其他节点都只有一个父节点，而"与或图"则允许有更多的父节点。搜索策略包括"盲目式搜索"，如宽度优先搜索（WFS）和深度优先搜索（DFS），以及博弈树搜索策略，如Max-Min搜索和α-β剪枝。 宽度优先搜索是重点内容，它遵循"先产生的节点先扩展"的原则，利用OPEN表（存储待扩展节点）和CLOSED表（存储已扩展节点）来组织搜索过程。在搜索过程中，每次扩展节点时，会检查其是否可解，如果遇到终叶节点（如题目中的t1、t2、t3、t4），则进一步判断节点的可解性。如果所有后继节点都不可解，且存在不可解的端节点（如A和B），搜索将停止，表明初始节点不可解。 举例说明，对于给定的与或树，宽度优先搜索的流程图展示了关键步骤，如扩展节点、标记可解或不可解标志，并根据节点的终叶性质决定是否终止搜索。这个例子强调了在实际问题中如何运用这些概念来求解逻辑问题。 本资源深入探讨了与或图和与或树在人工智能搜索中的应用，涉及理论概念、搜索策略和具体操作流程，为理解逻辑问题求解提供了清晰的指导。