Prolog积木世界实现遇DFS状态振荡循环问题求助

可能的问题原因 #

• 重复状态检查逻辑失效：若状态用无序事实的列表表示，Prolog中列表是有序的，直接用列表相等判断会将[on(a,b), on(b,table)]和[on(b,table), on(a,b)]判定为不同状态，导致重复状态未被过滤。
• 已访问集合维护错误：DFS递归时若未传递已访问集合的副本，而是直接修改原集合，回溯时会篡改上层的已访问记录，导致同一状态被多次访问。
• 动作生成未过滤可逆操作：积木世界中存在互为逆操作的动作（如把A从B移到桌子，再把A从桌子移回B），若未过滤这类动作，DFS会在两个状态间反复跳转。

可行解决办法 #

• 标准化状态表示：将状态转换为有序的标准形式，消除因事实顺序导致的状态误判。示例代码：

  standardize_state(State, Standardized) :-
      sort(State, Standardized). % 按元素排序生成唯一标准状态
  

  检查重复状态前，先对当前状态和已访问集合中的状态做标准化处理。
• 正确传递已访问集合：递归时将当前状态添加到已访问集合的副本中，传递给下一层，避免回溯时篡改原集合。示例：

  dfs(State, [State|Path], Visited) :-
      goal(State),
      Path = [].
  dfs(State, [State|Path], Visited) :-
      standardize_state(State, StdState),
      \+ member(StdState, Visited),
      move(State, NextState),
      dfs(NextState, Path, [StdState|Visited]). % 传递新的已访问集合副本
  

• 过滤可逆动作：在动作生成时记录上一步动作，排除逆操作。示例：

  move(State, NextState, LastAction) :-
      action(State, Action, NextState),
      \+ is_inverse(Action, LastAction).
  
  is_inverse(move(X, Y, Z), move(X, Z, Y)). % 定义逆动作判定规则
  

  DFS调用时传递上一步动作，避免生成回到前一状态的动作。
• 验证目标可达性：手动模拟初始状态到目标状态的动作序列，确认两者确实连通，排除因目标不可达导致的无限搜索。

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