传教士和食人族 - LISP

Question

传教士和食人族 - LISP

3

著名的传教士和食人族问题如下所示：三个传教士和三个食人族在河的东岸，他们有一艘足以容纳最多两个人的小船。对于任何一岸，如果传教士在场，则不能被食人族超过人数，因为食人族会吃掉传教士。小船不能空载过河。如何使所有传教士和食人族都活着到达对岸？

我选择将状态表示为包含五个元素的列表。第一个元素表示东岸传教士的数量；第二个表示东岸食人族的数量；第三个表示西岸传教士的数量；第四个表示西岸食人族的数量；第五个表示小船的位置，可以是东或西。按照这种表示方法，初始状态将表示为（3 3 0 0 east）。

我的操作符是否正确？或者说，是否有使用我的状态表示定义问题操作符的其他方式？

非常感谢您的任何见解！

我的问题操作符如下：

    (defparameter *operators*
     '(boat-takes-missionary-east
     boat-takes-cannibal-east
     boat-takes-missionary-west
     boat-takes-cannibal-west
     boat-takes-missionary-missionary-east
     boat-takes-missionary-cannibal-east
     boat-takes-cannibal-cannibal-east
     boat-takes-missionary-missionary-west
     boat-takes-missionary-cannibal-west
     boat-takes-cannibal-cannibal-West)
    )

- Soaring Eagle

3个回答

1

我首先要提取的是状态：没有人需要关心它们的表示。状态的实现只需要三个信息位，因为你只需要知道一侧的数字和船在哪一侧。

编写一个函数来创建状态，接受两侧的参数，并进行适当的检查。使用关键字参数很有用，因为这样您就可以使用提供的选项来确定是否可以从其他参数默认值或者是否需要对其进行检查。

编写一个函数来检查状态的合法性：传教士在该状态下是否会被吃掉？您可以将此与前一个函数结合起来，最终得到一个名为maybe-make-state的函数，它将返回一个状态，或者如果传教士会被吃掉，则返回nil。

编写一个谓词，告诉您状态是否是所需的结果。

使用上述函数编写一个函数，给定一个状态，返回所有合法子状态的列表。

现在，使用这些函数，您可以编写一个搜索算法来从起始状态开始搜索。该算法将需要广度优先搜索（为什么？）。

- user5920214

1

您选择的运算符需要进行分解，因此我宁愿直接使用该表示法。此外，您不需要告诉船是向东还是向西行驶，因为它已经编码在状态中了。您的运算符唯一需要知道的是运输多少传教士和多少食人族。

这意味着您可以用两个数字表示状态转换：

start state: (3 3 0 0 east)
transiton: (1 1)
end state: (2 2 1 1 west)

- Svante

我没有意识到船的位置是编码的。感谢您的洞察力！ - Soaring Eagle

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- coredump · Accepted Answer

不详细讲解，解决这个问题的一种简单方法是一种称为“生成和测试”的方法，其中您从初始状态生成所有可达状态并测试解决方案（或拒绝不需要的状态）。

这里是一种通用的前向搜索函数，接受一个初始状态、一个下一个函数来计算下一个状态列表（给定状态和当前“路径”），并对每个访问过的状态应用一个函数。

(defun forward-search (initial-state next function)
  (labels ((recurse (state path)
             (funcall function state path)
             (push state path)
             (dolist (state (funcall next state path))
               (recurse state path))))
    (recurse initial-state nil)))

例如，这里有一个从0开始的搜索，其中对于每个小于5的v，可能的相邻状态要么是v+1，要么是v+2。

(forward-search 0
                (lambda (v &optional p)
                  (declare (ignore p))
                  (if (< v 5)
                      (list (+ v 1) (+ v 2))
                      nil))
                (lambda (v path)
                  (declare (ignore v))
                  (print path)))

以下是跟踪记录，路径表示导致当前状态的所有中间状态（按相反顺序）：

NIL
(0)
(1 0)
(2 1 0)
(3 2 1 0)
(4 3 2 1 0)
(4 3 2 1 0)
(3 2 1 0)
(2 1 0)
(4 2 1 0)
(4 2 1 0)
(1 0)
(3 1 0)
(4 3 1 0)
(4 3 1 0)
(3 1 0)
(0)
(2 0)
(3 2 0)
(4 3 2 0)
(4 3 2 0)
(3 2 0)
(2 0)
(4 2 0)
(4 2 0)

在您的next函数中，可以使用路径参数来拒绝已经出现在路径中的状态（提示：您不希望多次访问同一状态，这在您的情况下很可能会发生）。

您需要有一种表示状态和计算下一个状态的方法（请参见其他答案）。