嵌套迷宫问题的可判定性与求解算法探究

受某无限嵌套迷宫实例启发，我们提出如下基于图论的嵌套迷宫问题：

基础设定 #

• 无向图 G 由顶点集 V 和无向边集 E 构成
• 额外定义有向边集 F
• 指定起始顶点 S 和目标顶点 Z

状态转移规则 #

我们需要找到一条从状态 (S, 0) 到状态 (Z, 0) 的路径，路径中的状态转移仅能通过 E 和 F 中的边实现，具体规则如下：

1. 无向边集 E 中的边 (u, v)：允许状态转移 (u, n) -> (v, n) 或 (v, n) -> (u, n)（任意 n >= 0），对应迷宫中的常规移动
2. 有向边集 F 中的边 (u, v)：允许状态转移 (u, n) -> (v, n + 1) 或 (v, n + 1) -> (u, n)（任意 n >= 0），对应进入/退出嵌套迷宫，状态的第二个元素记录当前“深度”

注：路径为边的序列，允许重复使用边

核心疑问 #

是否存在通用算法可解决上述嵌套迷宫问题？该问题看起来可能是不可判定的，但部分具体实例的分析难度较低。

补充思考 #

能否通过合并图 G 中所有相互可达的顶点来剔除无向边集 E？若可行，问题可简化为基于顶点集 V 和有向边集 F 的路径问题：需找到一条可重复使用边（正向或反向）的路径，要求路径中正向遍历边的总次数等于反向遍历的总次数，且路径的所有前缀中正向遍历次数均不小于反向遍历次数。

内容的提问来源于Stack Exchange，提问作者Davis Yoshida