我正在尝试编写一个程序来模拟跳蛙问题,即从左边跳三只青蛙必须跳到右边的三只石头,反之亦然。每只青蛙都可以在相邻的石头上向前跳跃,或者如果后面有一块空石头,则可以跳过另一只青蛙。青蛙不能向后跳。然后通过广度优先搜索算法运行它,但是每次运行它时,我都会得到AttributeError:'NoneType'对象没有属性'path',而且我不知道为什么要得到它。我已经在下面复制了我的代码,其中包含我正在测试的所有内容,包括用于运行BFS的帮助程序,非常感谢您的帮助。
LeapFrog:
from search import Problem, breadth_first_search #______________________________________________________________________________ class LeapFrog(Problem): #state is a tuple(LG,RG,LR,RR,MR) with initial value (0,3,0,3,1) #last value flips between 1(R) and 0(L) LG=3; RG=0; LR=0; RR=3; MR=0 #class "constants" def __init__(self, initState,goalState): Problem.__init__(self, initState, goalState) def actions(self, state): #actions are simply the result states possible in this example list=[] if state[LeapFrog.MR]==0: #Middle Rock has Frog #Move one Red to the middle newState = (state[LeapFrog.LG], state[LeapFrog.RG], state[LeapFrog.LR], state[LeapFrog.RR]-1,1) if(self.validate(newState)): list.append(newState) #Move one Green to the Middle newState = (state[LeapFrog.LG]-1, state[LeapFrog.RG], state[LeapFrog.LR], state[LeapFrog.RR], 1) if(self.validate(newState)): list.append(newState) else: #Move one Green to the Right and one Red to the LeftGreenFrogs newState = (state[LeapFrog.LG]-1, state[LeapFrog.RG]+1, state[LeapFrog.LR]+1, state[LeapFrog.RR]-1, 0) if(self.validate(newState)): list.append(newState) #Move one Green to the Right newState = (state[LeapFrog.LG]-1, state[LeapFrog.RG]+1, state[LeapFrog.LR], state[LeapFrog.RR], 0) if(self.validate(newState)): list.append(newState) #Move one Red to the Left newState = (state[LeapFrog.LG], state[LeapFrog.RG], state[LeapFrog.LR]+1, state[LeapFrog.RR]-1, 0) if(self.validate(newState)): list.append(newState) return list def validate(self, state): #verify no number is greater than the max if state[LeapFrog.LG] > 3 or state[LeapFrog.RG] > 3 or state[LeapFrog.LR] > 3 or state[LeapFrog.RR] > 3: return False #verify no number is negative if state[LeapFrog.LG] < 0 or state[LeapFrog.RG] < 0 or state[LeapFrog.LR] < 0 or state[LeapFrog.RR] < 0: return False #Verify each side doesn't go over 3 at any point if state[LeapFrog.LG] + state[LeapFrog.LR] > 3 or state[LeapFrog.RG] + state[LeapFrog.RR] > 3: return False return True def result(self, state, action): return action #since states are so lightweight, the action is itself the new state def main(): print('LeapFrog Problem: ') print(' Tuples are in this format --> [<Node (LeftGreenFrogs, RightGreenFrogs, LeftRedFrogs, RightRedFrogs, MiddleRock)>]') initState = (3,0,0,3,0) goalState = (0,3,3,0,0) problem = LeapFrog(initState, goalState) goal = breadth_first_search(problem) print("\nPath = ",goal.path()) print() main()
助手:
"""
Code is based on simplified AIMA book code repository, updated for python 3.
The way to use this code is to subclass Problem to create a class of problems,
then create problem instances and solve them with calls to the various search
functions."""
from utils import FIFOQueue, Stack, Dict, update
import sys
#______________________________________________________________________________
class Problem(object):
"""The abstract class for a formal problem. You should subclass
this and implement the methods actions and result, and possibly
__init__, goal_test, and path_cost. Then you will create instances
of your subclass and solve them with the various search functions."""
def __init__(self, initial, goal=None):
"""The constructor specifies the initial state, and possibly a goal
state, if there is a unique goal. Your subclass's constructor can add
other arguments."""
self.initial = initial
self.goal = goal
def actions(self, state):
"""Return the actions that can be executed in the given
state. The result would typically be a list, but if there are
many actions, consider yielding them one at a time in an
iterator, rather than building them all at once."""
abstract #There is no keyword abstract in python. This is just a trick that AIMA uses
def result(self, state, action):
"""Return the state that results from executing the given
action in the given state. The action must be one of
self.actions(state)."""
abstract
def goal_test(self, state):
"""Return True if the state is a goal. The default method compares the
state to self.goal, as specified in the constructor. Override this
method if checking against a single self.goal is not enough."""
return state == self.goal
def path_cost(self, c, state1, action, state2):
"""Return the cost of a solution path that arrives at state2 from
state1 via action, assuming cost c to get up to state1. If the problem
is such that the path doesn't matter, this function will only look at
state2. If the path does matter, it will consider c and maybe state1
and action. The default method costs 1 for every step in the path."""
return c + 1
#______________________________________________________________________________
class Node:
"""A node in a search tree. Contains a pointer to the parent (the node
that this is a successor of) and to the actual state for this node. Note
that if a state is arrived at by two paths, then there are two nodes with
the same state. Also includes the action that got us to this state, and
the total path_cost (also known as g) to reach the node. You will not need to
subclass this class."""
def __init__(self, state, parent=None, action=None, path_cost=0):
"Create a search tree Node, derived from a parent by an action."
update(self, state=state, parent=parent, action=action,
path_cost=path_cost, depth=0)
if parent:
self.depth = parent.depth + 1
def __repr__(self):
return "<Node %s>" % (self.state,)
def expand(self, problem):
"List the nodes reachable in one step from this node."
return [self.child_node(problem, action)
for action in problem.actions(self.state)]
def child_node(self, problem, action):
next = problem.result(self.state, action)
return Node(next, self, action,
problem.path_cost(self.path_cost, self.state, action, next))
def solution(self):
"Return the sequence of actions to go from the root to this node."
return [node.action for node in self.path()[1:]]
def path(self):
"Return a list of nodes forming the path from the root to this node."
node, path_back = self, []
while node:
path_back.append(node)
node = node.parent
return list(reversed(path_back))
# We want a queue/list of nodes to have no duplicated states, so we treat nodes
# with the same state as equal. [Problem: this may not be what you
# want in many contexts.]
def __eq__(self, other):
return isinstance(other, Node) and self.state == other.state
def __hash__(self):
return hash(str(self.state))
#______________________________________________________________________________
# Uninformed Search algorithms
def graph_search(problem, frontier):
"""Search through the successors of a problem to find a goal.
The argument frontier should be an empty queue.
If two paths reach a state, only use the first one. """
frontier.append(Node(problem.initial))
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
explored.add(node.state)
frontier.extend(child for child in node.expand(problem)
if child.state not in explored)
return None
def depth_first_search(problem):
"Search the deepest nodes in the search tree first."
return graph_search(problem, Stack())
def breadth_first_search(problem):
"Search the shallowest nodes in the search tree first."
return graph_search(problem, FIFOQueue())
def depth_limited_search(problem, limit=50):
def recursive_dls(node, problem, limit):
if problem.goal_test(node.state):
print(node.state)
return node
elif node.depth == limit:
return 'cutoff'
else:
cutoff_occurred = False
for child in node.expand(problem):
print(child.state)
result = recursive_dls(child, problem, limit)
if result == 'cutoff':
cutoff_occurred = True
elif result is not None:
return result
if cutoff_occurred:
return 'cutoff'
else:
return None
# Body of depth_limited_search:
return recursive_dls(Node(problem.initial), problem, limit)
def iterative_deepening_search(problem):
for depth in range(sys.maxsize):
result = depth_limited_search(problem, depth)
if result != 'cutoff':
return result
else:
print ("Cutoff occurred for depth ",depth)
我正在尝试编写一个程序来模拟跳蛙问题,即从左边跳三只青蛙必须跳到右边的三只石头,反之亦然。每只青蛙都能向前跳...
托马斯在看]
jklabDSBAHSbdAHbdsabvjkGvdsAhAdsvcvG