java - 过河者的一般 DFS

Question

我正在尝试编写一个 DFS 来解决多个过河问题（Fox Goat Cabbage、Jealous Husbands、Mercenaries and Cannibals 等）。我已经编写了拼图类，但是在构建求解器时遇到了麻烦。我了解 DFS 的工作原理，但我不知道从哪里开始使其适应这种设计。

每个谜题都有一个 move() 方法，如果它是有效的移动，则返回 true，如果它违反规则集，则返回 false。乘客在代表河流每一侧的一对列表中被跟踪。求解器可以访问这些列表，但我不确定如何使用它来生成可能的移动集，因为每次乘客过河时可能的移动都会改变。

Answer 1

validMoves在您的状态（或节点）对象中创建一个方法，该方法返回一个数组，一个数组Collection，或者更好的是，一个Iterator过度移动（或有效状态）。从搜索算法中调用它（在“节点扩展”阶段）。