This page contained op Quiz 1.

RECAP


Breadth First Search

Depth First Search

Iterative Deepening


								def BFS(start, end):
									global queue
									queue.append((start, [start]))
									while queue:
										node, path = queue.pop(0)
										visited.add(node)
										if node==end:
											return path
										for i in G[node]:
											if i not in visited:
												visited.add(i)
												queue.append((i, path+[i]))

Implementing BFS


Uniform Cost Search


Extending BFS to Weighted Graphs

Uniform Cost Search


  • Instead of a queue, use a priority queue
  • Priority is based on the cost of the path
  • Always expand the least costly path


Let's walk through an example!

Uniform Cost Search



									G={
											0: {1:1, 6:1, 7:4, 8:8, 3:7},
											1: {0:1, 2:2, 5:2, 4:1, 6:2},
											2: {1:2, 10:2},
											3: {0:7},
											4: {1:1},
											5: {1:2, 10:4},
											6: {0:1, 1:2, 9:1},
											7: {9:1, 0:4, 8:1},
											8: {0:8, 7:1, -1: 1},
											9: {6:1, 7:1},
											10: {2:2, 5:4, -1: 1},
											-1: {8:1, 10:1},
										}

Uniform Cost Search



								def UCS(G, start, goal):
									visited=set()
									pqueue=[]
									heapq.heappush(pqueue, (0, (0, ())))
									while pqueue:
										cost, (node, path)=heapq.heappop(pqueue)
										if node not in visited:
											visited.add(node)
											path = path + (node,)
											if node==goal:
												return path
											for neighbour, edgeweight in G[node].items():
												if neighbour not in visited:
													heapq.heappush(pqueue, (cost+edgeweight, (neighbour, path)))

Towards Informed Search


Heuristics

Estimates of how good the next state is

Approximations, not necessarily exact values

Can often be quickly computed

Examples of

Heuristics


  • Mazes - Distance to goal
  • 8-puzzle - Number of tiles out of place
  • Driving - Straight line distance * constant factor

Properties of

Heuristics



Admissible Heuristics

Never overestimates cost to goal

Consistent Heuristics

For every node $n$ and every successor node $n'$
$h(n) \le c(n \rightarrow n') + h(n')$

Greedy Best-First Search


Expand the node that appears to be closest to goal

Uses only the heuristic function

Can get stuck in local optima

A* Search


Expand the node that appears to be closest to goal

Uses both the heuristic function and the cost to reach the node

Guaranteed to find the optimal path

A* Search



							def astar(G, start, goal):
								pqueue=[]
								heapq.heappush(pqueue, (H_score(G, start, goal), 0, (start, ())))
								while pqueue:
									heuristic, cost, (node, path)=heapq.heappop(pqueue)
									path = path + (node,)
									if node==goal:
										return path
									for neighbour, edgeweight in G[node].items():
										G_score=cost+edgeweight
										heapq.heappush(pqueue, (G_score+H_score(G, neighbour, goal), G_score, (neighbour, path)))

Beam Search


Expand only the $k$ best nodes

Straightforward extension to A* Search

Incomplete and Suboptimal

Alternate version: expand branches where
$f(n') = f(n) \pm \delta$

Local Search & Optimization



Explore neighboring states on a trial-and-error basis

Not systematic, but fast!


Can you think of examples?

Hill Climbing


Start with a random state

Move to the best neighboring state

Repeat until no better state is found

Can get stuck in local optima

Next Class



More on Hill Climbing

Simulated Annealing

Genetic Algorithms