基于Prolog实现无内置谓词的地铁站直接连通站点计数

现有如下Prolog事实定义了地铁站点的连通关系：

%first line
connected(new_elmarg,elmarg).
connected(elmarg,ezbet_elnakhl).
connected(ezbet_elnakhl,ain_shams).
connected(ain_shams,elmatareyya).
connected(elmatareyya,helmeyet_elzaitoun).
connected(helmeyet_elzaitoun,hadayeq_elzaitoun).
connected(hadayeq_elzaitoun,saray_elqobba).
connected(saray_elqobba,hammamat_elqobba).
connected(hammamat_elqobba,kobri_elqobba).
connected(kobri_elqobba,manshiet_elsadr).
connected(manshiet_elsadr,eldemerdash).
connected(eldemerdash,ghamra).
connected(ghamra,alshohadaa).
connected(alshohadaa,urabi).
connected(urabi,nasser).
connected(nasser,sadat).
connected(sadat,saad_zaghloul).
connected(saad_zaghloul, alsayyeda_zeinab).
connected(alsayyeda_zeinab,elmalek_elsaleh).
connected(elmalek_elsaleh,margirgis).
connected(margirgis,elzahraa).
connected(elzahraa,dar_elsalam).
connected(dar_elsalam,hadayeq_elmaadi).
connected(hadayeq_elmaadi,maadi).
connected(maadi,thakanat_elmaadi).
connected(thakanat_elmaadi,tora_elbalad).
connected(tora_elbalad,kozzika).
connected(kozzika,tora_elasmant).
connected(tora_elasmant,elmaasara).
connected(elmaasara,hadayeq_helwan).
connected(hadayeq_helwan,wadi_hof).
connected(wadi_hof,helwan_university).
connected(helwan_university,ain_helwan).
connected(ain_helwan,helwan).
%second line
connected(shobra_elkheima,koliet_elzeraa).
connected(koliet_elzeraa,mezallat).
connected(mezallat,khalafawy).
connected(khalafawy,sainte_teresa).
connected(sainte_teresa,road_elfarag).
connected(road_elfarag,massara).
connected(massara,alshohadaa).
connected(alshohadaa,ataba).
connected(ataba,naguib).
connected(naguib,sadat).
connected(sadat,opera).
connected(opera,dokki).
connected(dokki,bohooth).
connected(bohooth,cairo_university).
connected(cairo_university,faisal).
connected(faisal,giza).
connected(giza,omm_elmisryeen).
connected(omm_elmisryeen,sakiat_mekki).
connected(sakiat_mekki,elmounib).

• 统计给定站点的直接相连站点总数
• 禁止使用findall等内置聚合谓词

测试示例 #

输入: are_connected(sadat,X).
输出: X = 4.
输入: are_connected(helwan,X).
输出: X = 1.

你编写的代码存在两个核心逻辑错误：

1. 没有计数遍历逻辑，两个基础子句每次匹配到连通关系就返回0，后续递归只会在0的基础上无限累加，没有实际统计匹配项的数量
2. 没有去重逻辑和计数终止边界，要么无限递归要么返回错误的计数结果

我们可以通过带已访问标记的累加递归实现计数，不需要使用内置聚合谓词：

% 对外调用的主谓词
are_connected(A, Count) :-
    count_connected(A, [], 0, Count).

% 辅助计数谓词：参数依次为目标站点、已统计邻接站点列表、当前累加值、最终计数结果
count_connected(A, Visited, Acc, FinalCount) :-
    % 匹配双向连通的邻接站点，且未被统计过
    (connected(A, Neighbor) ; connected(Neighbor, A)),
    \+ member(Neighbor, Visited),
    NewAcc is Acc + 1,
    count_connected(A, [Neighbor|Visited], NewAcc, FinalCount),
    !. % 剪枝避免回溯返回错误的更小计数值

% 无更多未统计邻接站点时，返回当前累加值为最终结果
count_connected(_, _, Acc, Acc).

• 调用are_connected(sadat, X)时，会匹配到4个邻接站点：nasser、saad_zaghloul、naguib、opera，返回X = 4符合测试要求
• 调用are_connected(helwan, X)时，仅匹配到1个邻接站点ain_helwan，返回X = 1符合测试要求

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