| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
import DataStructures
#----------------------------------------------------------------------
class Node:
"""
This class is used to represent nodes of the search tree. Each
node contains a state representation, a reference to the node's
parent node, a string that describes the action that generated
the node's state from the parent state, and the path cost g from
the start node to this node.
"""
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action
self.g = 0
def expand(self):
successors = []
for (newState, action) in self.state.applyOperators():
newNode = Node(newState, self, action)
successors.append(newNode)
return successors
#----------------------------------------------------------------------
def UninformedSearch(initialState, goalState, fringe):
start = Node(initialState, None, None)
fringe.insert(start)
closedStates = []
while not fringe.isEmpty():
current = fringe.remove()
# states must have an __eq__ method defined to test equality
if current.state == goalState:
print 'Found a solution...'
showSolution(current)
return current
elif current.state not in closedStates:
closedStates.append(current.state)
for successor in current.expand():
# set path cost of successor
successor.g = current.g + 1
fringe.insert(successor)
print 'Search failed'
def showSolution(node):
numSteps = node.g
path = []
while node != None:
path.insert(0, node)
node = node.parent
print path[0].state
for n in path[1:]:
print '%s\n%s' % (n.action, n.state)
print 'Solution took %d steps' % numSteps
#----------------------------------------------------------------------
# Test functions for uninformed search
def BreadthFirst(initialState, goalState):
fringe = DataStructures.Queue()
return UninformedSearch(initialState, goalState, fringe)
def DepthFirst(initialState, goalState):
fringe = DataStructures.Stack()
return UninformedSearch(initialState, goalState, fringe)
def UniformCost(initialState, goalState):
fringe = DataStructures.PriorityQueue(lambda node: node.g)
return UninformedSearch(initialState, goalState, fringe)
SolveIt = BreadthFirst # change this for PuzzleDisplayer.py to a different search function |
