Maze Solver DFS Algorithm

Question

Я изучаю пролог в курсе. У меня есть упражнение, где мне нужно прочитать файл, создать из него лабиринт, получить путь от источника к месту назначения и записать его в файл.

Я прочитал файл, и я утверждаю square(CoordX, CoordY) для каждой ячейки I , и connect(X, Y) для каждой из двух связанных ячеек.

TargetX, TargetY, , SourceY - это целые координаты, поэтому я знаю точку начала и точку назначения.

Обоснование, в котором я работал, заключается в том, что если текущий узел подключен к цели, закончен и возвращен. else, найти узел, к которому подключен текущий узел, и вызвать рекурсию с новым узлом

solveFirst(TargetX, TargetY, SourceX, SourceY, T):- 
    connects(square(SourceX, SourceY), NewSquare), 
    solve(TargetX, TargetY, SourceX, SourceY, NewSquare, T2), 
    T = T2. 

solve(TargetX, TargetY, SourceX, SourceY, NewSquare ,[Tail]):- 
    getFirst(Tail, HeadOfTail), 
    (
    connects(NewSquare, square(TargetX, TargetY)), 
    addFirst(NewSquare, Tail, T2), 
    Tail = T2 ; 
    connects(NewSquare, E), 
    solve(TargetX, TargetY, SourceX, SourceY, E, Tail) 
    ). 

Answer 1

Ваше обоснование кажется действительным. Единственное, что вам осталось сделать - это правильно реализовать его.

Во-первых, общее замечание о коде:

Когда вы видите цель, как:

T = T2 

спросить себя: Почему вы приведете T2на всех? Вы можете просто использовать вместо, так как это на том же сроке, если этот мяч удался.

Эта модель возникает дважды в вашей программе.

Другой вопрос: Никогда не ставить ; на конце линии Это выглядит слишком похоже на ,.

Итак, после того, как эти изменения, ваш solve/6 выглядит следующим образом:

 
solve(TargetX, TargetY, SourceX, SourceY, NewSquare, [Tail]):- 
    getFirst(Tail, HeadOfTail), 
    ( connects(NewSquare, square(TargetX, TargetY)), 
     addFirst(NewSquare, Tail, Tail) 
    ; connects(NewSquare, E), 
     solve(TargetX, TargetY, SourceX, SourceY, E, Tail) 
    ). 

Теперь спросите себя: ли это даже имеет смысл? В частности, может addFirst(NewSquare, Tail, Tail) Успех? Это трудно сказать для нас, так как у вас есть пропущенное определение.

Кроме того, при компиляции этого, вы получите предупреждение :

 
Singleton variables: [HeadOfTail] 

Так почему же вы даже представить эту переменную?

Концептуально, следующая модель может помочь вам:

 
path(Current, Target, Path) :- 
    ( connects(Current, Target), 
     Path = [Current] 
    ; connects(Current, Next), 
     Path = [Current|Ps], 
     path(Next, Target, Ps) 
    ). 

Answer 2

Я изменил свои правила таким образом

solve(TargetX, TargetY, _, _, NewSquare, [NewSquare]) :- 
    connects(NewSquare, square(TargetX, TargetY)). 

solve(TargetX, TargetY, SourceX, SourceY, NewSquare, [E | Tail]) :- 
    connects(NewSquare, E), 
    solve(TargetX, TargetY, SourceX, SourceY, E, Tail). 

solveFirst(TargetX, TargetY, SourceX, SourceY, [NewSquare | T]):- 
    connects(square(SourceX, SourceY), NewSquare), 
    solve(TargetX, TargetY, SourceX, SourceY, NewSquare, T). 

и со следующими фактами

square(1, 1). square(1, 2). square(1, 3). 
square(2, 1). square(2, 2). square(2, 3). 
square(3, 1). square(3, 2). square(3, 3). 

connects(square(1, 1), square(1, 2)). 
connects(square(1, 1), square(2, 1)). 
connects(square(1, 2), square(1, 3)). 
connects(square(1, 2), square(2, 2)). 
connects(square(2, 1), square(2, 2)). 
connects(square(2, 2), square(3, 2)). 
connects(square(3, 2), square(3, 3)). 

вызова solveFirst(3, 3, 1, 1, L), я (L) следующие пути

[square(1,2),square(2,2),square(3,2),square(3,2)] 
[square(2,1),square(2,2),square(3,2),square(3,2)] 

Но эта работа из-за отсутствия петель. Если добавить следующее соединение

connects(square(2, 2), square(1, 2)). 

так что вы можете цикл ((1,2) -> (2,2) -> (1,2) -> (2,2) ...) и из solveFirst(3, 3, 1, 1, L) Я получаю переполнение стека.

Чтобы избежать этой проблемы, вы можете вспомнить посещенные квадраты и не использовать их снова.

Я написал следующий пример, но считаю, что

(1) Я перешел начало и цель (запуск первой, второй целевой)

(2) Я добавил начало и цель в результирующий путь

(3) Я использую gprolog, поэтому у меня нет not/1; Я использовал \+ member.... вместо

getPath(Tx, Ty, Tx, Ty, _, [square(Tx, Ty)]). 

getPath(Sx, Sy, Tx, Ty, Visited, [square(Sx, Sy) | Path]) :- 
    connects(square(Sx, Sy), square(Nx, Ny)), 
    \+ member(square(Nx, Ny), Visited), % or not(member(square(Nx, Ny), Visited) 
    getPath(Nx, Ny, Tx, Ty, [square(Nx, Ny) | Visited], Path). 

getPath(Sx, Sy, Tx, Ty, Path) :- 
    getPath(Sx, Sy, Tx, Ty, [square(Sx, Sy)], Path). 

Используя следующие факты

square(1, 1). square(1, 2). square(1, 3). 
square(2, 1). square(2, 2). square(2, 3). 
square(3, 1). square(3, 2). square(3, 3). 

connects(square(1, 1), square(1, 2)). 
connects(square(1, 1), square(2, 1)). 
connects(square(1, 2), square(1, 3)). 
connects(square(1, 2), square(2, 2)). 
connects(square(2, 2), square(1, 2)). 
connects(square(2, 1), square(2, 2)). 
connects(square(2, 2), square(3, 2)). 
connects(square(3, 2), square(3, 3)). 

из getPath(1, 1, 3, 3, L) я получаю следующие пути

[square(1,1),square(1,2),square(2,2),square(3,2),square(3,3)] 
[square(1,1),square(2,1),square(2,2),square(3,2),square(3,3)] 

--- EDIT ---

Как было предложено Mat in комментарий (спасибо!), вместо \+ member(square(Nx, Ny), Visited) (или not(member(square(Nx, Ny), Visited)) вы могли бы написать (если пролог поддержка среды maplist/2)

maplist(dif(square(Nx,Ny)), Visited) 

навязать, что square(Nx, Ny) не в Visited списке.

Это решение является более общим, потому что (если я правильно понимаю) унификация работает в обоих направлениях.