Prolog全路径搜索异常：添加访问标记后仅返回单一路径

我是Prolog新手，正在开发一个程序：给定奖杯坐标（如trofeo(1,1)事实定义）和障碍物坐标（ostacolo事实定义），需找到从固定起点(0,0)到奖杯的最短路径，要求避开障碍物且不重复访问节点。

目前遇到的问题：

• 仅使用向右、向上移动规则，且不添加访问标记断言( \+(visitato(X1,Y1))-> assert(visitato(X1, Y1)))时，程序能返回所有路径（示例中返回两条路径）；
• 添加所有四个方向移动规则及该访问标记断言后，程序仅返回一条包含重复节点(0,0)的路径，无法生成全部可行路径。

原代码如下：

% to calculate the max
max([X],X):-!.
max([X|T],X):- max(T,N),X>=N,!.
max([X|T],N):- max(T,N).

:- dynamic visitato/2.

ostacolo(2,0).
trofeo(1,1).

% with this I am finding the maximum X and Y value between obstacles and trophy, to set a limit in the "grid".

max_coordinate(MaxX, MaxY) :- 
    findall(X, ostacolo(X, _), XOstacoli),
    findall(Y, ostacolo(_, Y), YOstacoli),
    findall(X, trofeo(X, _), XTesoro),
    findall(Y, trofeo(_, Y), YTesoro),
    append(XTesoro, XOstacoli, ListaX),
    append(YTesoro, YOstacoli, ListaY),
    max(ListaX,MaxX),
    max(ListaY,MaxY).

%every X,Y respects the limit if they are lower or equal to the maximum X and Y calculated before

limite(X, Y) :- 
  max_coordinate(MaxX, MaxY),
  X =< MaxX,
  Y =< MaxY.

% base case for recursion
path((X,Y), (X,Y), [(X,Y)], _ ).
% Limit is a constant to not exceed the Stack limit, adiacente is the rule written below
path((X,Y), Trofeo, [(X,Y)|Path], Limit) :- 
  Limit > 0,
  adiacente((X,Y), (X1,Y1)),
  NewLimit is Limit - 1,
  path((X1,Y1), Trofeo, Path,NewLimit).
  
% I recall in the console?- trofeo(X,Y), find_all_paths((0,0),(X,Y), Paths), to search for the paths

find_all_paths(Start, Trofeo, Paths) :- 
   setof(Path, path(Start, Trofeo, Path, 20), Paths).

