Subclasses for other search algorithms In this part of the assignment you will i
ID: 3867277 • Letter: S
Question
Subclasses for other search algorithms
In this part of the assignment you will implement other state-space search algorithms by defining classes for new types of searcher objects.
Uninformed state-space search: BFS and DFS
In searcher.py, define a class called BFSearcher for searcher objects that perform breadth-first search (BFS) instead of random search. As discussed in class, BFS involves always choosing one the untested states that has the smallest depth (i.e., the smallest number of moves from the initial state).
This class should be a subclass of the Searcher class that you implemented in Part III, and you should take full advantage of inheritance. In particular, you should not need to include any attributes in your BFSearcher class, because all of the necessary attributes will be inherited from Searcher.
Similarly, you should not need to define many methods, because most of necessary functionality is already provided in the methods that are inherited from Searcher.
However, you will need to do the following:
Make sure that your class header specifies that BFSearcher inherits from Searcher.
Because all of the attributes of a BFSearcher are inherited from Searcher, you will not need to define a constructor for this class. Rather, we can just use the constructor that is inherited from Searcher.
Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. Rather than choosing at random from the list of untested states, this version of next_state should follow FIFO (first-in first-out) ordering – choosing the state that has been in the list the longest. In class, we discussed why this leads to breadth-first search. As with the original version of next_state, this version should remove the chosen state from the list of untested states before returning it.
Examples:
In searcher.py, define a class called DFSearcher for searcher objects that perform depth-first search (DFS) instead of random search. As discussed in class, DFS involves always choosing one the untested states that has the largest depth (i.e., the largest number of moves from the initial state).
DFS, the next state to be tested should be one of the ones that has the largest depth in the state-space search tree.
Here again, the class should be a subclass of the Searcher class, and you should take full advantage of inheritance. The necessary steps are very similar to the ones that you took for BFSearcher, but the next_state() method should follow LIFO (last-in first-out) ordering – choosing the state that was most recently added to the list.
Examples:
In eight_puzzle.py, there is a helper function called create_searcher that is used to create the appropriate type of searcher object. Modify this helper function so that it will be able to create objects that perform BFS and DFS. To do so, simply uncomment the lines that handle cases in which the algorithm input is 'BFS' or 'DFS'. Once you do so, you should be able to use the eight_puzzle driver function to test your BFSearcher andDFSearcher classes.
Breadth-first search should quickly solve the following puzzle:
You may get a different time than we did, but the rest of the results should be the same. As discussed in class, BFS finds an optimal solution for eight-puzzle problems, so 5 moves is the fewest possible moves for this particular initial state.
Depth-first search, on the other hand, ends up going deep in the search tree before it finds a goal state:
Important: In cases like this one in which the solution has an extremely large number of moves, trying to show the moves is likely to cause an error. That’s because our print_moves_to method uses recursion, and the number of recursive calls is equal to the number of moves in the solution. Each recursive call adds a new stack frame to the top of the memory stack, and we can end up overflowing the stack when we make that many recursive calls.
To get a solution from DFS with fewer moves, we can impose a depth limit by passing it in as the third argument to the eight_puzzle function. For example:
Using a depth limit of 25 keeps DFS from going too far down a bad path, but the resulting solution requires 23 moves, which is still far from optimal!
Informed state-space search: Greedy and A*
In searcher.py, define a class called GreedySearcher for searcher objects that perform greedy search. As discussed in class, greedy search is an informed search algorithms that uses a heuristic function to estimate the remaining cost needed to get from a given state to the goal state (for the Eight Puzzle, this is just an estimate of how many additional moves are needed). Greedy Search uses this heuristic function to assign a priority to each state, and it selects the next state based on those priorities.
Once again, this class should be a subclass of the Searcher class that you implemented in Part III, and you should take full advantage of inheritance. However, the changes required in this class will be more substantial that the ones in BFSearcher andDFSearcher. Among other things, GreedySearcher objects will have a new attribute called heuristic that will allow you to choose among different heuristic functions, and they will also have a new method for computing the priority of a state.
Here are the necessary steps:
Make sure that your class header specifies that GreedySearcher inherits from Searcher.
Write a method priority(self, state) that takes a State object called state, and that computes and returns the priority of that state. For now, the method should compute the priority as follows:
where num_misplaced_tiles is the number of misplaced tiles in the Board object associated with state. Take advantage of the appropriate Board method to determine this value.
Copy the following constructor into the GreedySearcher class:
Make sure to maintain the appropriate indentation when you do so.
Two things worth noting:
GreedySearcher objects have an extra attribute called heuristic (and an associated extra input to their constructor). This attribute stores a reference to
which heuristic function the GreedySearcher should use. We’re not currently using this attribute in our priority method, but ultimately the method will use this attribute to choose between multiple different heuristic functions for estimating a State‘s remaining cost. If needed, you should review the powerpoint notes about this on Blackboard.
A GreedySearcher object’s states attribute is not just a list of states. Rather, it is a list of lists, where each sublist is a [priority, state] pair. This will allow a GreedySearcher to choose its next state based on the priorities of the states. Thus, we initialize states to be a list containing a sublist in which the initial state is paired with its priority.
Example:
If you don’t see a priority value of -5, check your priority method for possible problems.
Write a method add_state(self, state) that overrides (i.e., replaces) the add_state method that is inherited from Searcher. Rather than simply adding the specified state to the list of untested states, the method should add a sublist that is a [priority, state] pair, where priority is the priority of state, as determined by calling the priority method.
Examples:
Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. This version of next_state should choose one of the states with the highest priority.
Hints:
You can use max to find the sublist with the highest priority. If multiple sublists are tied for the highest priority, max will choose one of them.
You should remove the selected sublist from states, and you should return only the state component of the sublist – not the entire sublist.
Examples:
In searcher.py, define a class called AStarSearcher for searcher objects that perform A* search. Like greedy search, A* is an informed search algorithm that assigns a priority to each state based on a heuristic function, and that selects the next state based on those priorities. However, when A* assigns a priority to a state, it also takes into account the cost that has already been expended to get to that state (i.e. the number of moves to that state). More specifically, the priority of a state is computed as follows:
where heuristic is the value that the selected heuristic function assigns to the state, and num_moves is the number of moves that it took to get to that state from the initial state.
Once again, you should take full advantage of inheritance. However, we’re leaving it up to you decide which class to inherit from and how much new, non-inherited code is needed!
Here’s one thing you need to know: When constructing an AStarSearcher object, you will need to specify two inputs: (1) function that specifies which heuristic function should be used, and (2) an integer for the depth limit. See below for an example of constructing one.
Examples:
Modify the create_searcher helper function in eight_puzzle.py so that it will be able to create GreedySearcher and AStarSearcher objects. To do so, simply uncomment the lines that handle cases in which the algorithm input is 'Greedy' or 'A*'.
After you do so, try using the eight_puzzle driver function to see how the informed search algorithms perform on various puzzles. Here are some digit strings for puzzles that you might want to try, along with the number of moves in their optimal solutions:
'142358607' - 5 moves
'031642785' - 8 moves
'341682075' - 10 moves
'631074852' - 15 moves
'763401852' - 18 moves
'145803627' - 20 moves
A* should obtain optimal solutions; Greedy Search may or may not.
If a given algorithm ends up taking longer than you can afford to wait, you can stop it by using Ctrl-C from the keyboard.
Explanation / Answer
state space tree nodes
struct Node
{
// stores parent node of current node
// helps in tracing path when answer is found
Node* parent;
// stores matrix
int mat[N][N];
// stores blank tile cordinates
int x, y;
// stores the number of misplaced tiles
int cost;
// stores the number of moves so far
int level;
};
// Function to print N x N matrix
int printMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ", mat[i][j]);
printf(" ");
}
}
// Function to allocate a new node
Node* newNode(int mat[N][N], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
// set pointer for path to root
node->parent = parent;
// copy data from parent node to current node
memcpy(node->mat, mat, sizeof node->mat);
// move tile by 1 postion
swap(node->mat[x][y], node->mat[newX][newY]);
// set number of misplaced tiles
node->cost = INT_MAX;
// set number of moves so far
node->level = level;
// update new blank tile cordinates
node->x = newX;
node->y = newY;
return node;
}
// botton, left, top, right
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
// Function to calculate the the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
int calculateCost(int initial[N][N], int final[N][N])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
// Function to check if (x, y) is a valid matrix cordinate
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// print path from root node to destination node
void printPath(Node* root)
{
if (root == NULL)
return;
printPath(root->parent);
printMatrix(root->mat);
printf(" ");
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
void solve(int initial[N][N], int x, int y,
int final[N][N])
{
// Create a priority queue to store live nodes of
// search tree;
priority_queue<Node*, std::vector<Node*>, comp> pq;
// create a root node and calculate its cost
Node* root = newNode(initial, x, y, x, y, 0, NULL);
root->cost = calculateCost(initial, final);
// Add root to list of live nodes;
pq.push(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while (!pq.empty())
{
// Find a live node with least estimated cost
Node* min = pq.top();
// The found node is deleted from the list of
// live nodes
pq.pop();
// if min is an answer node
if (min->cost == 0)
{
// print the path from root to destination;
printPath(min);
return;
}
// do for each child of min
// max 4 children for a node
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
// create a child node and calculate
// its cost
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
// Add child to list of live nodes
pq.push(child);
}
}
}
}
// Driver code
int main()
{
// Initial configuration
// Value 0 is used for empty space
int initial[N][N] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
// Solvable Final configuration
// Value 0 is used for empty space
int final[N][N] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
// Blank tile coordinates in initial
// configuration
int x = 1, y = 2;
solve(initial, x, y, final);
return 0;
}