我实现了一个问题解决代理程序，使用Peter Norvig的"AI现代方法第三版；
然后，我用状态空间的广度优先搜索(BFS(和深度优先搜索(DFS(来解决这个难题。尽管双方都找到了解决方案，但我对DFS提出的解决方案感到困惑。BFS用12招解决了这个谜题，但DFS用100多招解决了它，这似乎是不对的。
我的部分实现跟踪从目标或最终节点返回根节点的路径。我希望两种算法都能产生相同的结果(即12次移动(，因为它们都使用相同的类方法来跟踪路线；并且我假设两种算法都将识别出与目标节点相同的节点。所以，除非我的假设是错误的，否则我的代码中要么有错误，要么有多种解决方案。
import numpy as np
initial_board = np.array([[1,2,3],
[4,0,5],
[6,7,8]])
initial_space = (1,1)
initial_state=[initial_action,(initial_board,initial_space)]
goal_board = np.array([[1,2,3],
[4,5,6],
[0,7,8]])
goal_space = (2,0)
goal_state = [goal_board,goal_space]
class Problem:
"""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."""
raise NotImplementedError
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)."""
raise NotImplementedError
def goal_test(self, state):
"""Return True if the state is a goal. The default method compares the
state to self.goal or checks for state in self.goal if it is a
list, as specified in the constructor. Override this method if
checking against a single self.goal is not enough."""
if isinstance(self.goal, list):
return is_in(state, self.goal)
else:
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
def value(self, state):
"""For optimization problems, each state has a value. Hill Climbing
and related algorithms try to maximize this value."""
raise NotImplementedError
class PuzzleProblem(Problem):
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."""
actions = []
(row,col) = state[1][1]
if row > 0 :
actions.append('U')
if row < 2:
actions.append('D')
if col > 0:
actions.append('L')
if col < 2:
actions.append('R')
return actions
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)."""
mat = state[1][0]
(row, col) = state[1][1]
if action == 'U':
mat1 = np.copy(mat)
mat1[row][col] = mat1[row-1][col]
mat1[row-1][col] = 0
return [action,(mat1,(row-1,col))]
if action == 'D':
mat1 = np.copy(mat)
mat1[row][col] = mat1[row+1][col]
mat1[row+1][col] = 0
return [action,(mat1,(row+1,col))]
if action == 'L':
mat1 = np.copy(mat)
mat1[row][col] = mat1[row][col-1]
mat1[row][col-1] = 0
return [action,(mat1,(row,col-1))]
if action == 'R':
mat1 = np.copy(mat)
mat1[row][col] = mat1[row][col+1]
mat1[row][col+1] = 0
return [action,(mat1,(row,col+1))]
def goal_test(self, state):
"""Return True if the state is a goal. The default method compares the
state to self.goal or checks for state in self.goal if it is a
list, as specified in the constructor. Override this method if
checking against a single self.goal is not enough."""
#print('State to test: ')
#print(state[1][0])
#file1.write(str(state[1][0]))
if isinstance(self.goal, list):
if (np.all(state[1][0] == self.goal[0])) and (state[1][1] == self.goal[1]):
print('GOAL REACHED')
return True
else:
return False
puzzle = PuzzleProblem(initial_state,goal_state)
from collections import deque
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. Other functions
may add an f and h value; see best_first_graph_search and astar_search for
an explanation of how the f and h values are handled. 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."""
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
self.depth = 0
if parent:
self.depth = parent.depth + 1
def __repr__(self):
return "<Node {}>".format(self.state)
def __lt__(self, node):
return self.state < node.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)]
actions = problem.actions(self.state)
action_results = []
children = []
for action in actions:
action_results.append(problem.result(self.state,action))
for action_state in action_results:
children.append(self.child_node(problem,action_state[0]))
return children
def child_node(self, problem, action):
"""[Figure 3.10]"""
next_state = problem.result(self.state, action)
next_node = Node(next_state, self, action, problem.path_cost(self.path_cost, self.state, action, next_state))
return next_node
def solution(self):
"""Return the sequence of actions to go from the root to this node."""
#file2 = open("BFSNodes.txt","a")
file4 = open("DFSNodes.txt","a")
sol = [node.state[1][0] for node in self.path()[1:]]
file4.writelines(str(sol))
file4.close()
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 for a queue of nodes in breadth_first_graph_search or
# astar_search to have no duplicated states, so we treat nodes
# with the same state as equal. [Problem: this may not be what you
# want in other contexts.]
def __eq__(self, other):
return isinstance(other, Node) and self.state == other.state
def __hash__(self):
# We use the hash value of the state
# stored in the node instead of the node
# object itself to quickly search a node
# with the same state in a Hash Table
return hash(self.state)
def not_in_explored(node,explored_list):
for n in explored_list:
if (n.state[1][0] == node.state[1][0]).all():
return False
return True
def breadth_first_tree_search(problem):
"""
[Figure 3.7]
Search the shallowest nodes in the search tree first.
Search through the successors of a problem to find a goal.
The argument frontier should be an empty queue.
Repeats infinitely in case of loops.
"""
frontier = deque([Node(problem.initial)]) # FIFO queue
explored_nodes = []
breaker = 0
file1 = open("BFSsol.txt","a")
while frontier:
breaker +=1
#print('BREAKER: ',breaker)
if breaker > 1000000:
print('breaking')
break
node = frontier.popleft()
if not_in_explored(node,explored_nodes):
explored_nodes.append(node)
if problem.goal_test(node.state):
solution = node.solution()
file1.write(str(solution))
file1.close()
return solution
frontier.extend(node.expand(problem))
return None
def depth_first_tree_search(problem):
"""
[Figure 3.7]
Search the deepest nodes in the search tree first.
Search through the successors of a problem to find a goal.
The argument frontier should be an empty queue.
Repeats infinitely in case of loops.
"""
file3 = open("DFSsol.txt","a")
explored_nodes = []
frontier = [Node(problem.initial)] # Stack
breaker = 0
while frontier:
breaker +=1
#print(breaker)
if breaker > 1000000:
print('breaking')
break
node = frontier.pop()
if not_in_explored(node,explored_nodes):
explored_nodes.append(node)
if problem.goal_test(node.state):
solution = node.solution()
file3.write(str(solution))
file3.close()
return solution
frontier.extend(node.expand(problem))
return None
breadth_first_tree_search(puzzle)
depth_first_tree_search(puzzle)
BFS得出了这个解决方案：['R'，'D'，'L'，'L'，'U'，'R'
但DFS衍生出了很多更多的举措。
我希望这两种算法都能在12次移动的解决方案中得出，因此我不理解为什么DFS会为一个解决方案产生这么多移动。
有人能指出代码中的错误吗；或者解释结果(如果正确的话(？
您所描述的是预期的：DFS不是最优的，它将找到不一定是最短的解决方案。顾名思义，它只是以深度优先的方式沿着搜索树向下运行，这意味着除非迫不得已，否则它永远不会回溯。它返回找到的第一个解决方案，在树的每个结点使用第一个猜测，如果没有，则尝试第二个、第三个等。因此，它找到的不一定是最短的。
DFS的好处是它的内存效率更高。它不需要跟踪几个未完成的候选人计划，因为它总是只考虑一个选项。
Upshot：您的代码很可能是正确的。