搜索不适用于Python中的过河问题

Question

过河问题描述： 我们有一个农夫、一只狼、一只山羊和一棵卷心菜，他们需要过河，但有以下限制：

1. 狼不能和山羊一起羞耻
2. 山羊不能和白菜呆在同一边
3. -初始状态：(‘L’,‘L’,‘L’,‘L’)
4. -最终状态：(‘R’,‘R’,‘R’,‘R’)
   状态列表描述了每个人的位置（农民、狼、山羊、卷心菜），因此 state('L','R','L','R') 意味着狼和卷心菜在右侧，而农夫和山羊在河的左边。我不想通过实现列表列表来使其变得更加复杂。

Answer 1

农民问题

我将从不同的角度来解决你的问题。我没有调试您的问题，而是通过逐步进行测试的方法解决了它。

设置和规则

首先让我们定义情况和规则

FARMER = 0
WOLF = 1
GOAT = 2
CABBAGE = 3

START_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):
    # The farmer moves to the other side and can bring 0 or 1 other things so long as it is on the same starting side
    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 move

assert( 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']]