lisp - 传教士和食人者 - LISP

Question

著名的传教士与食人者问题如下:

三个传教士和三个食人者在一条河的东边。他们有一艘大到最多可以载两个人的船。对于两岸，如果岸上有传教士，他们的人数不能超过食人者，因为食人者会吃掉传教士。如果船上没有人，船是不能自己过河的。所有的传教士和食人者如何才能活着到达另一边？

我选择将状态表示为包含五个元素的列表。第一个元素代表东岸传教士的数量；第二个代表东岸食人族的数量；第三个代表西岸传教士的人数；第四个代表西岸食人族的数量；第五个代表船的位置，可以是东也可以是西。在这种表示下，初始状态将表示为 (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)
    )

Answer 1

无需详细说明，解决此问题的一种简单方法是一种称为生成和测试的方法，您可以在其中从初始状态生成所有可达状态并测试解决方案(或拒绝不良状态)。

这是一种通用的前向搜索函数，接受一个初始状态，一个计算下一个状态列表的下一个函数(给定一个状态和一个当前“路径”)，并将一个函数应用于每个访问的状态。

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

trace如下，路径表示通向当前状态的所有中间状态(倒序):

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 函数中使用路径参数来拒绝路径中已经出现的状态(提示:您不希望多次访问一个状态，因为在您的例)。

您需要有一种方法来表示一个状态并计算下一个状态(参见其他答案)。