在SWI Prolog中用assertz()和retract()实现BFS的问题求助

我尝试用SWI-Prolog的assertz/1和retract/1实现广度优先搜索（BFS），但遇到了执行终止的问题。当前代码的问题是：当breadthfirst/1的目标检查分支执行时，会直接撤回数据库中的初始状态队列，导致后续调用扩展分支时没有可撤回的内容，程序提前终止。

原代码 #

:- dynamic paths/1.

bfs_solve(Solution) :-
  initial_state(Start),
  assertz(paths([[Start]])),
  breadthfirst(Solution).

breadthfirst([Node | Path]) :-
  retract(paths([[Node | Path] | _])),
  goal(Node).

breadthfirst(Solution) :-
  retract(paths([Path | RestPaths])),
  extend(Path, NewPaths),
  conc(RestPaths, NewPaths, Paths1),
  assertz(paths(Paths1)),
  breadthfirst(Solution).

extend([Node | Path], NewPaths) :-
  bagof([NewNode, Node | Path],
  (s(Node, NewNode), \+ member(NewNode, [Node | Path])),
  NewPaths),
  !.

extend(Path, []).

initial_state([1, 2, 3, 4, 5]).
goal([0, 0, 0, 0, 0]).

% 状态转移谓词s/2此处省略，不影响当前问题分析

member(X, [X | Tail]).
member(X, [Head | Tail]) :-
  member(X, Tail).

conc([], L, L).
conc([X | L1], L2, [X | L3]) :-
  conc(L1, L2, L3).

错误原因 #

核心问题在于第一个breadthfirst/1子句的逻辑顺序错误：

• 该子句先执行retract(paths([[Node | Path] | _]))，直接从数据库中删除了整个队列事实，无论当前路径是否满足目标。
• 如果初始状态不满足goal(Node)，子句会失败，但此时队列已经被删除，后续第二个breadthfirst/1子句执行retract(paths([Path | RestPaths]))时，数据库中已经没有paths/1事实，导致程序直接终止。

修复后的代码 #

调整breadthfirst/1的逻辑，先完整取出队列，再检查第一个路径是否为目标，避免提前删除队列：

:- dynamic paths/1.

bfs_solve(Solution) :-
    initial_state(Start),
    assertz(paths([[Start]])),
    breadthfirst(Solution).

% 先取出整个队列，检查第一个路径是否为目标
breadthfirst(Solution) :-
    retract(paths([[Node|Path]|RestPaths])), % 取出队列的第一个路径和剩余队列
    (   goal(Node)
    ->  Solution = [Node|Path] % 找到目标，返回解
    ;   extend([Node|Path], NewPaths), % 扩展当前路径
        conc(RestPaths, NewPaths, NewQueue), % 新队列=剩余队列+新路径
        assertz(paths(NewQueue)), % 保存新队列
        breadthfirst(Solution) % 递归处理新队列
    ).

extend([Node | Path], NewPaths) :-
    bagof([NewNode, Node | Path],
          (s(Node, NewNode), \+ member(NewNode, [Node | Path])),
          NewPaths),
    !.

extend(Path, []).

initial_state([1, 2, 3, 4, 5]).
goal([0, 0, 0, 0, 0]).

member(X, [X | Tail]).
member(X, [Head | Tail]) :-
    member(X, Tail).

conc([], L, L).
conc([X | L1], L2, [X | L3]) :-
    conc(L1, L2, L3).

关键修改说明 #

• 将两个breadthfirst/1子句合并为一个，通过条件分支处理目标检查和路径扩展逻辑，保证队列操作的原子性。
• 先完整取出队列的第一个路径和剩余队列，再判断是否为目标：如果是则直接返回解，否则扩展路径后构建新队列存入数据库，继续递归BFS。
• 彻底避免了队列被提前删除的问题，确保BFS迭代过程的连续性。

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