Artificial Intelligence: A Modern Approach |

"""Search (Chapters 3-4) 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 __future__ import generators from utils import * import agents import math, random, sys, time, bisect, string

classProblem:"""The abstract class for a formal problem. You should subclass this and implement the method successor, 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 = goaldefsuccessor(self, state):"""Given a state, return a sequence of (action, state) pairs reachable from this state. If there are many successors, consider an iterator that yields the successors one at a time, rather than building them all at once. Iterators will work fine within the framework."""abstractdefgoal_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. Implement this method if checking against a single self.goal is not enough."""return state == self.goaldefpath_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 + 1defvalue(self):"""For optimization problems, each state has a value. Hill-climbing and related algorithms try to maximize this value."""abstract

classNode:"""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."update(self, state=state, parent=parent, action=action, path_cost=path_cost, depth=0) if parent: self.depth = parent.depth + 1def__repr__(self): return"<Node %s>"% (self.state,)defpath(self):"Create a list of nodes from the root to this node."x, result = self, [self] while x.parent: result.append(x.parent) x = x.parent return resultdefexpand(self, problem):"Return a list of nodes reachable from this node. [Fig. 3.8]"return [Node(next, self, act, problem.path_cost(self.path_cost, self.state, act, next)) for (act, next) in problem.successor(self.state)]

classSimpleProblemSolvingAgent(agents.Agent):"""Abstract framework for problem-solving agent. [Fig. 3.1]"""def__init__(self): Agent.__init__(self) state = [] seq = []defprogram(percept): state = self.update_state(state, percept) if not seq: goal = self.formulate_goal(state) problem = self.formulate_problem(state, goal) seq = self.search(problem) action = seq[0] seq[0:1] = [] return action self.program = program

## Uninformed Search algorithmsdeftree_search(problem, fringe):"""Search through the successors of a problem to find a goal. The argument fringe should be an empty queue. Don't worry about repeated paths to a state. [Fig. 3.8]"""fringe.append(Node(problem.initial)) while fringe: node = fringe.pop() if problem.goal_test(node.state): return node fringe.extend(node.expand(problem)) return Nonedefbreadth_first_tree_search(problem):"Search the shallowest nodes in the search tree first. [p 74]"return tree_search(problem, FIFOQueue())defdepth_first_tree_search(problem):"Search the deepest nodes in the search tree first. [p 74]"return tree_search(problem, Stack())defgraph_search(problem, fringe):"""Search through the successors of a problem to find a goal. The argument fringe should be an empty queue. If two paths reach a state, only use the best one. [Fig. 3.18]"""closed = {} fringe.append(Node(problem.initial)) while fringe: node = fringe.pop() if problem.goal_test(node.state): return node if node.state not in closed: closed[node.state] = True fringe.extend(node.expand(problem)) return Nonedefbreadth_first_graph_search(problem):"Search the shallowest nodes in the search tree first. [p 74]"return graph_search(problem, FIFOQueue())defdepth_first_graph_search(problem):"Search the deepest nodes in the search tree first. [p 74]"return graph_search(problem, Stack())defdepth_limited_search(problem, limit=50):"[Fig. 3.12]"defrecursive_dls(node, problem, limit): cutoff_occurred = False if problem.goal_test(node.state): return node elif node.depth == limit: return'cutoff'else: for successor in node.expand(problem): result = recursive_dls(successor, problem, limit) if result =='cutoff': cutoff_occurred = True elif result != None: return result if cutoff_occurred: return'cutoff'else: return None # Body of depth_limited_search: return recursive_dls(Node(problem.initial), problem, limit)defiterative_deepening_search(problem):"[Fig. 3.13]"for depth in xrange(sys.maxint): result = depth_limited_search(problem, depth) if result is not'cutoff': return result

