搜索无法解决 python 中的过河问题

Question

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

狼不能与羊为敌
山羊不能和白菜在同一边
-初始状态：(‘L’,‘L’,‘L’,‘L’)

-结局状态：(‘R’,‘R’,‘R’,‘R’)
状态列表描述了每个人的位置（农民、狼、山羊、卷心菜），所以 state('L','R','L','R') 表示狼和卷心菜在右侧，而农夫和山羊在河的左边。我不想通过实现列表列表来让它变得更复杂。我的代码的问题是它从初始状态开始，在第一步（右边的农民和山羊）之后停止。我找不到任何方法来使递归工作以获得可接受的结果。所以我可以使用一些帮助来使递归发挥作用并按预期工作。提前谢谢你。

""" ----------------------------------------------------------------------------
******** Search Code for DFS  and other search methods
******** (expanding front and extending queue)
******** author:  
"""


import copy

#left, right of the river
spaces = {
  'R': ['L'],
  'L': ['R']
}

def enter(state):
  if state[0]==state[1] and state[2]==state[3]:
    new_state=state=['R', state[1]] + ['R', state[3]]
    return new_state

#function that swaps the side of the river that the farmer is
def swap(state_l, i, j): 
state_l[i] = state_l[j]
return state_l

'''
operators for the movement of the farmer
'''

def neighbour1(state):
  elem=['L']
  i=state.index(elem) if elem in state else -1  #checking if the elem is in the state
  if i >=0:
    swap(state, i, spaces[i][0])
    return state

def neighbour2(state):   
  elem=['L']
  i=state.index(elem) if elem in state else -1
  if i >=0:
    swap(state, i, spaces[i][1])
    return state


""" ----------------------------------------------------------------------------
**** FRONT managment
**** 
"""

def find_children(state):

  children=[]

  enter_state=copy.deepcopy(state)
  enter_child=enter(enter_state)

  tr1_state=copy.deepcopy(state)
  tr1_child=neighbour1(tr1_state)

  tr2_state=copy.deepcopy(state)
  tr2_child=neighbour2(tr2_state)

  if tr1_child is not None: 
      children.append(tr1_child)

  if tr2_child is not None: 
      children.append(tr2_child)

  if enter_child is not None: 
      children.append(enter_child)

  return children


""" ----------------------------------------------------------------------------
** initialization of front
** 
"""

def make_front(state):
  return [state]

""" ----------------------------------------------------------------------------
**** expanding front
****   
"""

def expand_front(front, method):  
  if method=='DFS':        
    if front:
        print("Front:")
        print(front)
        node=front.pop(0)
        for child in find_children(node):     
            front.insert(0,child)

  elif method=='BFS':
    if front: 
        print("Front:")
        print(front)
        node=front.pop(0)
        for child in find_children(node):     
            front.append(child)
return front
'''
elif method=='BestFS':
#'''           
#else: "other methods to be added"        


""" ----------------------------------------------------------------------------
**** QUEUE
**** 
"""

""" ----------------------------------------------------------------------------
** initialization of queue
** 
"""

def make_queue(state):
  return [[state]]

""" ----------------------------------------------------------------------------
**** expanding queue
**** επέκταση ουράς
"""

def extend_queue(queue, method):
  if method=='DFS':
    print("Queue:")
    print(queue)
    node=queue.pop(0)
    queue_copy=copy.deepcopy(queue)
    children=find_children(node[-1])
    for child in children:
        path=copy.deepcopy(node)
        path.append(child)
        queue_copy.insert(0,path)

elif method=='BFS': 
    if queue:
        print("Queue:")
        print(queue)
        node=queue.pop(0)
        queue_copy=copy.deepcopy(queue)
        children=find_children(node[-1])
        for child in children:
            path=copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)
'''
elif method=='BestFS':
#'''
#else: "other methods to be added" 

return queue_copy

""" ----------------------------------------------------------------------------
**** Basic recursive function to create search tree (recursive tree expansion)
**** 
"""

def find_solution(front, queue, closed, method):

  if not front:
    print('_NO_SOLUTION_FOUND_')

  elif front[0] in closed:
    new_front=copy.deepcopy(front)
    new_front.pop(0)
    new_queue=copy.deepcopy(queue)
    new_queue.pop(0)
    find_solution(new_front, new_queue, closed, method)

  elif is_goal_state(front[0]):
    print('_GOAL_FOUND_')
    print(queue[0])

  else:
    closed.append(front[0])
    front_copy=copy.deepcopy(front)
    front_children=expand_front(front_copy, method)
    queue_copy=copy.deepcopy(queue)
    queue_children=extend_queue(queue_copy, method)
    closed_copy=copy.deepcopy(closed)
    find_solution(front_children, queue_children, closed_copy, method)


"""" ----------------------------------------------------------------------------
** Executing the code
** 
"""

def is_goal_state(state):  
  if state == ['R','R','R','R']:
    return True 

def main():

initial_state = ['L','L','L','L']  
method='DFS'

""" ----------------------------------------------------------------------------
**** starting search
**** 
"""

print('____BEGIN__SEARCHING____')
find_solution(make_front(initial_state), make_queue(initial_state), [], method)


if __name__ == "__main__":
  main()

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 列表来跟踪我们去过的地方。此功能仅returns个中奖答案。

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

搜索无法解决 python 中的过河问题

Search not working for river crossing problem in python

recursion

artificial-intelligence

breadth-first-search

depth-first-search

python-3.x

农民问题

设置和规则

生成动作

深度优先搜索

最终输出