Starting from:
$30
COMS4701-Homework 1 Search Solved
In this assignment you will create an agent to solve the Npuzzle game. You will implement and compare several search algorithms, and collect some statistics related to their performances.
I. Introduction
The Npuzzle game consists of a board holding N = m^2 − 1 distinct movable tiles, plus one empty space. There is one tile for each number in the set {1, …, m^2 − 1}. In this assignment, we will represent the blank s pace with the number 0 and focus on the m = 3 case (8puzzle).
In this combinatorial search problem, the aim is to get from any initial board state to the configuration with all tiles arranged in ascending order ⟨0, 1,…, m^2 − 1⟩ this is your goal state. The search space is the set of all possible states reachable from the initial state. Each move consists of swapping the empty space with a component in one of the four directions {‘Up’, ‘Down’, ‘Left’, ‘Right’}. Give each move a cost of one. Thus, the total cost of a path will be equal to the number of moves made.
II. Algorithm Review
Recall from lecture that search begins by visiting the root node of the search tree, given by the initial state. Three main events occur when visiting a node:
First, we remove a node from the frontier set.
Second, we check if this node matches the goal state.
If not, we then expand the node. To expand a node, we generate all of its immediate successors and add them to the frontier, if they (i) are not yet already in the frontier, and (ii) have not been visited yet.
This describes the life cycle of a visit, and is the basic order of operations for search agents in this assignment—(1) remove, (2) check, and (3) expand. We will implement the assignment algorithms as described here. Please refer to lecture notes for further details, and review the lecture pseudocode before you begin.
IMPORTANT: You may encounter implementations that attempt to shortcircuit this order by performing the goalcheck on successor nodes immediately upon expansion of a parent node. For example, Russell & Norvig's implementation of BFS does precisely this. Doing so may lead to edgecase gains in efficiency, but do not alter the general characteristics of complexity and optimality for each method. For simplicity and grading purposes in this assignment, do not make such modifications to algorithms learned in lecture.
IV. What Your Program Outputs
Your program will create and/or write to a file called o utput.txt, containing the following statistics:
path_to_goal: the sequence of moves taken to reach the goal cost_of_path: the number of moves taken to reach the goal nodes_expanded: the number of nodes that have been expanded search_depth: the depth within the search tree when the goal node is found max_search_depth: the maximum depth of the search tree in the lifetime of the algorithm running_time: the total running time of the search instance, reported in seconds max_ram_usage: the maximum RAM usage in the lifetime of the process as measured by the r u_maxrss attribute in the r esource module, reported in megabytes
Example #1: BreadthFirst Search
Suppose the program is executed for breadthfirst search as follows:
$ python driver.py bfs 1,2,5,3,4,0,6,7,8
This should result in the solution path:
.T he output file will contain e xactly the following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 10 search_depth: 3 max_search_depth: 4
running_time: 0.00188088
max_ram_usage: 0.07812500
Example #2: DepthFirst Search
.
Suppose the program is executed for depthfirst search as follows:
$ python driver.py dfs 1,2,5,3,4,0,6,7,8
This should result in the solution path:
.
The output file will contain e xactly the following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 181437
search_depth: 3
max_search_depth: 66125
running_time: 5.01608433
max_ram_usage: 4.23940217
.
More test cases are provided in t he FAQs.
Note on Correctness
.
All variables, except running_time and m ax_ram_usage, have one and only one correct answer when running BFS and DFS. A* nodes_expanded might vary depending on implementation details. You’ll be fine as long as your algorithm follows all specifications listed in these instructions.
As running_time and m ax_ram_usage values vary greatly depending on your machine and implementation details, there is no "correct" value to look for. They are for you to monitor time and space complexity of your code, which we highly recommend. A good way to check the correctness of your program is to walk through small examples by hand, like the ones above.
I. Introduction
The Npuzzle game consists of a board holding N = m^2 − 1 distinct movable tiles, plus one empty space. There is one tile for each number in the set {1, …, m^2 − 1}. In this assignment, we will represent the blank s pace with the number 0 and focus on the m = 3 case (8puzzle).
In this combinatorial search problem, the aim is to get from any initial board state to the configuration with all tiles arranged in ascending order ⟨0, 1,…, m^2 − 1⟩ this is your goal state. The search space is the set of all possible states reachable from the initial state. Each move consists of swapping the empty space with a component in one of the four directions {‘Up’, ‘Down’, ‘Left’, ‘Right’}. Give each move a cost of one. Thus, the total cost of a path will be equal to the number of moves made.
II. Algorithm Review
Recall from lecture that search begins by visiting the root node of the search tree, given by the initial state. Three main events occur when visiting a node:
First, we remove a node from the frontier set.
Second, we check if this node matches the goal state.
If not, we then expand the node. To expand a node, we generate all of its immediate successors and add them to the frontier, if they (i) are not yet already in the frontier, and (ii) have not been visited yet.
This describes the life cycle of a visit, and is the basic order of operations for search agents in this assignment—(1) remove, (2) check, and (3) expand. We will implement the assignment algorithms as described here. Please refer to lecture notes for further details, and review the lecture pseudocode before you begin.
IMPORTANT: You may encounter implementations that attempt to shortcircuit this order by performing the goalcheck on successor nodes immediately upon expansion of a parent node. For example, Russell & Norvig's implementation of BFS does precisely this. Doing so may lead to edgecase gains in efficiency, but do not alter the general characteristics of complexity and optimality for each method. For simplicity and grading purposes in this assignment, do not make such modifications to algorithms learned in lecture.
IV. What Your Program Outputs
Your program will create and/or write to a file called o utput.txt, containing the following statistics:
path_to_goal: the sequence of moves taken to reach the goal cost_of_path: the number of moves taken to reach the goal nodes_expanded: the number of nodes that have been expanded search_depth: the depth within the search tree when the goal node is found max_search_depth: the maximum depth of the search tree in the lifetime of the algorithm running_time: the total running time of the search instance, reported in seconds max_ram_usage: the maximum RAM usage in the lifetime of the process as measured by the r u_maxrss attribute in the r esource module, reported in megabytes
Example #1: BreadthFirst Search
Suppose the program is executed for breadthfirst search as follows:
$ python driver.py bfs 1,2,5,3,4,0,6,7,8
This should result in the solution path:
.T he output file will contain e xactly the following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 10 search_depth: 3 max_search_depth: 4
running_time: 0.00188088
max_ram_usage: 0.07812500
Example #2: DepthFirst Search
.
Suppose the program is executed for depthfirst search as follows:
$ python driver.py dfs 1,2,5,3,4,0,6,7,8
This should result in the solution path:
.
The output file will contain e xactly the following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 181437
search_depth: 3
max_search_depth: 66125
running_time: 5.01608433
max_ram_usage: 4.23940217
.
More test cases are provided in t he FAQs.
Note on Correctness
.
All variables, except running_time and m ax_ram_usage, have one and only one correct answer when running BFS and DFS. A* nodes_expanded might vary depending on implementation details. You’ll be fine as long as your algorithm follows all specifications listed in these instructions.
As running_time and m ax_ram_usage values vary greatly depending on your machine and implementation details, there is no "correct" value to look for. They are for you to monitor time and space complexity of your code, which we highly recommend. A good way to check the correctness of your program is to walk through small examples by hand, like the ones above.
1 file (303.6KB)
