无限状态空间下AI搜索算法停机问题：我的推理是否正确？

你的推理完全正确。

在经典无信息搜索算法的设计逻辑中（参考《人工智能：一种现代方法》），返回失败的唯一判定标准是前沿（frontier）为空且未找到目标节点。而当初始节点处于一个无限且与目标节点不连通的图中时，初始节点所在的连通分支是无限的——每扩展一个节点，都会产生新的未访问节点加入前沿，前沿永远不会被耗尽：

• BFS（广度优先搜索）：会逐层扩展节点，无限分支会持续为前沿补充新节点，前沿规模只会增长不会清空
• DFS（深度优先搜索）：会沿着某条无限路径持续深入，栈结构的前沿始终有后续节点可扩展
• IDS（迭代加深搜索）：每次提升深度限制后，都会在无限分支中扩展出更多新节点，每一轮迭代的前沿都不会为空，最终陷入无限迭代循环
• UCS（一致代价搜索）：只要初始连通分支存在无限多的可访问节点（无论路径代价是否递增），前沿都会不断得到新节点补充，永远无法触发失败判定

这类算法没有机制检测“目标节点是否处于当前连通分支内”，只能依赖前沿耗尽来判断无解，因此在这种无限不连通的场景下会永远运行，无法返回失败结果。

内容的提问来源于stack exchange，提问作者Zaratruta