# Informed (Heuristic) Searchdefbest_first_graph_search(problem, f):"""Search the nodes with the lowest f scores first. You specify the function f(node) that you want to minimize; for example, if f is a heuristic estimate to the goal, then we have greedy best first search; if f is node.depth then we have depth-first search. There is a subtlety: the line "f = memoize(f,'f')" means that the f values will be cached on the nodes as they are computed. So after doing a best first search you can examine the f values of the path returned."""f = memoize(f,'f') return graph_search(problem, PriorityQueue(min, f))greedy_best_first_graph_search= best_first_graph_search # Greedy best-first search is accomplished by specifying f(n) = h(n).defastar_search(problem, h=None):"""A* search is best-first graph search with f(n) = g(n)+h(n). You need to specify the h function when you call astar_search. Uses the pathmax trick: f(n) = max(f(n), g(n)+h(n))."""h = h or problem.hdeff(n): return max(getattr(n,'f', -infinity), n.path_cost + h(n)) return best_first_graph_search(problem, f)

## Other search algorithmsdefrecursive_best_first_search(problem):"[Fig. 4.5]"defRBFS(problem, node, flimit): if problem.goal_test(node.state): return node successors = expand(node, problem) if len(successors) == 0: return None, infinity for s in successors: s.f = max(s.path_cost + s.h, node.f) while True: successors.sort(lambda x,y: x.f - y.f) # Order by lowest f value best = successors[0] if best.f > flimit: return None, best.f alternative = successors[1] result, best.f = RBFS(problem, best, min(flimit, alternative)) if result is not None: return result return RBFS(Node(problem.initial), infinity)defhill_climbing(problem):"""From the initial node, keep choosing the neighbor with highest value, stopping when no neighbor is better. [Fig. 4.11]"""current = Node(problem.initial) while True: neighbor = argmax(expand(node, problem), Node.value) if neighbor.value() <= current.value(): return current.state current = neighbordefexp_schedule(k=20, lam=0.005, limit=100):"One possible schedule function for simulated annealing"return lambda t: if_(t < limit, k * math.exp(-lam * t), 0)defsimulated_annealing(problem, schedule=exp_schedule()):"[Fig. 4.5]"current = Node(problem.initial) for t in xrange(sys.maxint): T = schedule(t) if T == 0: return current next = random.choice(expand(node. problem)) delta_e = next.path_cost - current.path_cost if delta_e > 0 or probability(math.exp(delta_e/T)): current = nextdefonline_dfs_agent(a):"[Fig. 4.12]"pass #### moredeflrta_star_agent(a):"[Fig. 4.12]"pass #### more

# Genetic Algorithmdefgenetic_search(problem, fitness_fn, ngen=1000, pmut=0.0, n=20):"""Call genetic_algorithm on the appropriate parts of a problem. This requires that the problem has a successor function that generates reasonable states, and that it has a path_cost function that scores states. We use the negative of the path_cost function, because costs are to be minimized, while genetic-algorithm expects a fitness_fn to be maximized."""states = [s for (a, s) in problem.successor(problem.initial_state)[:n]] random.shuffle(states) fitness_fn = lambda s: - problem.path_cost(0, s, None, s) return genetic_algorithm(states, fitness_fn, ngen, pmut)defgenetic_algorithm(population, fitness_fn, ngen=1000, pmut=0.0):"""[Fig. 4.7]"""defreproduce(p1, p2): c = random.randrange(len(p1)) return p1[:c] + p2[c:] for i in range(ngen): new_population = [] for i in len(population): p1, p2 = random_weighted_selections(population, 2, fitness_fn) child = reproduce(p1, p2) if random.uniform(0,1) > pmut: child.mutate() new_population.append(child) population = new_population return argmax(population, fitness_fn)defrandom_weighted_selection(seq, n, weight_fn):"""Pick n elements of seq, weighted according to weight_fn. That is, apply weight_fn to each element of seq, add up the total. Then choose an element e with probability weight[e]/total. Repeat n times, with replacement. """totals = []; runningtotal = 0 for item in seq: runningtotal += weight_fn(item) totals.append(runningtotal) selections = [] for s in range(n): r = random.uniform(0, totals[-1]) for i in range(len(seq)): if totals[i] > r: selections.append(seq[i]) break return selections

# The remainder of this file implements examples for the search algorithms.

