c - 有力量的食人者和传教士

Question

我需要一些帮助来完成教授给我们的数学任务。任何建议都会有所帮助。问题是：

有 N 个食人者和 M 个传教士。所有传教士都有一个力量属性，可以是 1 或任何正整数。力量表明他可以击退多少食人族。

基本上：河的两边，有一个2槽的船，你必须把所有的家伙转移到另一边，不能让食人族吃掉传教士。

您将如何为此编写程序？什么是转移分组算法？

感谢期待，

标记。

Answer 1

将您的问题建模为状态图。

在这里，一个状态是 ({L,R} ⁿ ,{L,R} ^m ,{L,R}) 其中：

• 第一个n条目：每个传教士一个 - 他在哪里：河的左/右岸
• 接下来，m条目：每个食人动物一个 - 他在哪里：河的左/右岸
• 最后一个条目是船

这些是您的顶点-您还应该修剪无效状态-传教士的力量在一个（或多个）方面不够。很容易为每个状态计算它。

你的优势是：

E = { (S1,S2) | Can move in one boat ride from S1 to S2 }

剩下要做的就是使用一些最短路径算法来找到从:(L,L,....,L)到的最短路径(R,R,...,R)。

您可以使用BFS来完成此任务，甚至可以使用双向搜索- 或使用知情算法（具有可接受的启发式），例如A* Algorithm。

PS。“图”只是概念性的，实际上您将拥有一个函数next:S->2^S，它给定一个状态 - 返回该状态的所有有效后继（状态，您可以使用图上的一条边从 获取它们S）。这将允许您即时“生成图表”。

您的next(S)函数应该类似于（高级伪代码，没有优化）：

next(S):
   let x be the bank where the boat is, and y the other bank
   for each person p1 on bank x:
      S' = S where boat and p1 moved from x to y
      if S' is valid according to strength limitations, yield S'
      for each p2 != p1 on bank x:
         S' = S where boat and p1 and p2 moved from x to y
         if S' is valid according to strength limitations, yield S'