% basically with this we are saying that there are four possible actions: move up, right, left, down. The coordinates evaluated must be positive(rule positivo), respect the limit(rule limite), must be not an obstacle(rule \+obstacle), and if they are not yet visited(rule \+(visitato(X1,Y1)), then we will insert a fact, that will state that the current X1,Y1 coordinate was visited.

adjacent((X, Y), (X1, Y1)) :- 
  (X1 is X, Y1 is Y - 1),
   positivo(X1,Y1),
   limite(X1,Y1),
   \+ostacolo(X1,Y1),
   (   \+(visitato(X1,Y1))-> assert(visitato(X1, Y1))).
adjacent((X, Y), (X1, Y1)) :- 
    (X1 is X-1, Y1 is Y),
    positivo(X1,Y1),
    limite(X1,Y1),
   \+ostacolo(X1,Y1),
   (   \+(visitato(X1,Y1))-> assert(visitato(X1, Y1))).
adjacent((X, Y), (X1, Y1)) :- 
    (X1 is X + 1, Y1 is Y),
     positivo(X1,Y1),
     limite(X1,Y1),
     \+ostacolo(X1,Y1),
   (  \+(visitato(X1,Y1))-> assert(visitato(X1, Y1))).
adjacent((X, Y), (X1, Y1)) :- 
   (X1 is X, Y1 is Y + 1),
    positivo(X1,Y1),
    limite(X1,Y1),
   \+ostacolo(X1,Y1),
    (  \+(visitato(X1,Y1))-> assert(visitato(X1, Y1))).

% establish that all the coordinates must be positive
positivo(X,Y) :- 
    X >= 0, Y >= 0.

问题核心原因 #

你用动态断言assert(visitato/2)记录访问节点的方式会全局修改知识库：第一次搜索路径时标记的节点会永久保留，后续搜索其他路径时，这些已标记节点会被判定为已访问，导致无法生成新路径。同时，路径定义未自带访问历史，完全依赖全局动态事实，才会出现起点(0,0)被重复加入的情况。

解决方案 #

放弃全局动态断言，改用递归参数传递已访问节点列表的方式——这是Prolog处理无重复路径问题的标准做法，每次路径搜索都是独立的，不会污染全局状态。

修改后的完整代码 #

% 计算列表最大值
max([X], X) :- !.
max([X|T], X) :- max(T, N), X >= N, !.
max([X|T], N) :- max(T, N).

ostacolo(2, 0).
trofeo(1, 1).

% 计算障碍物和奖杯的最大坐标，限制网格范围
max_coordinate(MaxX, MaxY) :- 
    findall(X, ostacolo(X, _), XOstacoli),
    findall(Y, ostacolo(_, Y), YOstacoli),
    findall(X, trofeo(X, _), XTesoro),
    findall(Y, trofeo(_, Y), YTesoro),
    append(XTesoro, XOstacoli, ListaX),
    append(YTesoro, YOstacoli, ListaY),
    max(ListaX, MaxX),
    max(ListaY, MaxY).

% 判断坐标是否在网格范围内
limite(X, Y) :- 
    max_coordinate(MaxX, MaxY),
    X =< MaxX,
    Y =< MaxY.

% 坐标非负
positivo(X, Y) :- 
    X >= 0, Y >= 0.

% 四个方向的移动规则，无需全局断言，后续在path中检查是否已访问
adiacente((X, Y), (X1, Y1)) :- 
    X1 is X, Y1 is Y - 1,
    positivo(X1, Y1),
    limite(X1, Y1),
    \+ostacolo(X1, Y1).
adiacente((X, Y), (X1, Y1)) :- 
    X1 is X - 1, Y1 is Y,
    positivo(X1, Y1),
    limite(X1, Y1),
    \+ostacolo(X1, Y1).
adiacente((X, Y), (X1, Y1)) :- 
    X1 is X + 1, Y1 is Y,
    positivo(X1, Y1),
    limite(X1, Y1),
    \+ostacolo(X1, Y1).
adiacente((X, Y), (X1, Y1)) :- 
    X1 is X, Y1 is Y + 1,
    positivo(X1, Y1),
    limite(X1, Y1),
    \+ostacolo(X1, Y1).

% 路径递归基础：起点等于终点，路径仅包含该点
path((X, Y), (X, Y), [(X, Y)], _).
% 路径递归：当前点到终点的路径，需确保下一个点未被访问过
path((X, Y), Trofeo, [(X, Y)|Path], Limit) :- 
    Limit > 0,
    adiacente((X, Y), (X1, Y1)),
    \+member((X1, Y1), [(X, Y)|Path]), % 检查下一个点未在当前路径中
    NewLimit is Limit - 1,
    path((X1, Y1), Trofeo, Path, NewLimit).

% 查找所有可行路径
find_all_paths(Start, Trofeo, Paths) :- 
    setof(Path, path(Start, Trofeo, Path, 20), Paths).

% 查找最短路径：先找所有路径，再筛选长度最小的
find_shortest_path(Start, Trofeo, ShortestPath) :-
    find_all_paths(Start, Trofeo, Paths),
    maplist(length, Paths, Lengths),
    min_list(Lengths, MinLen),
    member(ShortestPath, Paths),
    length(ShortestPath, MinLen).

关键修改点 #

1. 移除全局动态断言：删掉:- dynamic visitato/2及所有assert(visitato(X1,Y1))相关代码，避免全局状态污染。
2. 传递路径历史：通过[(X,Y)|Path]记录当前已走路径，用\+member((X1,Y1), [(X,Y)|Path])检查下一个节点是否已访问，确保路径无重复。
3. 新增最短路径规则：find_shortest_path/3可直接返回最短路径，满足核心需求。

使用方式 #

在Prolog控制台执行：

% 返回所有可行路径
?- trofeo(X,Y), find_all_paths((0,0),(X,Y), Paths).
% 返回最短路径
?- trofeo(X,Y), find_shortest_path((0,0),(X,Y), Shortest).

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