状态空间搜索

状态空间搜索是对从初始状态通过可用动作可达的状态集合进行系统探索，以找到满足目标测试的状态或达到该状态的路径。

Definition

状态空间搜索将问题视为一个图，其节点是状态，边是动作，并根据固定策略从前沿扩展状态，直到找到目标状态或空间耗尽。

Scope

本主题涵盖了将问题表述为状态空间（状态、动作、转换模型、目标测试、路径成本）以及在没有领域特定指导的情况下探索状态空间的无信息搜索策略：广度优先搜索、统一成本搜索、深度优先搜索、深度受限搜索和迭代加深搜索。它包括对这些策略的完备性、最优性、时间复杂度和空间复杂度的分析，以及带有重复状态检测的树搜索和图搜索之间的区别。启发式指导在单独的启发式搜索和A*主题中进行处理。

Core questions

• 问题如何表示为状态、动作、转换模型和目标测试？
• 广度优先、深度优先、统一成本和迭代加深搜索在前沿排序上有何不同？
• 每种无信息策略的完备性、最优性、时间复杂度和空间复杂度保证是什么？
• 图搜索如何避免树搜索中允许的对状态的浪费性重复探索？

Key concepts

• 初始状态和目标测试
• 转换模型和后继
• 前沿（开放列表）和已探索集合
• 广度优先搜索
• 深度优先搜索
• 统一成本搜索
• 迭代加深
• 树搜索与图搜索

Key theories

前沿排序决定策略

无信息搜索算法的区别仅在于它们从前沿移除状态的顺序：FIFO队列产生广度优先搜索，LIFO栈产生深度优先搜索，而基于路径成本的优先队列产生统一成本搜索。

迭代加深作为空间高效的最优解

深度优先迭代加深搜索重复运行深度受限的深度优先搜索，并逐渐增加限制，将深度优先搜索的线性空间与广度优先搜索的完备性和最优性（在单位成本下）结合起来。

Clinical relevance

无信息状态空间搜索是寻路、解谜、模型检查中的可达性分析以及启发式和对抗性搜索的基础概念和实现基础；理解其复杂性有助于指导何时盲目搜索可行，何时需要启发式方法。

History

系统状态空间搜索源于20世纪50年代的图遍历算法，包括摩尔和迪杰斯特拉的最短路径工作，并在早期人工智能中被构建为问题解决模型。Korf在1985年对迭代加深搜索的分析确立了其在线性空间下可接受树搜索中的最优性。

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

广度优先搜索何时最优？

当每一步的成本相同时，广度优先搜索是最优的，因为它首先找到最浅的目标。当步长成本不同时，统一成本搜索（按累积路径成本对前沿进行排序）是保证最低成本解决方案的无信息策略。

为什么使用迭代加深而不是普通的广度优先搜索？

广度优先搜索存储整个前沿，可能需要指数级的内存。迭代加深重复进行深度优先搜索，并逐渐增加深度限制，只使用线性内存，同时在单位成本问题上保持完备性和最优性，代价是重新扩展较浅的节点。