人工智能第一次实验报告 图搜索策略

在本次人工智能实验中，主要涉及的是图搜索策略，特别是针对九宫问题或八数码问题的求解。实验目的是深入理解图搜索策略的概念，包括启发式搜索和α-β剪枝，并通过编程演示来比较和分析不同策略的实质，强调全局择优搜索的应用。 1. **有解与无解的判定**： 实验中采用了逆序值的方法来判断初始状态和目标状态是否有解。逆序值是计算数列中每个数前面比它大的数的个数的总和。如果初始状态和目标状态的逆序值奇偶性相同，则说明有解，否则无解。具体实现是通过两个嵌套循环计算逆序值，然后比较它们的奇偶性。 2. **启发式函数的设计**： 启发式函数的设定考虑了搜索的深度（g(n)）和不在位的棋子数目（h(n)），形成估价函数f(n) = g(n) + h(n)。这里定义了一个名为`Node`的结构体，包含了棋盘状态、当前深度、不在位棋子数目和估价函数值，以及指向父节点和前后节点的指针。 3. **开放列表与关闭列表的实现**： 开放列表使用带有头结点的单链表表示，链表头部的节点具有最小的估价函数值，这符合全局择优搜索的要求。关闭列表同样用单链表表示，按照扩展步骤顺序连接。 4. **关键函数**： - **扩展结点函数**：负责根据当前节点生成所有可能的子节点，并计算它们的新状态、深度、不在位数目以及估价函数值。 - **是否在开放列表或关闭列表中的函数**：检查给定状态的节点是否已经存在于开放列表或关闭列表中，避免重复搜索。 - **判断方向函数**：用于确定移动棋子的方向，这是操作棋盘状态的关键。 5. **搜索过程**： 实验采用深度优先搜索，配合启发函数进行全局优化。当扩展节点时，会先将新节点添加到开放列表，然后根据估价函数值从小到大进行选择。如果找到目标状态，搜索结束；否则，将当前节点移入关闭列表，并继续扩展下一个最优节点。 6. **性能优化**： 使用启发式函数可以有效地指导搜索方向，减少无效的路径探索，提高搜索效率。此外，通过维护开放列表和关闭列表，可以跟踪已访问的节点，防止回环和重复计算。 通过这次实验，学生能够深入理解启发式搜索策略在解决实际问题中的应用，以及全局择优搜索在优化搜索过程中的作用。同时，自定义启发式函数的能力和对搜索空间的有效管理是提高算法效率的关键。