# Graphs and Graph ProblemsclassGraph:"""A graph connects nodes (verticies) by edges (links). Each edge can also have a length associated with it. The constructor call is something like: g = Graph({'A': {'B': 1, 'C': 2}) this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from A to B, and an edge of length 2 from A to C. You can also do: g = Graph({'A': {'B': 1, 'C': 2}, directed=False) This makes an undirected graph, so inverse links are also added. The graph stays undirected; if you add more links with g.connect('B', 'C', 3), then inverse link is also added. You can use g.nodes() to get a list of nodes, g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the length of the link from A to B. 'Lengths' can actually be any object at all, and nodes can be any hashable object."""def__init__(self, dict=None, directed=True): self.dict = dict or {} self.directed = directed if not directed: self.make_undirected()defmake_undirected(self):"Make a digraph into an undirected graph by adding symmetric edges."for a in self.dict.keys(): for (b, distance) in self.dict[a].items(): self.connect1(b, a, distance)defconnect(self, A, B, distance=1):"""Add a link from A and B of given distance, and also add the inverse link if the graph is undirected."""self.connect1(A, B, distance) if not self.directed: self.connect1(B, A, distance)defconnect1(self, A, B, distance):"Add a link from A to B of given distance, in one direction only."self.dict.setdefault(A,{})[B] = distancedefget(self, a, b=None):"""Return a link distance or a dict of {node: distance} entries. .get(a,b) returns the distance or None; .get(a) returns a dict of {node: distance} entries, possibly {}."""links = self.dict.setdefault(a, {}) if b is None: return links else: return links.get(b)defnodes(self):"Return a list of nodes in the graph."return self.dict.keys()defUndirectedGraph(dict=None):"Build a Graph where every edge (including future ones) goes both ways."return Graph(dict=dict, directed=False)defRandomGraph(nodes=range(10), min_links=2, width=400, height=300, curvature=lambda: random.uniform(1.1, 1.5)):"""Construct a random graph, with the specified nodes, and random links. The nodes are laid out randomly on a (width x height) rectangle. Then each node is connected to the min_links nearest neighbors. Because inverse links are added, some nodes will have more connections. The distance between nodes is the hypotenuse times curvature(), where curvature() defaults to a random number between 1.1 and 1.5."""g = UndirectedGraph() g.locations = {} ## Build the cities for node in nodes: g.locations[node] = (random.randrange(width), random.randrange(height)) ## Build roads from each city to at least min_links nearest neighbors. for i in range(min_links): for node in nodes: if len(g.get(node)) < min_links: here = g.locations[node]defdistance_to_node(n): if n is node or g.get(node,n): return infinity return distance(g.locations[n], here) neighbor = argmin(nodes, distance_to_node) d = distance(g.locations[neighbor], here) * curvature() g.connect(node, neighbor, int(d)) return gromania= UndirectedGraph(Dict( A=Dict(Z=75, S=140, T=118), B=Dict(U=85, P=101, G=90, F=211), C=Dict(D=120, R=146, P=138), D=Dict(M=75), E=Dict(H=86), F=Dict(S=99), H=Dict(U=98), I=Dict(V=92, N=87), L=Dict(T=111, M=70), O=Dict(Z=71, S=151), P=Dict(R=97), R=Dict(S=80), U=Dict(V=142))) romania.locations = Dict( A=( 91, 492), B=(400, 327), C=(253, 288), D=(165, 299), E=(562, 293), F=(305, 449), G=(375, 270), H=(534, 350), I=(473, 506), L=(165, 379), M=(168, 339), N=(406, 537), O=(131, 571), P=(320, 368), R=(233, 410), S=(207, 457), T=( 94, 410), U=(456, 350), V=(509, 444), Z=(108, 531))australia= UndirectedGraph(Dict( T=Dict(), SA=Dict(WA=1, NT=1, Q=1, NSW=1, V=1), NT=Dict(WA=1, Q=1), NSW=Dict(Q=1, V=1))) australia.locations = Dict(WA=(120, 24), NT=(135, 20), SA=(135, 30), Q=(145, 20), NSW=(145, 32), T=(145, 42), V=(145, 37))classGraphProblem(Problem):"The problem of searching a graph from one node to another."def__init__(self, initial, goal, graph): Problem.__init__(self, initial, goal) self.graph = graphdefsuccessor(self, A):"Return a list of (action, result) pairs."return [(B, B) for B in self.graph.get(A).keys()]defpath_cost(self, cost_so_far, A, action, B): return cost_so_far + (self.graph.get(A,B) or infinity)defh(self, node):"h function is straight-line distance from a node's state to goal."locs = getattr(self.graph,'locations', None) if locs: return int(distance(locs[node.state], locs[self.goal])) else: return infinity

