解決一個特定的循環

Question

near(a1,b1). near(b1,c1). near(c1,d1). near(d1,e1). near(e1,f1). 
near(f1,g1). near(a1,a2). near(a2,a3). near(a3,a4). near(a4,a5). 
near(a5,a6). near(a6,a7). near(a7,a8). near(a8,a9). near(b1,b2). 
near(b2,b3). near(b3,b4). near(b4,b5). near(b5,b6). near(b6,b7). 
near(b7,b8). near(b8,b9). near(c4,d4). near(d1,e4). near(e4,f4). 
near(f4,g4). near(g4,h4). near(g1,g2). near(g2,g3). near(g3,g4). 
near(f4,f5). near(f5,f6). near(f6,f7). near(f7,f8). near(f8,f9). 
near(a6,b6). near(b6,c6). near(a9,b9). near(b9,c9). near(c9,d9). 
near(d9,f9). near(f9,g9). near(g9,h9). near(h9,i9). 

path(X,X). 
path(X,Y):- 
    near(X,Z), path(Z,Y), 
    write(X), 
    write('->'), 
    write(Z). 

maze(X,Y):-findall(X,path(X,Y),Path_List),write(Path_List). 

這是尋找迷宮。

我想打印出這樣的

Route1 [18] a1 -> b1 -> c1 -> d1 -> e1 -> f1 -> g1 -> g2 -> g3 -> g4 -> h4 -> h5 -> h6 -> h7 -> h8 -> h9 -> i9 

，並顯示其他4路。

我想用cut？或回溯。但是我不能碰這個代碼。

Answer 1

一般來說，寫出回溯算法實際解決問題所需的中間步驟是非常有用的技術。路徑/ 2秒條款產生的大部分輸出是'噪聲'。

這也是導致跟蹤/ 0作爲Prolog主調試工具的動機。跟蹤附加信息，如嵌套級別，即必不可少的以使輸出有意義。

那麼我會建議擺脫路徑/ 2寫入（S），加一個參數「叼回」的道路，譜寫服務謂詞打印：

path(X,X, [X]). 
path(X,Y, [X|Cs]):- 
    near(X,Z), path(Z,Y, Cs). 

maze(X,Y):- forall(path(X,Y,Ps),writeln(Ps)). 

?- maze(a1,i9). 
[a1,b1,c1,d1,e4,f4,f5,f6,f7,f8,f9,g9,h9,i9] 
[a1,b1,b2,b3,b4,b5,b6,b7,b8,b9,c9,d9,f9,g9,h9,i9] 
[a1,a2,a3,a4,a5,a6,a7,a8,a9,b9,c9,d9,f9,g9,h9,i9] 
[a1,a2,a3,a4,a5,a6,b6,b7,b8,b9,c9,d9,f9,g9,h9,i9] 
true. 

不是非常有吸引力的，但肯定更有用。

注意，路徑/ 3（以及路徑/ 2）將循環在循環的存在永遠 ...

編輯使用pqGraphviz，此代碼段

maze_g(X,Y) :- 
    graph_window(maze_g(X,Y),[]). 

maze_g(X,Y,G) :- 
    forall(path(X,Y,Ns), 
     (maplist(make_node(G),Ns,Ps) 
     ,nodes_chain(Ps,Cs) 
     ,make_edges(G,Cs))). 

隨後?- maze_g(a1,i9).，收益率