迷宫求解器DFS算法

Question

我在一门课上学习序言。我有一个练习，我需要读取一个文件，从中生成一个迷宫，获得从源到目标的路径，然后将其写入一个文件。

我读了文件，对我拥有的每个单元格断言square（CoordX，CoordY），对连接的每两个单元格断言connect（X，Y）。

TargetX，TargetY，SourceX，SourceY都是整数坐标，所以我知道起点和终点。

我的工作原理是，如果当前节点连接到目标，完成并返回。否则，找到当前节点所连接的节点，并用新节点调用递归

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？你可以简单地使用T，因为如果这个目标成功，这两个词是相同的。

这种模式在程序中出现两次。

另一个问题：永远不要放 在一行的末尾，它看起来太像，。

因此，在这些更改之后，您的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）-

为了避免这个问题，您可以记住访问过的方块，并避免再次使用它们。

我已经写了下面的例子，但是请考虑一下

（1） 我已经切换了开始和目标（先开始，后目标）

（2） 我在生成的路径中添加了start和target

（3）我使用gprolog，所以我没有not/1；我使用了\成员......代替

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

---编辑---

正如Mat在评论中所建议的（谢谢！），您可以编写（如果您的prolog环境支持maplist/2），而不是\member（square（Nx，Ny），Visited）（或not（member（square（Nx，Ny，Visited））

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

要强制执行square（Nx，Ny）不在已访问的列表中。

这个解决方案更一般，因为（如果我理解正确的话）统一是双向的。