#### NOTE: NQueensProblem not working properly yet.classNQueensProblem(Problem):"""The problem of placing N queens on an NxN board with none attacking each other. A state is represented as an N-element array, where the a value of r in the c-th entry means there is a queen at column c, row r, and a value of None means that the c-th column has not been filled in left. We fill in columns left to right."""def__init__(self, N): self.N = N self.initial = [None] * Ndefsuccessor(self, state):"In the leftmost empty column, try all non-conflicting rows."if state[-1] is not None: return [] ## All columns filled; no successors else:defplace(col, row): new = state[:] new[col] = row return new col = state.index(None) return [(row, place(col, row)) for row in range(self.N) if not self.conflicted(state, row, col)]defconflicted(self, state, row, col):"Would placing a queen at (row, col) conflict with anything?"for c in range(col-1): if self.conflict(row, col, state[c], c): return True return Falsedefconflict(self, row1, col1, row2, col2):"Would putting two queens in (row1, col1) and (row2, col2) conflict?"return (row1 == row2 ## same row or col1 == col2 ## same column or row1-col1 == row2-col2 ## same \ diagonal or row1+col1 == row2+col2) ## same / diagonaldefgoal_test(self, state):"Check if all columns filled, no conflicts."if state[-1] is None: return False for c in range(len(state)): if self.conflicted(state, state[c], c): return False return True

## Inverse Boggle: Search for a high-scoring Boggle board. A good domain for ## iterative-repair and related search tehniques, as suggested by Justin Boyan.ALPHABET='ABCDEFGHIJKLMNOPQRSTUVWXYZ'cubes16= ['FORIXB','MOQABJ','GURILW','SETUPL','CMPDAE','ACITAO','SLCRAE','ROMASH','NODESW','HEFIYE','ONUDTK','TEVIGN','ANEDVZ','PINESH','ABILYT','GKYLEU']defrandom_boggle(n=4):"""Return a random Boggle board of size n x n. We represent a board as a linear list of letters."""cubes = [cubes16[i % 16] for i in range(n*n)] random.shuffle(cubes) return map(random.choice, cubes) ## The best 5x5 board found by Boyan, with our word list this board scores ## 2274 words, for a score of 9837boyan_best= list('RSTCSDEIAEGNLRPEATESMSSID')defprint_boggle(board):"Print the board in a 2-d array."n2 = len(board); n = exact_sqrt(n2) for i in range(n2): if i % n == 0: print if board[i] =='Q': print'Qu', else: print str(board[i]) +' ', printdefboggle_neighbors(n2, cache={}):""""Return a list of lists, where the i-th element is the list of indexes for the neighbors of square i.""" if cache.get(n2): return cache.get(n2) n = exact_sqrt(n2) neighbors = [None] * n2 for i in range(n2): neighbors[i] = [] on_top = i < n on_bottom = i >= n2 - n on_left = i % n == 0 on_right = (i+1) % n == 0 if not on_top: neighbors[i].append(i - n) if not on_left: neighbors[i].append(i - n - 1) if not on_right: neighbors[i].append(i - n + 1) if not on_bottom: neighbors[i].append(i + n) if not on_left: neighbors[i].append(i + n - 1) if not on_right: neighbors[i].append(i + n + 1) if not on_left: neighbors[i].append(i - 1) if not on_right: neighbors[i].append(i + 1) cache[n2] = neighbors return neighborsdefIf n2 is a perfect square, return its square root, else raise error.exact_sqrt(n2): "" n = int(math.sqrt(n2)) assert n * n == n2 return n

classWordlist: """This class holds a list of words. You can use (word in wordlist) to check if a word is in the list, or wordlist.lookup(prefix) to see if prefix starts any of the words in the list."""def__init__(self, filename, min_len=3): lines = open(filename).read().upper().split() self.words = [word for word in lines if len(word) >= min_len] self.words.sort() self.bounds = {} for c in ALPHABET: c2 = chr(ord(c) + 1) self.bounds[c] = (bisect.bisect(self.words, c), bisect.bisect(self.words, c2))deflookup(self, prefix, lo=0, hi=None): """See if prefix is in dictionary, as a full word or as a prefix. Return two values: the first is the lowest i such that words[i].startswith(prefix), or is None; the second is True iff prefix itself is in the Wordlist.""" words = self.words i = bisect.bisect_left(words, prefix, lo, hi) if i < len(words) and words[i].startswith(prefix): return i, (words[i] == prefix) else: return None, Falsedef__contains__(self, word): return self.words[bisect.bisect_left(self.words, word)] == worddef__len__(self): return len(self.words)

