Subversion Repositories programming

Rev

Rev 392 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 392 Rev 393
Line 19... Line 19...
19 
 
 19 
 
20 
from PuzzlePiece import PuzzlePiece
 20 
from PuzzlePiece import PuzzlePiece
21 
from Graph import Graph
 21 
from Graph import Graph
22 
import yapgvb
 22 
import yapgvb
23 
 
 23 
 
- 
 
 24 
class SearchResult (object):
- 
 
 25 
	"""Class to store a search result"""
- 
 
 26 
 
- 
 
 27 
	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):
- 
 
 28 
		self.completed = completed
- 
 
 29 
		self.status = status
- 
 
 30 
		self.depth_reached = depth_reached
- 
 
 31 
		self.nodes_created = nodes_created
- 
 
 32 
		self.result_graph = result_graph
- 
 
 33 
		self.search_name = None
- 
 
 34 
 
- 
 
 35 
	def __repr__ (self):
- 
 
 36 
		"""Turn myself into a string"""
- 
 
 37 
		answer =  '%s -- Reached Depth: %s -- Nodes Created: %s' % \
- 
 
 38 
			(self.status, self.depth_reached, self.nodes_created)
- 
 
 39 
 
- 
 
 40 
		if self.search_name:
- 
 
 41 
			answer = self.search_name + '\n' + answer
- 
 
 42 
 
- 
 
 43 
		return answer
- 
 
 44 
 
- 
 
 45 
	def set_search_name (self, name):
- 
 
 46 
		self.search_name = name
- 
 
 47 
 
- 
 
 48 
 
24 
class PuzzleSearch (object):
 49 
class PuzzleSearch (object):
25 
	"""Implements a graph search"""
 50 
	"""Implements a graph search"""
26 
 
 51 
 
27 
	def __init__ (self, start_node, goal_nodes):
 52 
	def __init__ (self, start_node, goal_nodes):
28 
		"""Constructor.
 53 
		"""Constructor.
Line 74... Line 99...
74 
 
 99 
 
75 
				result.add_edge (v1, v2)
 100 
				result.add_edge (v1, v2)
76 
				result.set_edge_color (v1, v2, yapgvb.colors.red)
 101 
				result.set_edge_color (v1, v2, yapgvb.colors.red)
77 
				result.set_edge_label (v1, v2, str(counter))
 102 
				result.set_edge_label (v1, v2, str(counter))
78 
 
 103 
 
79 
				result.set_vertex_value (str(N), result.get_vertex_value(v2)+1)
 - 
 
80 
 
 - 
 
81 
			else:
 104 
			else:
82 
				# Set start node shape to be a double circle
 105 
				# Set start node shape to be a double circle
83 
				result.set_vertex_shape (str(N), yapgvb.shapes.doublecircle)
 106 
				result.set_vertex_shape (str(N), yapgvb.shapes.doublecircle)
84 
				result.set_vertex_value (str(N), 0) # set depth
 - 
 
85 
				firsttime = False
 107 
				firsttime = False
86 
			###############################################################
 108 
			###############################################################
87 
 
 109 
 
88 
			# Check if we've reached the goal
 110 
			# Check if we've reached the goal
89 
			if N in self.__goal_nodes:
 111 
			if N in self.__goal_nodes:
90 
				print '%s nodes created' % (len(OPEN) + len(CLOSED))
 - 
 
91 
				print 'searched to depth: %s' % result.get_vertex_value (str(N))
 - 
 
92 
				# Set the goal node's shape to be a diamond
 112 
				# Set the goal node's shape to be a diamond
93 
				result.set_vertex_shape (str(N), yapgvb.shapes.diamond)
 113 
				result.set_vertex_shape (str(N), yapgvb.shapes.diamond)
- 
 
 114 
 
- 
 
 115 
				# Create the return result
