人工智能课件：第二章 与或图搜索.pdf

在人工智能领域，与或图搜索是一种重要的问题求解方法，特别是在解决复杂决策问题和路径规划问题时。本章主要探讨了与或图的基本概念、结构以及如何利用它们进行搜索。 与或图是一种特殊的图结构，它由节点和连接符构成，可以用来表示问题的结构。在与或图中，节点可以通过连接符相互连接。这里的“与”节点表示所有子节点必须满足一定条件（即所有子节点都必须解），整个节点才被视为解；而“或”节点则意味着只要其中一个子节点满足条件（至少一个子节点解），整个节点就是解。例如，在一个寻路问题中，“与”节点可能代表需要通过多个路口，而“或”节点则代表可以选择不同的路线到达目的地。 搜索的目标是从初始节点n0出发，寻找一条到达目标节点集合N={n7, n8}的路径，判断是否存在解，并找到解。在与或图中，一个节点是否可解取决于它的子节点。非终节点的解性根据其子节点的解性来确定：“与”节点要求所有子节点都可解，而“或”节点则只要有至少一个子节点可解即可。 节点的耗散值是评估搜索过程中节点状态的重要指标，它用于计算从当前节点到目标节点的潜在代价。耗散值的递推计算公式为k(n, N) = Cn + k(n1, N) + ... + k(ni, N)，其中Cn表示连接符的耗散值，ni表示子节点。通过递归定义，我们可以构建从节点n到目标集合N的解图。 在实际应用中，AO*算法是一种高效的与或图搜索策略，它结合了A*算法的启发式搜索和与或图的特性。AO*算法包括两个主要过程：一是自上而下的局部图扩展，选择最优的局部图进行扩展；二是自下而上的耗散值计算，更新节点的可解性，并删除无用的后裔节点。在示例中，AO*算法逐步扩展节点，计算耗散值，并根据启发式函数h(n)选择最有希望的路径。 总结起来，与或图搜索是人工智能中一种强大的问题解决工具，尤其适用于处理具有多种可能解决方案的问题。AO*算法则提供了一种有效的搜索策略，能够平衡探索和贪婪行为，以找到最优解。理解与或图和AO*算法的运作原理对于开发智能系统和优化决策过程至关重要。