开发者

General DFS on River Crossers

开发者 https://www.devze.com 2023-01-19 12:39 出处:网络
I\'m trying to write a DFS to solve multiple river crossing problems (Fox Goat Cabbage, Jealous Husbands, Mercenaries and Cannibals, etc.). I\'ve written the puzzle classes, but I\'m having trouble st

I'm trying to write a DFS to solve multiple river crossing problems (Fox Goat Cabbage, Jealous Husbands, Mercenaries and Cannibals, etc.). I've written the puzzle classes, but I'm having trouble structuring my solver. I understand how DFS works, but I can't figure out where to start to adapt it to this design.

Each puzzle has a move() method 开发者_开发技巧which returns true if it's a valid move, or false if it breaks the ruleset. The passengers are tracked in a pair of lists which represent each respective side of the river. The solver has access to these lists, but I'm not sure how to use this to generate a possible move set, as the possible moves will change each time a passenger is taken across the river.


Create a validMoves method in your state (or node) objects that returns an array of, a Collection of, or, better yet, an Iterator over moves (or over valid states). Call this from the search algorithm (in the "node expansion" phase).

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号