Prolog查詢無限搜索

Question

我是Prolog的初學者，我想問一個關於Prolog的問題。

我的程序基於非確定性有限狀態自動機。

開始狀態是S0並且最終狀態是S3。

該圖是

所以如果有一個字符串[a,a,b,b,c,c]應該像

start(s0). 
edge(a, s0, s0). 
edge(a, s0, s1). 
edge(b, s1, s1). 
edge(b, s1, s2). 
edge(c, s2, s2). 
edge(c, s2, s3). 
final(s3). 

有一個謂詞accepts(Ls)如果（有Ls是字符串的列表）

accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B). 

並假設NFA從狀態硅轉到狀態Sj的和在它們之間有一個狀態Sk的，goesTo謂詞被定義爲

goesTo(Ls, Si, Sj) :- edge (L, Si, Sk), goesTo(Ls, Sk, Sj). 

但是，如果查詢accepts(Ls)（的任意列表字符串範圍從a到c） 教程問題說它幾乎肯定會進入無限搜索併發生堆棧溢出。

但是，我不明白爲什麼查詢將進入無限的搜索並導致堆棧溢出。如果你能給我理由，那將非常棒！

（編輯:)確切的報價是：

「的典型Prolog的用戶可能會希望他/她的goesTo規則是這樣的針鋒相對的查詢接受（X）將產生連續的弦這是上面的NFA所接受的，幾乎可以肯定的是，鑑於給定NFA的上述表示，Prolog系統將進入無限搜索併發生堆棧溢出，請說出爲什麼是這樣（如果您要避免此問題，請說你如何設法避免它）。「

Answer 1

這是你的NFA的定義：

start(s0). 
edge(a, s0, s0). 
edge(a, s0, s1). 
edge(b, s1, s1). 
edge(b, s1, s2). 
edge(c, s2, s2). 
edge(c, s2, s3). 
final(s3). 

它有可能會通過它測試接受任何輸入字符串沒有聯繫。注意每行末尾的點 - 這些是定義NFA的Prolog謂詞。

運行你accepts/1與任何具體輸入的字符串會導致有限的遞歸。這裏的搜索空間是有限的，並且它肯定會被耗盡 - 只要你用完全實例化的有限長度的字符串調用accepts/1即可。現在

，如果你嘗試產生所有可能路徑接受的字符串，那麼你就會有一個無限循環，因爲有可以接受的字符串的無限數量：

a,b,c 
a,a,b,c 
a,a,a,b,c 
a,a,a,a,b,c 
..... 

都這個自動機可以接受的字符串。

你的謂詞定義都錯過了最後一個點。而且goesTo不太對。它必須改爲：

goesTo([], S, S). 
goesTo([L1|Ls], S1, Sn) :- edge(L1, S1, S2), goesTo(Ls, S2, Sn). 
accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B). 

另請注意，謂詞名稱和左括號之間不能有空格。

---

所以現在OP已經澄清了他們的問題。它是

爲什麼要生成所有可能接受的字符串企圖幾乎肯定會進入一個非生產性循環？

呼叫accepts(X)確實進入無限遞歸，因爲產生一個新的節點來嘗試的是從一開始就重新啓動，所以內部的a秒的無限增長的字符串是煉

a 
a,a 
a,a,a 
a,a,a,a 
.... 

僅僅是因爲edge(a,s0,s0)是數據庫中第一個edge事實，並且edge/3的調用位於goesTo/3謂詞定義內的第一個位置。而Prolog的搜索策略是從左到右的。

我們可以通過重新排列，像這樣的目標，從完全非生產性的行爲（其中Prolog的只是掛在一個無限循環）的生產行爲得到：

start(s0). 
edge(a, s0, s1). 
edge(b, s1, s2). 
edge(c, s2, s3). 
edge(a, s0, s0). 
edge(b, s1, s1). 
edge(c, s2, s2). 
final(s3). 

現在，

12 ?- accepts(X). 

X = [a, b, c] ; 
X = [a, b, c, c] ; 
X = [a, b, c, c, c] ; 
X = [a, b, c, c, c, c] ; 
X = [a, b, c, c, c, c, c] ; 
X = [a, b, c, c, c, c, c, c] ; 
X = [a, b, c, c, c, c, c, c, c] 

不幸的是作爲可以看出這一代人傾向於c。如何使它「公平」...讓我們把它留給另一個問題，我們呢？

Answer 2

由於Prolog採用的搜索策略，程序將循環。它試圖通過策略來解決查詢探索解決方案空間的問題，即空間效率高但不完整。

現在應該清楚，解決方案空間是無限在你的情況下，因爲這些循環在圖中。從初始狀態到最終狀態有無限的路徑。

Iterative deepening應該是枚舉路徑的更簡單方法，它很容易在Prolog中實現。另一種可能性是執行搜索。

Answer 3

因爲它是其他人所說的循環。

P.S分配一直延續到週四，所以沒有必要恐慌[但] ，是的，我知道你在做