Search

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.

class search.Problem(initial, goal=None)

Bases: object

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.

actions(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.

result(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).

goal_test(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.

path_cost(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.

value(state)

For optimization problems, each state has a value. Hill Climbing and related algorithms try to maximize this value.

class search.Node(state, parent=None, action=None, path_cost=0)

Bases: object

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.

expand(problem)

List the nodes reachable in one step from this node.

child_node(problem, action)

[Figure 3.10]

solution()

Return the sequence of actions to go from the root to this node.

path()

Return a list of nodes forming the path from the root to this node.

class search.SimpleProblemSolvingAgentProgram(initial_state=None)

Bases: object

[Figure 3.1] Abstract framework for a problem-solving agent.

update_state(state, percept)

Update the agent’s world state from the latest percept (abstract).

formulate_goal(state)

Decide on a goal to pursue given the current state (abstract).

formulate_problem(state, goal)

Build a Problem instance from the current state and chosen goal (abstract).

search(problem)

Return a sequence of actions that solves the given problem (abstract).

search.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.

search.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.

search.depth_first_graph_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. Does not get trapped by loops. If two paths reach a state, only use the first one.

search.breadth_first_graph_search(problem)

[Figure 3.11] Note that this function can be implemented in a single line as below: return graph_search(problem, FIFOQueue())

search.best_first_graph_search(problem, f, display=False)

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 breadth-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.

search.best_first_tree_search(problem, f, display=False)

Search the nodes with the lowest f scores first, without remembering the states already reached. This is the tree-search counterpart of best_first_graph_search: it drops the explored set and the frontier membership/replacement bookkeeping, so it is faster when the state space is a tree (no repeated states) but does not terminate on a graph that contains cycles. You specify the function f(node) that you want to minimize.

search.uniform_cost_search(problem, display=False)

[Figure 3.14]

search.uniform_cost_tree_search(problem, display=False)

[Figure 3.14] Tree-search version of uniform-cost search.

search.depth_limited_search(problem, limit=50)

[Figure 3.17]

search.iterative_deepening_search(problem)

[Figure 3.18]

search.bidirectional_search(problem)

Meet-in-the-middle (MM) bidirectional search. Searches forward from the initial state and backward from the goal at the same time, returning the cost of the optimal path where the two frontiers meet (np.inf if no path exists).

search.greedy_best_first_graph_search(problem, f, display=False)

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 breadth-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.

search.greedy_best_first_tree_search(problem, f, display=False)

Search the nodes with the lowest f scores first, without remembering the states already reached. This is the tree-search counterpart of best_first_graph_search: it drops the explored set and the frontier membership/replacement bookkeeping, so it is faster when the state space is a tree (no repeated states) but does not terminate on a graph that contains cycles. You specify the function f(node) that you want to minimize.

search.astar_search(problem, h=None, display=False)

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, or else in your Problem subclass.

search.astar_tree_search(problem, h=None, display=False)

Tree-search version of A*: best-first tree search with f(n) = g(n) + h(n). Faster than astar_search when the state space is a tree, since it keeps no explored set. You need to specify the h function when you call astar_tree_search, or else in your Problem subclass.

search.iterative_deepening_astar_search(problem, h=None)

[Section 3.5.3] Iterative-deepening A* search: repeatedly run a depth-first search bounded by an f = g + h contour, raising the bound to the smallest f that exceeded it, until a goal within the bound is found.

class search.EightPuzzle(initial, goal=(1, 2, 3, 4, 5, 6, 7, 8, 0))

Bases: Problem

The problem of sliding tiles numbered from 1 to 8 on a 3x3 board, where one of the squares is a blank. A state is represented as a tuple of length 9, where element at index i represents the tile number at index i (0 if it’s an empty square)

find_blank_square(state)

Return the index of the blank square in a given state

actions(state)

Return the actions that can be executed in the given state. The result would be a list, since there are only four possible actions in any given state of the environment

result(state, action)

Given state and action, return a new state that is the result of the action. Action is assumed to be a valid action in the state

goal_test(state)

Given a state, return True if state is a goal state or False, otherwise

check_solvability(state)

Checks if the given state is solvable

h(node)

Return the heuristic value for a given state. Default heuristic function used is h(n) = number of misplaced tiles

class search.NPuzzle(initial=None, goal=None, size=3, heuristic='hamming', shuffle=10)

Bases: Problem

Generalization of the Eight Puzzle problem. The problem consists of sliding tiles numbered from 1 to N ^2 on a NxN board, where one of the squares is a blank. The state is represented as a tuple of length N^2, where element at index i represents the tile number at index i , where ‘0’ denotes empty square index

shuffle_state(shuffle, state)

Perform random action from the initial state

find_blank_square(state)

Return the index of the blank square in a given state

actions(state)

Return the actions that can be executed in the given state. The result would be a list of maximally four directions, since there are only four possible actions in any given state of the environment

result(state, action)

Given state and action, return a new state that is the result of the action. Action is assumed to be a valid action in the state

goal_test(state)

Given a state, return True if state is a goal state or False otherwise

check_solvability(state)

Checks if the given state is solvable. Whether or not puzzle is solvable depends on size being even or odd. If N is odd, then puzzle instance is solvable if number of inversions is even in the input state. If N is even, puzzle instance is solvable if the blank is on an even row counting from the bottom (second-last, fourth-last, etc.) and number of inversions is odd or the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.) and number of inversions is even.” reference : https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/

h(node)

Return the heuristic value for a given state. Default heuristic function used is h(n) = number of misplaced tiles

hamming_distance_heuristic(node)

Number of tiles that are not in their goal position (Hamming distance).

class search.TravelingSalesman(all_cities, initial, goal=None)

Bases: Problem

The problem of finding the shortest Hamiltonian cycle (tour) that visits every city exactly once and returns to the start.

value(state)

Define state value

actions(state)

Return the actions that can be executed in the given state. The result would be a list

result(state, action)

Given state and action, return a new state that is the result of the action. Action is assumed to be a valid action in the state

goal_test(state)

Given a state, return True if state is a goal state or False, otherwise

get_unvisited_cities(state)

Returns unused actions(cities)

path_cost(c, state1, action, state2)

Return next state cost

h(node)

Admissible heuristic: total edge weight of the MST over the cities that have not yet been visited.

eval_unvisited_mst_edges_sum(unvisited_nodes)

Return the total MST edge weight over the unvisited cities (0.0 if none).

tsp_kruskal(unvisited_nodes)

Generate MST of the graph and return sum of edges

init_distance_matrix(all_cities)

Generate matrix of distance between all cities

class search.DisjointSets

Bases: object

Union-find (disjoint-set) structure with union by rank, used to build the MST for the TravelingSalesman heuristic.

make_set(vertex)

Create a new singleton set whose only element is vertex.

find(vertex)

Return the representative (root) of the set that vertex belongs to.

union(vertex_u, vertex_v)

Merge the sets containing vertex_u and vertex_v, attaching the lower-rank tree under the higher-rank one (union by rank).

class search.PlanRoute(initial, goal, allowed, dimrow)

Bases: Problem

The problem of moving the Hybrid Wumpus Agent from one place to other

actions(state)

Return the actions that can be executed in the given state. The result would be a list, since there are only three possible actions in any given state of the environment

result(state, action)

Given state and action, return a new state that is the result of the action. Action is assumed to be a valid action in the state. A fresh state object is returned; the input state is never mutated, so the search tree stays consistent.

goal_test(state)

Return True when the state matches any goal position. The goal is a collection of [x, y] cells or of position objects; for the latter the orientation must match too (e.g. a shooting position).

h(node)

Manhattan distance from the node’s location to the nearest goal cell.

search.recursive_best_first_search(problem, h=None)

[Figure 3.26]

search.hill_climbing(problem)

[Figure 4.2] From the initial node, keep choosing the neighbor with highest value, stopping when no neighbor is better.

search.exp_schedule(k=20, lam=0.005, limit=100)

One possible schedule function for simulated annealing

search.simulated_annealing(problem, schedule=<function exp_schedule.<locals>.<lambda>>)

[Figure 4.5] CAUTION: This differs from the pseudocode as it returns a state instead of a Node.

search.simulated_annealing_full(problem, schedule=<function exp_schedule.<locals>.<lambda>>)

This version returns all the states encountered in reaching the goal state.

search.and_or_graph_search(problem)

[Figure 4.11]Used when the environment is nondeterministic and completely observable. Contains OR nodes where the agent is free to choose any action. After every action there is an AND node which contains all possible states the agent may reach due to stochastic nature of environment. The agent must be able to handle all possible states of the AND node (as it may end up in any of them). Returns a conditional plan to reach goal state, or failure if the former is not possible.

class search.PourProblem(initial=None, goals=(), capacities=None)

Bases: Problem

Problem about pouring water between jugs to achieve some water level. Each state is a tuple of levels. In the initialization, provide a tuple of capacities, e.g. PourProblem(initial=(2, 4, 3), goals={7}, capacities=(8, 16, 32)), which means three jugs of capacity 8, 16, 32 currently filled with 2, 4, 3 units of water, respectively, and the goal is to get a level of 7 in any one of the jugs.

actions(state)

The actions executable in this state: fill or dump any jug, or pour one into another.

result(state, action)

The state that results from executing this action in this state.

goal_test(state)

True if any of the jugs has a level equal to one of the goal levels.

class search.PeakFindingProblem(initial, grid, defined_actions={'E': (1, 0), 'N': (0, 1), 'S': (0, -1), 'W': (-1, 0)})

Bases: Problem

Problem of finding the highest peak in a limited grid

actions(state)

Returns the list of actions which are allowed to be taken from the given state

result(state, action)

Moves in the direction specified by action

value(state)

Value of a state is the value it is the index to

class search.OnlineDFSAgent(problem)

Bases: object

[Figure 4.21] The abstract class for an OnlineDFSAgent. Override update_state method to convert percept to state. While initializing the subclass a problem needs to be provided which is an instance of a subclass of the Problem class.

update_state(percept)

To be overridden in most cases. The default case assumes the percept to be of type state.

class search.OnlineSearchProblem(initial, goal, graph)

Bases: Problem

A problem which is solved by an agent executing actions, rather than by just computation. Carried in a deterministic and a fully observable environment.

actions(state)

Return the actions available from state (the outgoing graph edges).

output(state, action)

Return the state reached by taking action in state.

h(state)

Returns least possible cost to reach a goal for the given state.

c(s, a, s1)

Returns a cost estimate for an agent to move from state ‘s’ to state ‘s1’.

update_state(percept)

Convert a percept into a state (abstract; override in subclasses).

goal_test(state)

Return True if state is the goal state.

class search.LRTAStarAgent(problem)

Bases: object

[Figure 4.24] Abstract class for LRTA*-Agent. A problem needs to be provided which is an instance of a subclass of Problem Class.

Takes a OnlineSearchProblem [Figure 4.23] as a problem.

LRTA_cost(s, a, s1, H)

Returns cost to move from state ‘s’ to state ‘s1’ plus estimated cost to get to goal from s1.

search.genetic_search(problem, ngen=1000, pmut=0.1, n=20)

Call genetic_algorithm on the appropriate parts of a problem. This requires the problem to have states that can mate and mutate, plus a value method that scores states.

search.genetic_algorithm(population, fitness_fn, gene_pool=[0, 1], f_thres=None, ngen=1000, pmut=0.1)

[Figure 4.8]

search.fitness_threshold(fitness_fn, f_thres, population)

Return the fittest individual if its fitness reaches f_thres, otherwise None (also None when no threshold f_thres is given).

search.init_population(pop_number, gene_pool, state_length)

Initializes population for genetic algorithm pop_number : Number of individuals in population gene_pool : List of possible values for individuals state_length: The length of each individual

search.select(r, population, fitness_fn)

Select r individuals from the population, sampling each with probability proportional to its fitness.

search.recombine(x, y)

Single-point crossover: combine a random-length prefix of x with the corresponding suffix of y.

search.recombine_uniform(x, y)

Uniform crossover: build a child string by taking roughly half of its genes from x and the rest from y, at random positions.

search.mutate(x, gene_pool, pmut)

With probability pmut, replace one randomly chosen gene of x with a random gene from gene_pool; otherwise return x unchanged.

class search.Graph(graph_dict=None, directed=True)

Bases: object

A graph connects nodes (vertices) 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.

make_undirected()

Make a digraph into an undirected graph by adding symmetric edges.

connect(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.

connect1(A, B, distance)

Add a link from A to B of given distance, in one direction only.

get(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 {}.

nodes()

Return a list of nodes in the graph.

search.UndirectedGraph(graph_dict=None)

Build a Graph where every edge (including future ones) goes both ways.

search.RandomGraph(nodes=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], min_links=2, width=400, height=300, curvature=<function <lambda>>)

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.

search.vacuum_world = <search.Graph object>

[Figure 4.23] One-dimensional state space Graph

class search.GraphProblem(initial, goal, graph)

Bases: Problem

The problem of searching a graph from one node to another.

actions(A)

The actions at a graph node are just its neighbors.

result(state, action)

The result of going to a neighbor is just that neighbor.

path_cost(cost_so_far, A, action, B)

Cost so far plus the length of the edge from A to B (np.inf if no edge).

find_min_edge()

Find minimum value of edges.

h(node)

h function is straight-line distance from a node’s state to goal.

class search.GraphProblemStochastic(initial, goal, graph)

Bases: GraphProblem

A version of GraphProblem where an action can lead to nondeterministic output i.e. multiple possible states.

Define the graph as dict(A = dict(Action = [[<Result 1>, <Result 2>, …], <cost>], …), …) A the dictionary format is different, make sure the graph is created as a directed graph.

result(state, action)

Return the list of possible states that the action may lead to.

path_cost()

Not defined for the stochastic graph problem.

class search.NQueensProblem(N)

Bases: 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 a value of r in the c-th entry means there is a queen at column c, row r, and a value of -1 means that the c-th column has not been filled in yet. We fill in columns left to right. >>> depth_first_tree_search(NQueensProblem(8)) <Node (7, 3, 0, 2, 5, 1, 6, 4)>

actions(state)

In the leftmost empty column, try all non-conflicting rows.

result(state, row)

Place the next queen at the given row.

conflicted(state, row, col)

Would placing a queen at (row, col) conflict with anything?

conflict(row1, col1, row2, col2)

Would putting two queens in (row1, col1) and (row2, col2) conflict?

goal_test(state)

Check if all columns filled, no conflicts.

h(node)

Return number of conflicting queens for a given node

search.random_boggle(n=4)

Return a random Boggle board of size n x n. We represent a board as a linear list of letters.

search.print_boggle(board)

Print the board in a 2-d array.

search.boggle_neighbors(n2, cache={})

Return a list of lists, where the i-th element is the list of indexes for the neighbors of square i.

search.exact_sqrt(n2)

If n2 is a perfect square, return its square root, else raise error.

class search.Wordlist(file, min_len=3)

Bases: object

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.

lookup(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.

class search.BoggleFinder(board=None)

Bases: object

A class that allows you to find all the words in a Boggle board.

wordlist = None

set_board(board=None)

Set the board, and find all the words in it.

find(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.

words()

The words found.

scores = [0, 0, 0, 0, 1, 2, 3, 5, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11]

score()

The total score for the words found, according to the rules.

search.boggle_hill_climbing(board=None, ntimes=100, verbose=True)

Solve inverse Boggle by hill-climbing: find a high-scoring board by starting with a random one and changing it.

search.mutate_boggle(board)

Randomly replace one cell of a Boggle board with a random face of a random die, returning the changed index and the old letter so the move can be undone.

class search.InstrumentedProblem(problem)

Bases: Problem

Delegates to a problem, and keeps statistics.

actions(state)

Delegate to the wrapped problem, counting the successor query.

result(state, action)

Delegate to the wrapped problem, counting the generated state.

goal_test(state)

Delegate to the wrapped problem, counting the goal test and recording the state when it is a goal.

path_cost(c, state1, action, state2)

Delegate the path cost computation to the wrapped problem.

value(state)

Delegate the state value computation to the wrapped problem.

search.compare_searchers(problems, header, searchers=[<function breadth_first_tree_search>, <function breadth_first_graph_search>, <function depth_first_graph_search>, <function iterative_deepening_search>, <function depth_limited_search>, <function recursive_best_first_search>])

Run every searcher on every problem and print a table of the resulting InstrumentedProblem statistics (successors / goal tests / states generated).

search.compare_graph_searchers()

Prints a table of search results.