如何爲這個「移動塊」Prolog練習實現一個求解謂詞？

Question

我使用的伊萬·布拉科書研究序言：人工智能編程，我發現了一些困難，實施工作的最後部分提出

演習是使用圖形來決定如何移動塊和程序按順序排列它們。

這是有關程序必須做的圖像：

正如你在前面的IMMAGE見塊A，B，C可以使用多種受理舉動感動是：

• 塊可以僅當它是在該堆的頂部上移動

• 塊可以在地面上被移動（上空隙棧）

• A嵌段可以在另一個塊被移動（在另一個棧 的包含一些其它塊頂部）

因此，這些可容許移動引起可能的轉變的曲線圖一個狀態，並在圖中的另一個狀態時，事之間這樣的：

因此，正如你可以在上圖中看到的那樣，我可以使用3個子列表來反駁一個情況。

每個子列表rappresent堆疊在哪裏可以根據前述約束

因此，例如，先前的圖的中心節點的情況可表示爲把塊：

[[A], [B], [C]]

因爲每個堆棧都包含一個單獨的塊。

通過在左上角，其中我一個堆疊中的其它塊C，A下方的節點所表示的情況，B可以表示爲：

[[C,A,B], [], []]

好了，我的程序是以下一個：

del(X, [X|Tail], Tail). 

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1). 

/* s(CurrentState, SuccessorState): Predicate that calculate a legal move from 
            the CurrentState to the SuccessorState: 
*/ 
s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :- 
            del([Top1|Stack1], Stacks, Stacks1), 
            del(Stack2, Stacks1, OtherStacks). 

goal(Situation) :- member([a,b,c], Situation). 

在這些最後的日子裏，我深入地研究了它，並且我理解它是如何工作的。

基本上與S/3謂詞是我後繼函數s(CurrentState, SuccessorState)計算從CurrentState到SuccessorState一個合法的移動。

該斷言效果很好，其實如果我啓動以下查詢：

[debug] ?- s([[a,b,c],[],[]],R). 
R = [[b, c], [a], []] 

我獲得[B，C]，[A]，[]是後繼狀態對於狀態[[a，b，c]，[]，[]]，這很好，因爲我已經從第二個堆棧頂部的第一個堆棧頂部移除了a塊（這是無效的）這是完全合法的舉動。

好了，怎麼回事我有goal/1謂詞說，當我已經達到了一個最終狀態（當計算必須停止）：

goal(Situation) :- member([a,b,c], Situation). 

上面說的情況（具體的堆棧列表配置）是一個目標情況，如果在相關堆棧列表中有一個堆棧是[a，b，c]列表。

所以下面的情況是目標的情況：

[[a,b,c],[],[]] 
[[], [a,b,c],[]] 
[[],[], [a,b,c]] 

好了我現在的問題是下面的一個：我要實現的solve/2謂詞是這樣的：

solve([[c,a,b],[],[]], Situation) 

，從開始通過的情況（在這種情況下，第一個堆棧中的所有塊的地址爲c，中間爲b，中間爲a在頂部），並達到目標的情況。

我不知道到底是什麼我必須做的，我怎麼也得解決這個問題（可惜我沒有老師）

我是想激勵自己看這個版本的八皇后問題是使用類似的編程技術（其中我有一個目標，以滿足和解決謂語）：

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]), 
          noattack(Queen, Queens, 1). 

goal([_,_,_,_,_,_,_,_]). 

noattack(_,[],_) :- !. 
noattack(Y,[Y1|Ylist],Xdist) :- Y =\= Y1, 
            Y1-Y =\= Xdist, 
            Y-Y1 =\= Xdist, 
            Dist1 is Xdist + 1, 
            noattack(Y,Ylist,Dist1). 

solve(N,[N]) :- goal(N).  % sample call: solve([], X). 

solve(N, [N|Sol1]) :- s(N,N1), 
         solve(N1,Sol1). 

Answer 1

將有在空間搜索圖的循環，那麼你可以切換到某種形式的約束搜索。我知道它越容易越深入搜索：

?- length(Situation,_), solve([[c,a,b],[],[]], Situation). 
Situation = [[[c, a, b], [], []], [[a, b], [c], []], [[b], [a], [c]], [[], [b, c], [a]], [[], [a, b|...], []]] . 

長度/ 2列舉出長度不變的未綁定列表。所以我們得到一個結果。

請注意，如果沒有從初始狀態到目標/ 1的解決方案，這仍將循環。 如果這是不好的，我認爲解決/ 2將需要服務solve2/2謂詞，這將得到的路徑，以啓用非確定性s/2調用後通常\+ memberchk(NewState, Visited)。然後它會（未經測試）

solve(N, SearchPath) :- solve2([N], SearchPath). 

solve2([N|Visited], [N|Visited]) :- goal(N). 
solve2([N|Visited], Path) :- 
    s(N,N1), 
    \+ memberchk(N1, Visited), 
    solve2([N1,N|Visited], Path).