- 
 
 116 
				search_result = SearchResult (completed=True,
- 
 
 117 
							status='Success',
- 
 
 118 
							depth_reached=N.depth,
- 
 
 119 
							nodes_created=len(OPEN)+len(CLOSED),
- 
 
 120 
							result_graph=result)
94 
				return result
 121 
				return search_result
95 
 
 122 
 
96 
			# Add the children of N (aka M) to OPEN
 123 
			# Add the children of N (aka M) to OPEN
97 
			OPEN = add_function (M, OPEN, CLOSED)
 124 
			OPEN = add_function (M, OPEN, CLOSED)
98 
 
 125 
 
99 
			counter += 1
 126 
			counter += 1
100 
 
 127 
 
101 
			# Check to make sure we don't loop for too long
 128 
			# Check to make sure we don't loop for too long
102 
			if (len(OPEN) + len(CLOSED)) > MAX_NODES_CREATED:
 129 
			if (len(OPEN) + len(CLOSED)) > MAX_NODES_CREATED:
- 
 
 130 
				search_result = SearchResult (completed=False,
- 
 
 131 
							status='FAILURE -- Max nodes exceeded',
- 
 
 132 
							depth_reached=N.depth,
- 
 
 133 
							nodes_created=len(OPEN)+len(CLOSED),
- 
 
 134 
							result_graph=None)
103 
				return 'FAILURE'
 135 
				return search_result
104 
 
 136 
 
- 
 
 137 
		search_result = SearchResult (completed=False,
- 
 
 138 
					status='FAILURE -- goal not found',
- 
 
 139 
					depth_reached=N.depth,
- 
 
 140 
					nodes_created=len(OPEN)+len(CLOSED),
- 
 
 141 
					result_graph=None)
105 
		return 'FAILURE'
 142 
		return search_result
106 
 
 143 
 
- 
 
 144 
################################################################################
- 
 
 145 
### Specific Search Algorithms
- 
 
 146 
################################################################################
107 
def add_bfs (M, OPEN, CLOSED):
 147 
def add_bfs (M, OPEN, CLOSED):
108 
	for node in M:
 148 
	for node in M:
109 
		if (node not in OPEN) and (node not in CLOSED):
 149 
		if (node not in OPEN) and (node not in CLOSED):
110 
			OPEN.append (node)
 150 
			OPEN.append (node)
111 
 
 151 
 
Line 116... Line 156...
116 
		if (node not in OPEN) and (node not in CLOSED):
 156 
		if (node not in OPEN) and (node not in CLOSED):
117 
			OPEN.insert (0, node) # insert node at beginning
 157 
			OPEN.insert (0, node) # insert node at beginning
118 
 
 158 
 
119 
	return OPEN
 159 
	return OPEN
120 
 
 160 
 
- 
 
 161 
def best_first_generic (M, OPEN, CLOSED, heuristic_func):
- 
 
 162 
	newopen = []
- 
 
 163 
 
- 
 
 164 
	for node in M:
- 
 
 165 
		if (node not in OPEN) and (node not in CLOSED):
- 
 
 166 
			OPEN.append (node)
- 
 
 167 
 
- 
 
 168 
	for node in OPEN:
- 
 
 169 
		heuristic = heuristic_func (node)
- 
 
 170 
		newopen.append ((heuristic, node))
- 
 
 171 
 
- 
 
 172 
	newopen.sort ()
- 
 
 173 
 
- 
 
 174 
	return [n[1] for n in newopen]
- 
 
 175 
 
- 
 
 176 
def bfs_oop (M, OPEN, CLOSED):
- 
 
 177 
	return best_first_generic (M, OPEN, CLOSED, lambda x: x.num_out_of_place ())
- 
 
 178 
 
- 
 
 179 
def bfs_dfc (M, OPEN, CLOSED):
- 
 
 180 
	return best_first_generic (M, OPEN, CLOSED, lambda x: x.total_distance_from_correct ())
- 
 
 181 
 
- 
 
 182 
