在Prolog中尋找路徑

我想教自己序言。下面，我寫了一些代碼，我認爲它應該返回無向圖中節點之間的所有路徑......但事實並非如此。我試圖理解爲什麼這個特定的代碼不起作用（我認爲這個問題與類似的Prolog尋路帖不同）。我在SWI-Prolog中運行它。任何線索？在Prolog中尋找路徑

% Define a directed graph (nodes may or may not be "room"s; edges are encoded by "leads_to" predicates). 
room(kitchen). 
room(living_room). 
room(den). 
room(stairs). 
room(hall). 
room(bathroom). 
room(bedroom1). 
room(bedroom2). 
room(bedroom3). 
room(studio). 
leads_to(kitchen, living_room). 
leads_to(living_room, stairs). 
leads_to(living_room, den). 
leads_to(stairs, hall). 
leads_to(hall, bedroom1). 
leads_to(hall, bedroom2). 
leads_to(hall, bedroom3). 
leads_to(hall, studio). 
leads_to(living_room, outside). % Note "outside" is the only node that is not a "room" 
leads_to(kitchen, outside). 

% Define the indirection of the graph. This is what we'll work with. 
neighbor(A,B) :- leads_to(A, B). 
neighbor(A,B) :- leads_to(B, A).

IFF A - >乙 - 「ç - > d是一個無環的路徑，然後

path(A, D, [B, C])

應該是真實的。即，第三個參數包含中間節點。

% Base Rule (R0) 
path(X,Y,[]) :- neighbor(X,Y). 

% Inductive Rule (R1) 
path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), not(member(Z, P)), path(Z,Y,P).

然而，

?- path(bedroom1, stairs, P).

是假的。爲什麼？難道我們不應該獲得比賽R1與

X = bedroom1 
Y = stairs 
Z = hall 
P = []

以來，

?- neighbor(bedroom1, hall). 
true. 

?- not(member(hall, [])). 
true. 

?- path(hall, stairs, []). 
true .

？

事實上，如果我評價

?- path(A, B, P).

我只得到了長度爲1的解決方案。

來源

2013-03-18 user1889797

歡迎來到序言！問題實質上是，當你在R1中得到not(member(Z, P))時，P仍然是一個純變量，因爲評估還沒有得到path(Z, Y, P)來定義它。一個關於Prolog的令人驚訝又令人振奮的事情之一就是member(Ground, Var)會生成包含Ground與Var統一他們的列表：

?- member(a, X). 
X = [a|_G890] ; 
X = [_G889, a|_G893] ; 
X = [_G889, _G892, a|_G896] .

這有混亂的副作用，即在非實例列表檢查值將始終成功這就是爲什麼not(member(Z, P))將始終失敗，導致R1始終失敗。事實上，你得到所有的R0解決方案，而不是R1解決方案是一個線索，在R1的東西導致它總是失敗。畢竟，我們知道R0的作品。

如果交換這兩個目標，你會得到你想要的第一個結果：

path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), path(Z,Y,P), not(member(Z, P)). 

?- path(bedroom1, stairs, P). 
P = [hall]

如果你問其他的解決方案，你會得到一個堆棧溢出。這是因爲改變之後我們很樂意用path(Z,Y,P)儘可能快地生成周期解，只能在not(member(Z, P))後丟棄它們。（順便說一下，一個微弱的效率增益，我們可以切換到memberchk/2而不是member/2。當然，做錯事快沒有太大的幫助。:)

我傾向於將其轉換爲一個廣度優先搜索，這在Prolog中意味着增加一個「開放集合」參數來包含你還沒有嘗試過的解決方案，並且在每個節點首先嚐試一些開放集合中的東西，然後將該節點的可能性添加到開放集合的末尾。當開放集合消失時，你已經嘗試了每個可以獲得的節點。對於某些路徑查找問題，它是比深度優先搜索更好的解決方案。您可以嘗試的另一件事是將路徑分隔爲訪問組件和將來組件，並僅檢查訪問組件。只要你沒有在當前步驟中產生一個循環，你可以放心，你根本沒有產生一個循環，沒有必要擔心未來的步驟。

你提到這個問題的方式讓我相信你不想要一個完整的解決方案，只是一個提示，所以我認爲這是你所需要的。讓我知道如果這是不正確的。

來源

2013-03-18 03:38:59

在Prolog中尋找路徑

回答

相關問題