如何在Prolog中实现反向可达出发地列表查询？

已实现reach(Departure, Arrivals)谓词，用于查询从指定出发地Departure可到达的所有目的地Arrivals列表。现需实现一个谓词，查询所有能到达指定目的地的出发地列表，例如查询?- list(krum, Departure)，应返回Departure = [uzhorod]。

现有代码 #

reachable(D, D, _).
reachable(Departure, Arrival, Visited) :- 
    trip(_, Departure, Point, _),
    \+ member(Point, Visited),
    reachable(Point, Arrival, [Point|Visited]).
reachable(Departure, Arrival) :- 
    reachable(Departure, Arrival, [Departure]).

reach(Departure, Arrivals):-
    setof(
        Arrival,
        reachable(Departure, Arrival),
        Arrivals
    ),
    Arrivals \= [Departure].

事实数据 #

trip(01, kuiv, odessa, 1500).
trip(02, kuiv, lviv, 700).
trip(08, lviv, zaporizhya, 700).
trip(03, uzhorod, krum, 6000).
trip(04, vunohradiv, odessa, 2540).
trip(05, ternopil, kuiv, 3800).
trip(06, zaporizhya, donetsk, 900).
trip(07, lytsk, mariupol, 7500).

% trip(Id, 出发地, 目的地, 价格)

现有输出示例 #

?- reach(kuiv, Arrivals).
Answer: Arrivals = [donetsk, kuiv, lviv, odessa, zaporizhya]

解决方案 #

要实现反向查询，我们需要编写反向遍历的可达性谓词，从目标目的地出发，回溯所有能到达它的出发地：

% 反向可达：起点与终点相同
reverse_reachable(D, D, _).
% 反向遍历：找到能直接抵达当前点的前一站，且未被访问过
reverse_reachable(Departure, Arrival, Visited) :-
    trip(_, Point, Arrival, _),  % 调换trip的出发地和目的地参数，反向查找
    \+ member(Point, Visited),
    reverse_reachable(Departure, Point, [Point|Visited]).
% 反向可达入口谓词，初始访问列表包含目标目的地
reverse_reachable(Departure, Arrival) :-
    reverse_reachable(Departure, Arrival, [Arrival]).

% 最终查询谓词：收集所有能到达指定目的地的出发地
list(Arrival, Departures) :-
    setof(
        Departure,
        reverse_reachable(Departure, Arrival),
        Departures
    ),
    Departures \= [Arrival].  % 排除仅目标地自身的情况（若不需要可移除该判断）

测试示例 #

?- list(krum, Departure).
Answer: Departure = [uzhorod]

逻辑说明 #

• reverse_reachable谓词通过反向遍历trip数据，从目标目的地出发，递归查找所有能通过中转到达它的出发地，同时用Visited列表避免循环。
• setof用于对结果去重并排序，确保输出是有序的无重复列表。

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