def astar_bfs (M, OPEN, CLOSED):
- 
 
 183 
	return best_first_generic (M, OPEN, CLOSED, lambda x: x.depth)
- 
 
 184 
 
- 
 
 185 
def astar_oop (M, OPEN, CLOSED):
- 
 
 186 
	return best_first_generic (M, OPEN, CLOSED,
- 
 
 187 
			lambda x: x.depth + x.num_out_of_place ())
- 
 
 188 
 
- 
 
 189 
def astar_dfc (M, OPEN, CLOSED):
- 
 
 190 
	return best_first_generic (M, OPEN, CLOSED,
- 
 
 191 
			lambda x: x.depth + x.total_distance_from_correct ())
- 
 
 192 
 
121 
 
 193 
 
122 
from Graph import Graph
 194 
from Graph import Graph
123 
from DrawGraph import DrawGraph
 195 
from DrawGraph import DrawGraph
124 
import random
 196 
import random
125 
 
 197 
 
Line 131... Line 203...
131 
	return child
 203 
	return child
132 
 
 204 
 
133 
def main ():
 205 
def main ():
134 
	initial = [1, 2, 3, 4, 'E', 5, 6, 7, 8]
 206 
	initial = [1, 2, 3, 4, 'E', 5, 6, 7, 8]
135 
 
 207 
 
136 
	start = PuzzlePiece (initial)
 208 
	start = PuzzlePiece (initial) # temporary use!
137 
	goal = get_nth_child (start, 10)
 209 
	goal = get_nth_child (start, 20)
- 
 
 210 
	start = PuzzlePiece (initial, 0, goal)
138 
 
 211 
 
139 
	s = PuzzleSearch (start, (goal, ))
 212 
	s = PuzzleSearch (start, (goal, ))
- 
 
 213 
 
- 
 
 214 
	# Run some tests
- 
 
 215 
	result = s.search (add_dfs, 1000)
- 
 
 216 
	result.set_search_name ('Depth First Search')
- 
 
 217 
	print result
- 
 
 218 
	print
- 
 
 219 
 
140 
	result = s.search (add_bfs, 1000)
 220 
	result = s.search (add_bfs, 1000)
- 
 
 221 
	result.set_search_name ('Breadth First Search: normal')
- 
 
 222 
	print result
- 
 
 223 
	print
- 
 
 224 
 
- 
 
 225 
	result = s.search (bfs_oop, 1000)
- 
 
 226 
	result.set_search_name ('Best First Search: Out-of-place')
- 
 
 227 
	print result
- 
 
 228 
	print
- 
 
 229 
 
- 
 
 230 
	result = s.search (astar_bfs, 1000)
- 
 
 231 
	result.set_search_name ('A*-search: Breadth-first-search')
- 
 
 232 
	print result
- 
 
 233 
	print
- 
 
 234 
 
- 
 
 235 
	result = s.search (astar_oop, 1000)
- 
 
 236 
	result.set_search_name ('A*-search: Out-of-place')
- 
 
 237 
	print result
- 
 
 238 
	print
- 
 
 239 
 
- 
 
 240 
	result = s.search (astar_dfc, 1000)
- 
 
 241 
	result.set_search_name ('A*-search: Distance-from-correct')
- 
 
 242 
	print result
- 
 
 243 
	print
141 
 
 244 
 
142 
	if result != 'FAILURE':
 245 
	if result.result_graph != None:
143 
		DrawGraph ('result', result).render_graph ('res.svg', yapgvb.engines.dot)
 246 
		DrawGraph ('result', result.result_graph).render_graph ('res.svg', yapgvb.engines.dot)
144 
	else:
 247 
	else:
145 
		print result
 248 
		print 'Failed to render graph'
146 
 
 249 
 
147 
 
 250 
 
148 
if __name__ == '__main__':
 251 
if __name__ == '__main__':
149 
	main ()
 252 
	main ()