classBoggleFinder: """A class that allows you to find all the words in a Boggle board.""" wordlist = None ## A class variable, holding a wordlistdef../data/wordlist__init__(self, board=None): if BoggleFinder.wordlist is None: BoggleFinder.wordlist = Wordlist("") self.found = {} if board: self.set_board(board)defSet the board, and find all the words in it.set_board(self, board=None): "" if board is None: board = random_boggle() self.board = board self.neighbors = boggle_neighbors(len(board)) self.found = {} for i in range(len(board)): lo, hi = self.wordlist.bounds[board[i]] self.find(lo, hi, i, [], '') return selfdeffind(self, lo, hi, i, visited, prefix): """Looking in square i, find the words that continue the prefix, considering the entries in self.wordlist.words[lo:hi], and not revisiting the squares in visited.""" if i in visited: return wordpos, is_word = self.wordlist.lookup(prefix, lo, hi) if wordpos is not None: if is_word: self.found[prefix] = True visited.append(i) c = self.board[i] if c == 'Q': c = 'QU' prefix += c for j in self.neighbors[i]: self.find(wordpos, hi, j, visited, prefix) visited.pop()defThe words found.words(self): "" return self.found.keys() scores = [0, 0, 0, 0, 1, 2, 3, 5] + [11] * 100defThe total score for the words found, according to the rules.score(self): "" return sum([self.scores[len(w)] for w in self.words()])defThe number of words found.__len__(self): "" return len(self.found)

defboggle_hill_climbing(board=None, ntimes=100, print_it=True): """Solve inverse Boggle by hill-climbing: find a high-scoring board by starting with a random one and changing it.""" finder = BoggleFinder() if board is None: board = random_boggle() best = len(finder.set_board(board)) for _ in range(ntimes): i, oldc = mutate_boggle(board) new = len(finder.set_board(board)) if new > best: best = new print best, _, board else: board[i] = oldc ## Change back if print_it: print_boggle(board) return board, bestdefmutate_boggle(board): i = random.randrange(len(board)) oldc = board[i] board[i] = random.choice(random.choice(cubes16)) ##random.choice(boyan_best) return i, oldc

## Code to compare searchers on various problems.classInstrumentedProblem(Problem): """Delegates to a problem, and keeps statistics."""defReturn a list of (action, state) pairs reachable from this state.__init__(self, problem): self.problem = problem self.succs = self.goal_tests = self.states = 0 self.found = Nonedefsuccessor(self, state): "" result = self.problem.successor(state) self.succs += 1; self.states += len(result) return resultdefReturn true if the state is a goal." self.goal_tests += 1 result = self.problem.goal_test(state) if result: self.found = state return resultgoal_test(self, state): "def__getattr__(self, attr): if attr in ('succs','goal_tests','states'): return self.__dict__[attr] else: return getattr(self.problem, attr)def__repr__(self): return'<%4d/%4d/%4d/%s>'% (self.succs, self.goal_tests, self.states, str(self.found)[0:4])defcompare_searchers(problems, header, searchers=[breadth_first_tree_search, breadth_first_graph_search, depth_first_graph_search, iterative_deepening_search, depth_limited_search, astar_search]):defdo(searcher, problem): p = InstrumentedProblem(problem) searcher(p) return p table = [[name(s)] + [do(s, p) for p in problems] for s in searchers] print_table(table, header)defcompare_graph_searchers(): compare_searchers(problems=[GraphProblem('A','B', romania), GraphProblem('O','N', romania), GraphProblem('Q','WA', australia)], header=['Searcher','Romania(A,B)','Romania(O, N)','Australia'])

AI: A Modern Approach by Stuart Russell and Peter Norvig | Modified: Jul 18, 2005 |