Prolog：Knight的最短路徑

Question

嗨，所以在我被告知這個問題已被多次詢問之前，我已經瀏覽了一堆問題，但沒有一個涉及到Prolog。這是我遇到的困難。

我想找到棋盤上兩點之間的最短路徑。我擁有的代碼專門針對騎士。這是到目前爲止我的代碼：

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中編寫代碼以找到最短路徑的任何幫助都將非常有幫助，並且是我正在尋找的。

Answer 1

要遵循您的方法，似乎列舉所有路徑，並找到最低限度，我會去與aggregate圖書館。

但首先，我會建議您清理一下您的代碼，因爲我不確定它會以這種方式正常工作（但我剛剛檢查得非常快）。

特別是，您想要到達一個謂詞path((X1, Y1),(X2, Y2),Path)，這將允許枚舉所有路徑（如果多次重試），然後停止。一旦所有路徑都被耗盡，你似乎無限期地循環。 你可以找到一些關於如何枚舉所有非循環路徑here的啓示。

一旦是固定的，你可以通過以下方式使用aggregate/3：

:-use_module(library(aggregate)).  

find_min(Start, End, Path) :- 
    aggregate(
     min(Length, Path), 
     (path(Start, End, Path), length(Path, Length)), 
     min(_,P) 
    ). 

find_min(Start, End, Path)然後將允許您從一個細胞枚舉所有的最短路徑到另一個。 請注意，可能存在從Start到End的多條最短路徑;這將返回所有最短路徑，而不僅僅是一條。

另一種可能的解決方案是實現Djikstra的最短路徑算法，該算法可能比列舉所有路徑和找到最小值更有效，就像我們在這裏所做的那樣。但這將是一個完全不同的方法。

EDIT：用小板4×4或5×5，則枚舉所有路徑並找到分鐘方法可以工作，但對8×8板的複雜性將變得unmangeable。 在這裏，最好的方法是改變你的方法和實現，例如Djikstra的算法。