如何使用列表記錄從A到B的路徑？

Question

如果我有一個節點1,2地圖，...，N，我想知道如果我可以從n1去n2，我可以使用下面的代碼：

path(1,2). 
path(3,5). 
..... 

get_to(A,B) :- path(A,B). 
get_to(A,B) :- path(A,C),get_to(C,B). 

但如何能記錄從A到B的路徑並顯示它？

Answer 1

那麼你可以使用一個蓄電池：

get_to(A,B,L) :- 
    get_to(A,B,[A],L). 

get_to(A,B,L,L2) :- 
    path(A,B), 
    append(L,[B],L2). 
get_to(A,B,L,L3) :- 
    path(A,C), 
    append(L,[C],L2), 
    get_to(C,B,L2,L3). 

凡L是陣列中存儲的路徑中的節點。

萬一圖形看起來像：

path(1,2). 
path(1,3). 
path(3,4). 
path(4,6). 
path(6,5). 
path(5,7). 

這將導致：

?- get_to(1,7,L). 
L = [1, 3, 4, 6, 5, 7] 

用這種方法的問題然而是，append操作花費線性時間導致顯著開銷。但是，您可以嘗試構建反向路徑...

get_to(A,B,L) :- 
    get_to(A,B,[B],L). 

get_to(A,B,L,[A|L]) :- 
    path(A,B). 
get_to(A,B,L,L2) :- 
    path(C,B), 
    get_to(A,C,[C|L],L2). 

產生的 - 顯然 - 在相同的路徑，但速度更快...

?- get_to(1,7,L). 
L = [1, 3, 4, 6, 5, 7] . 

Answer 2

首先，讓我們得到正確的術語：節點之間的直接連接（通常稱爲vertices）被稱爲邊緣。整個過程被稱爲一條路。這裏是第一次嘗試：

path(A,B,[A,B]) :- edge(A,B). 
path(A,C,[A,B|Vs]) :- edge(A,B), path(B,C,[B|Vs]). 

請注意，列表現在可以用來確定一個固定長度的所有路徑。

?-length(P, 10), path(A,B, P). 

甚至所有的路徑，按長度排序：

?- length(P, N), path(A,B, P). 

價格這個一般性的是，這最後一個查詢不會終止。有辦法解決這個問題，但他們不是直截了當的。