Пролог: Самый короткий путь для рыцаря

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). 

Как вы можете видеть, я только найти первый путь, а не самый короткий путь. Я не уверен, как закодировать в прологе и выяснить способ получить все кратчайшие пути. Я думал о том, чтобы составить список всех возможных путей, которые пройдут, и найти кратчайший, но я не могу написать код.

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; это вернет все кратчайшие пути, а не только один.

Другим возможным решением было бы реализовать алгоритм кратчайшего пути Джикстры, который, вероятно, будет намного более эффективным, чем перечисление всех путей и поиск минимума, как мы это делаем. Но это был бы совершенно другой подход.

EDIT: с небольшой доской 4x4 или 5x5, то перечисление всех путей и поиск минимального подхода могут работать, но на плате 8x8 сложность станет непостоянной. Здесь наилучшим способом было бы изменить ваш подход и реализовать, например, алгоритм Джикстры.