过河问题的描述：我们有一位农民、一只狼、一只羊和一颗白菜，他们需要在以下限制条件下过河：
- 狼不能和羊在同一侧
- 羊不能和白菜在同一侧
- -初始状态：（‘L’,‘L’,‘L’,‘L’）
- -最终状态：（‘R’,‘R’,‘R’,‘R’）
状态列表描述了每个人的位置，（农民，狼，羊，白菜），所以状态（‘L’,‘R’,‘L’,‘R’）表示狼和白菜在河的右侧，而农民和羊在河的左侧。我不想通过实现列表的列表来使其更加复杂。
回答：
农民问题
我将从一个不同的角度来解决你的问题。不是调试你的问题，我采用了一种逐步解决的方法，并在过程中进行测试。
设置和规则
首先让我们定义情况和规则
FARMER = 0WOLF = 1GOAT = 2CABBAGE = 3START_STATE = ['L','L','L','L']def wolfRule(state): return state[FARMER] == state[WOLF] or state[WOLF] != state[GOAT]assert( wolfRule(['L','L','L','L']) == True)assert( wolfRule(['R','L','L','L']) == False)assert( wolfRule(['R','L','R','L']) == True)def goatRule(state): return state[FARMER] == state[GOAT] or state[GOAT] != state[CABBAGE]assert( goatRule(['L','L','L','L']) == True)assert( goatRule(['R','L','L','L']) == False)assert( goatRule(['R','L','L','R']) == True)def validRule(state): return wolfRule(state) and goatRule(state)def winRule(state): return state == ['R','R','R','R']assert( winRule(['L','L','L','L']) == False)assert( winRule(['R','L','L','L']) == False)assert( winRule(['R','R','R','R']) == True)我们已经定义了每条规则，并添加了一些断言语句以确保它们正常工作，当我们运行上述代码时，我们可以确定一切都准备就绪。
生成移动
递归搜索的一部分是生成下一个有效移动。我们将分两部分进行。第一部分仅生成所有可能的移动，第二部分将筛选出仅有效的移动
def generateMoves(state): # 农民移动到另一侧，可以带0或1个其他东西，只要它在同一起始侧 for other in [FARMER, WOLF, GOAT, CABBAGE]: if state[FARMER] == state[other]: move = copy(state) move[FARMER] = 'L' if state[FARMER] == 'R' else 'R' move[other] = 'L' if state[other] == 'R' else 'R' yield moveassert( list(generateMoves(START_STATE)) == [['R','L','L','L'],['R','R','L','L'],['R','L','R','L'],['R','L','L','R']] )同样，我们添加了一个测试以确保生成移动时符合我们的预期
def validMoves(state_list): return [ state for state in state_list if validRule(state)]assert( list(validMoves(generateMoves(START_STATE))) == [['R','L','R','L']] )确实，唯一有效的第一步移动是农民带羊过河！
深度优先搜索
现在我们进行深度优先搜索，使用previous_states列表来跟踪我们去过的地方。这个函数只返回一个获胜的答案。
def depthFirstSearch(state, previous_states): previous_states.append(state) if winRule(state): return previous_states for move in validMoves(generateMoves(state)): if move not in previous_states: result = depthFirstSearch(move, previous_states) if result is not None: return result previous_states.pop() return None同样，至少要有一个测试来确保它给出预期的结果
assert( depthFirstSearch(['L','R','L','R'],[]) == [['L','R','L','R'],['R','R','R','R']] )最终输出
我们运行它
depthFirstSearch(START_STATE,[])并得到解决方案！
[['L', 'L', 'L', 'L'], ['R', 'L', 'R', 'L'], ['L', 'L', 'R', 'L'], ['R', 'R', 'R', 'L'], ['L', 'R', 'L', 'L'], ['R', 'R', 'L', 'R'], ['L', 'R', 'L', 'R'], ['R', 'R', 'R', 'R']]