有没有办法将递归 Prolog 代码块转换为 DFS 实现来解决传教士和食人族问题？

Question

我...也许尝试学习如何使用Prolog。目前我正在尝试解决传教士和食人者问题 - 你需要将 3 名传教士和 3 名食人者移过河，如果食人者数量超过传教士，他们就会吃掉他们。可以用船过河，最多两人可以使用该船（至少需要 1 人在船上才能从河的一侧移动到另一侧）。

我一直遇到麻烦，所以我一直在网上寻找解决方案（也许不是最好的主意）。几乎所有这些似乎都只产生了一个问题的解决方案，但我的印象是有不止一种解决方案。我和一位朋友谈过这个问题，他建议使用 DFS 实现，但我不太明白如何以适合传教士/食人族问题中使用的状态的方式使用它。我正在寻找的解决方案在 Prolog 中有这个递归解决方案：

path([A,B,C],[D,E,F],Traversed,Moves) :-
   move([A,B,C],[I,J,K],Out),
   legal([I,J,K]),  % Don't use this move unless it's safe.
   not(member([I,J,K],Traversed)),
   path([I,J,K],[D,E,F],[[I,J,K]|Traversed],[ [[I,J,K],[A,B,C],Out] | Moves ]).

合法的是是否可以在传教士不被吃掉的情况下进行移动：

legal([B,A,_]) :-
   (A =< B ; B = 0),
   C is 3-A, D is 3-B,
   (C =< D; D = 0).

移动涉及规定传教士和食人者如何移动的每条规则。

如何创建一种解决方案，使用 DFS 通过递归生成所有正确答案，而递归仅生成一个解决方案？

我已经运行了解决方案代码，但它并不能完全帮助我很好地理解事情，而且我对 Prolog 的经验不足使我很难将递归解决方案转换为 DFS 解决方案。

Answer 1

Prolog 的部分“魔力”在于深度优先搜索机制是执行模型的固有部分。相应的搜索树由执行（可能是递归）代码期间遇到的非确定性语言结构（例如替代子句或分号）隐式定义。

因此，只要您的代码的

move

谓词定义了几个替代动作，您就已经有了一个 DFS 实现！当您运行代码时，您会得到第一个解决方案，对应于搜索树中最左边的成功路径。根据要求，可以通过backtracking找到更多解决方案。在 Prolog 系统的顶层，通常通过键入

;

（分号）来请求。

考虑这个简化的程序

moves([]).
moves([X|Xs]) :- move(X), moves(Xs).

move(a).
move(b).

这里我们有两个不确定性来源：

moves/2

中空列表子句和非空列表子句之间的选择，以及

move/1

中a和b之间的选择。根据情况，系统将使用这些来探索不同的搜索树：

?- moves(Xs).
Xs = []
Yes (0.00s cpu, solution 1, maybe more) ;
Xs = [a]
Yes (0.00s cpu, solution 2, maybe more) ;
Xs = [a, a]
Yes (0.00s cpu, solution 3, maybe more)
...

?- Xs = [_,_], moves(Xs).
Xs = [a, a]
Yes (0.00s cpu, solution 1, maybe more) ;
Xs = [a, b]
Yes (0.00s cpu, solution 2, maybe more) ;
Xs = [b, a]
Yes (0.00s cpu, solution 3, maybe more) ;
Xs = [b, b]
Yes (0.00s cpu, solution 4)