Prolog的列表遞歸

我謂詞的目標是：Prolog的列表遞歸

?- line_terminal_stations(east_london, StartsAt, EndsAt). 
StartsAt = shoreditch 
EndsAt = new_cross

下面是我到目前爲止，遞歸工作有什麼預期，並逐步創建上線的電臺列表。

line_terminal_stations(LineName, StationX, StationY):- 
    next_station(LineName, StationX, StationY, []). 

next_station(LineName, StationX, StationY, V) :- 

    link(StationX, StationY, LineName), 
    next_station(LineName, StationY, _, [StationX | V]).

但是一旦找到最後一個站，謂詞失敗並開始'撤消'列表。而當鏈接/ 3失敗，我想結束遞歸，所以我可以提取列表的第一個和最後一個站。鏈接/ 3的

例子：

line_terminal_stations(east_london, StartsAt, EndsAt). 

Redo: (9) link(_G3031, _G3032, east_london) ? creep 
Exit: (9) link(whitechapel, shadwell, east_london) ? creep 
Call: (9) next_station(east_london, shadwell, _G3128, [whitechapel]) ? creep 
Call: (10) link(shadwell, _G3127, east_london) ? creep 
Exit: (10) link(shadwell, wapping, east_london) ? creep 
Call: (10) next_station(east_london, wapping, _G3131, [shadwell, whitechapel]) ? creep 
Call: (11) link(wapping, _G3130, east_london) ? creep 
Exit: (11) link(wapping, rotherhithe, east_london) ? creep 
Call: (11) next_station(east_london, rotherhithe, _G3134, [wapping, shadwell, whitechapel]) ? creep 
Call: (12) link(rotherhithe, _G3133, east_london) ? creep 
Exit: (12) link(rotherhithe, surrey_docks, east_london) ? creep 
Call: (12) next_station(east_london, surrey_docks, _G3137, [rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Call: (13) link(surrey_docks, _G3136, east_london) ? creep 
Exit: (13) link(surrey_docks, new_cross_gate, east_london) ? creep 
Call: (13) next_station(east_london, new_cross_gate, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Call: (14) link(new_cross_gate, _G3139, east_london) ? creep 
Fail: (14) link(new_cross_gate, _G3139, east_london) ? creep 
Fail: (13) next_station(east_london, new_cross_gate, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Redo: (13) link(surrey_docks, _G3136, east_london) ? creep 
Exit: (13) link(surrey_docks, new_cross, east_london) ? creep 
Call: (13) next_station(east_london, new_cross, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Call: (14) link(new_cross, _G3139, east_london) ? creep 
Fail: (14) link(new_cross, _G3139, east_london) ? creep 
Fail: (13) next_station(east_london, new_cross, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Fail: (12) next_station(east_london, surrey_docks, _G3137, [rotherhithe, wapping, shadwell, whitechapel]) ? creep 
Fail: (11) next_station(east_london, rotherhithe, _G3134, [wapping, shadwell, whitechapel]) ? creep 
Fail: (10) next_station(east_london, wapping, _G3131, [shadwell, whitechapel]) ? creep 
Fail: (9) next_station(east_london, shadwell, _G3128, [whitechapel]) ? creep

來源

2016-12-12 Joe

您可以添加鏈接/ 3和一些示例數據嗎？ – Limmen

一用最少的代碼修改的方法是：

link(shoreditch, whitechapel, east_london). 
link(whitechapel, shadwell, east_london). 

line_terminal_stations(LineName, First, Last):- 
    next_station(LineName, _, _, [], Stations), 
    Stations = [Last|_], 
    last(Stations, First). 

next_station(LineName, StationX, StationY, V, [StationX|V]) :- 
\+ link(StationX, StationY, LineName). 

next_station(LineName, StationX, StationY, V, Stations) :- 
    link(StationX, StationY, LineName), 
    next_station(LineName, StationY, _, [StationX | V], Stations).

試運行：

[debug] ?- line_terminal_stations(east_london, StartsAt, EndsAt). 
StartsAt = shoreditch, 
EndsAt = shadwell

但是，因爲它代表的鏈接/ 3需要按照正確的順序找到真正的啓動站。也就是說，您可以回溯並找到不同的起始站：

[debug] ?- line_terminal_stations(east_london, StartsAt, EndsAt). 
StartsAt = shoreditch, 
EndsAt = shadwell ; 
StartsAt = whitechapel, 
EndsAt = shadwell

來源

2016-12-12 18:03:03 Limmen

追蹤您提出的變更，我現在明白我錯過了什麼，感激！ – Joe

但你需要遞歸：

link(shoreditch, whitechapel, east_london). 
link(whitechapel, shadwell, east_london).

行程中的實例？

如果線不是環，可以簡單地強加StartAt是一個起點，但不是終點，而這個EndAt是一個終點，但不是起點。

我的意思是

line_terminal_stations(Line, StartsAt, EndsAt) :- 
    link(StartsAt, _, Line), 
    \+ link(_, StartsAt, Line), 
    link(_, EndsAt, Line), 
    \+ link(EndsAt, _, Line).

來源

2016-12-12 18:00:19 max66

Prolog的列表遞歸

回答

相關問題