嗨,所以在我被告知這個問題已被多次詢問之前,我已經瀏覽了一堆問題,但沒有一個涉及到Prolog。這是我遇到的困難。Prolog:Knight的最短路徑
我想找到棋盤上兩點之間的最短路徑。我擁有的代碼專門針對騎士。這是到目前爲止我的代碼:
move1((X1,Y1), (X2,Y2)) :- up1(X1, X2), up2(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- up2(X1, X2), up1(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- up1(X1, X2), down2(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- up2(X1, X2), down1(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- down1(X1, X2), up2(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- down2(X1, X2), up1(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- down1(X1, X2), down2(Y1, Y2).
move1((X1,Y1), (X2,Y2)) :- down2(X1, X2), down1(Y1, Y2).
up1(U, V) :- successor(U, V).
up2(U, W) :- successor(U, V), successor(V, W).
down1(U, V) :- up1(V, U).
down2(U, V) :- up2(V, U).
successor(1, 2).
successor(2, 3).
successor(3, 4).
successor(4, 5).
edge((X1,Y1) , (X2,Y2)) :- move1((X1,Y1), (X2,Y2)).
path((X1,Y1), (X2,Y2),N,[(X1,Y1), (X2,Y2)]) :- N > 0, edge((X1,Y1), (X2,Y2)).
path((X1,Y1), (X3,Y3),N,[(X1,Y1)|P1]) :- N > 0, N1 is N-1, path((X2,Y2), (X3,Y3),N1,P1), edge((X1,Y1), (X2,Y2)), nonmember((X1,Y1),P1).
shortest((X1,Y1),(X2,Y2),P) :- path((X1,Y1),(X2,Y2),24,P),!.
visit((X1,Y1),P,N) :- path((X1,Y1), (X2,Y2),N,P),N2 is N+1,len(P,N2).
len([],0).
len([_|T],N) :- len(T,X), N is X+1.
nonmember(X,[]).
nonmember(X,[U|Y]) :- X \= U, nonmember(X,Y).
正如你所看到的,我只找到的第一個路徑,而不是最短路徑。我不確定如何在prolog中編寫代碼並找出一條獲得所有最短路徑的方法。我正在考慮列出所有可能的路徑,然後找到最短路徑,但我似乎無法編寫代碼。
findAll((X1,Y1),(X2,Y2),P,L) :- path((X1,Y1),(X2,Y2),24,P),length(P,L).
給我所有路徑的長度,但我不知道如何處理它。 如何在Prolog中編寫代碼以找到最短路徑的任何幫助都將非常有幫助,並且是我正在尋找的。
你可以用'\ + memberchk'而不是'nonmember'謂詞來嘗試嗎? –
是啊對不起,我刪除了我的意見,因爲我有點想通了,如果我最後打電話給nonmember,那麼它現在有效,因爲P1現在有值。另外,我試圖使用上面給出的代碼,而我似乎無法實現它的工作。使用最短路徑調用:最短((1,1),(4,4),P)。它只是保持循環。 – helpCompSci
用我的代碼我注意到,當我沒有切割時調用最短路徑時,它從最短路徑開始並繼續列出更長和更長的路徑。說我的代碼先找到最短路徑然後繼續找到更長的路徑是否安全? – helpCompSci