Test Problems

Eight Puzzle

class py_search.problems.eight_puzzle.EightPuzzle

An eight puzzle class that can be used to test different search algorithms. When first created the puzzle is in the solved state.

copy()

Makes a deep copy of an EightPuzzle object.

executeAction(action)

Executes an action to the EightPuzzle object.

Parameters:action ("up", "left", "right", or "down") – the action to execute

legalActions()

Returns an iterator to the legal actions that can be executed in the current state.

randomize(num_shuffles)

Randomizes an EightPuzzle by executing a random action num_suffles times.

class py_search.problems.eight_puzzle.EightPuzzleProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

This class wraps around an Eight Puzzle object and instantiates the successor and goal test functions necessary for conducting search.

This class also implements an heuristic function which is used to compute the value for each successor as cost to node + heuristic estimate of distance to goal. This yield A* search when used with best first search or a more greedy variant when used with Beam Search.

goal_test(node)

Check if the goal state has been reached.

misplaced_tile_heuristic(state)

The misplaced tiles heuristic.

node_value(node)

The function used to compute the value of a node.

successors(node)

Computes successors and computes the value of the node as cost + heuristic, which yields A* search when using best first search.

class py_search.problems.eight_puzzle.NoHeuristic(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.problems.eight_puzzle.EightPuzzleProblem

A variation on the Eight Puzzle Problem that has a heuristic for 0. This yields something equivelent to dijkstra’s algorithm when used with best first search and a more greedy variant when used with Beam Search.

node_value(node)

N-Queens Problem

class py_search.problems.nqueens.LocalnQueensProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

A class that wraps around the nQueens object. This version of the problem starts with an empty board and then progressively adds queens.

goal_test(node)

Check if the goal state (i.e., no queen conflicts) has been reached.

random_node()

random_successor(node)

Generate all permutations of rows.

successors(node)

Generate all permutations of rows.

class py_search.problems.nqueens.nQueens(n)

An nQueens puzzle object

copy()

Makes a deep copy of an nQueens object.

num_conflicts()

Returns a count of the number of conflicts. First checks if there are column conflicts (row conflicts are impossible because of representation). Then checks for diagonals.

randomize()

Randomizes an nQueens by shuffling a list of row to columns assignments.

class py_search.problems.nqueens.nQueensProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

A class that wraps around the nQueens object. This version of the problem starts with an empty board and then progressively adds queens.

goal_test(node)

Check if the goal state (i.e., no queen conflicts) has been reached.

node_value(node)

The function used to compute the value of a node.

successors(node)

Generate all possible next queen states.

Assignment Problem

class py_search.problems.assignment_problem.AssignmentProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

A tree search version of the assignment problem. Starts with an initially empty assignment and then incrementally builds the assignment up adding one assignment per expansion.

goal_test(node)

A test of whether a complete assignment has been reached.

min_cost_heuristic(node)

A huristic specifying the minimum cost that could be achieved for unassigned rows.

node_value(node)

The value of a node is the combination of the node cost and the min_cost heuristic

successors(node)

An iterator that yields the sucessors of the provided node.

class py_search.problems.assignment_problem.LocalAssignmentProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

This class represents a local search version of the assignment problem. I.e., a random state is generated to start the search and then neighbors of the state can be expanded in order to reduce the solution cost.

goal_test(node)

node_value(node)

Returns a lower bound on the solution cost reachable from the given node (or its children)

random_node()

Generates a node that has a random assignment.

random_successor(node)

A function that returns a random successor of the current node. This is used by the simulated annealing function, so it doesn’t have to expand all successors.

A successor is generated by randomly flipping a pair of row to column assignments.

successors(node)

Generates successor states by flipping each pair of row to column assignments.

py_search.problems.assignment_problem.cost(assignment, costs)

Given an assignemnt and a cost matrix, returns the cost of the assignment.

py_search.problems.assignment_problem.print_matrix(m)

Print a matrix

py_search.problems.assignment_problem.random_assignment(n)

Returns a random valid assignment for an n x n matrix

py_search.problems.assignment_problem.random_matrix(n)

Generates an a list of list of floats (representing an n x n matrix) where the values have mean 0 and std 1.

This is used as cost matrix for an assignment problem.

Graph Partition Problem

class py_search.problems.graph_partition.LocalGraphPartitionProblem(initial, goal=None, initial_cost=0, extra=None)

Bases: py_search.base.Problem

This class represents a local search version of the graph partition problem. I.e., a random state is generated to start the search and then neighbors of the state can be expanded in order to reduce the solution cost.

goal_test(node)

The search should never terminate early.

node_value(node)

This function is used by the branch_and_bound approach to determine whether successor nodes have the potential to be better than the current node. If this just returns the node cost, then the algorithm will explore nodes greedily.

random_node()

Generates a node that has a random assignment.

random_successor(node)

A function that returns a random successor of the current node. This is used by the simulated annealing function, so it doesn’t have to expand all successors.

A successor is generated by randomly flipping a pair of row to column assignments.

successors(node)

Generates successor states by flipping each pair of row to column assignments.

py_search.problems.graph_partition.cutsize(E, p)

py_search.problems.graph_partition.generate_graph(n, p)

Generates a random graph for graph partitioning. n specifies the number of nodes and p specifies the probability that any pair of nodes has a transition.

py_search.problems.graph_partition.random() → x in the interval [0, 1).

py_search.problems.graph_partition.random_partition(V)