1. Homepage
  2. Programming
  3. COMS 4701 Artificial Intelligence Homework 1: Coding - Search

COMS 4701 Artificial Intelligence Homework 1: Coding - Search

Engage in a Conversation
USColumbia UniversityCOMS 4701Artificial IntelligenceSearchBreadth-First SearchDepth-First SearchA-Star SearchBFSDFSA* SearchCOMS4701Python

COMS 4701 Artificial Intelligence
CourseNana.COM

Homework 1: Coding - Search CourseNana.COM


CourseNana.COM

In this assignment you will create an agent to solve the N-puzzle game. You will implement and compare several search algorithms, and collect some statistics related to their performances. Visit mypuzzle.org/sliding for the game’s rules. Please read all sections carefully: CourseNana.COM

I. Introduction
II. Algorithm Review
III. What You Need To Submit IV. What Your Program Outputs V. Implementation and Testing VI. Before You Finish
CourseNana.COM


CourseNana.COM


CourseNana.COM

I. Introduction CourseNana.COM

The N-puzzle game consists of a board holding N = m2 1 distinct movable tiles, plus one empty space. There is one tile for each number in the set {0, 1,..., m2 1}. In this assignment, we will represent the blank space with the number 0 and focus on the m = 3 case (8-puzzle). CourseNana.COM

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,..., m2 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. CourseNana.COM


CourseNana.COM

II. Algorithm Review CourseNana.COM

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: CourseNana.COM

First, we remove a node from the frontier set.
Second, we check if this node matches the goal state. CourseNana.COM

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. CourseNana.COM

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 pseudo-code before you begin. CourseNana.COM


CourseNana.COM

III. What You Need To Submit CourseNana.COM

Your job in this assignment is to write puzzle.py, which solves any 8-puzzle board when given an arbitrary starting configuration. The program will be executed as follows: CourseNana.COM

$ python3 puzzle.py <method> <board> CourseNana.COM

The method argument will be one of the following. You must implement all three of them: bfs (Breadth-First Search)
dfs (Depth-First Search)
ast (A-Star Search)
CourseNana.COM

The board argument will be a comma-separated list of integers containing no spaces. For example, to use the bread-first search strategy to solve the input board given by the starting configuration {0,8,7,6,5,4,3,2,1}, the pro- gram will be executed like so (with no spaces between commas): CourseNana.COM

$ python3 puzzle.py bfs 0,8,7,6,5,4,3,2,1 CourseNana.COM


IV. What Your Program Outputs CourseNana.COM

Your program will create and/or write to a file called output.txt, containing the following statistics: CourseNana.COM

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
CourseNana.COM

max ram usage: the maximum RAM usage in the lifetime of the process as measured by the ru maxrss attribute in the resource module, reported in megabytes CourseNana.COM

Example 1: Breadth-First Search CourseNana.COM

Suppose the program is executed for breadth-first search as follows: CourseNana.COM

$ python3 puzzle.py bfs 1,2,5,3,4,0,6,7,8 This should result in the solution path: CourseNana.COM

CourseNana.COM

The output file will contain exactly the following lines: CourseNana.COM

path to goal: [‘Up’, ‘Left’, ‘Left’] cost of path: 3
nodes expanded: 10
search depth: 3
CourseNana.COM

max search depth: 4 running time: 0.00188088 max ram usage: 0.07812500 CourseNana.COM

Example 2: Depth-First Search CourseNana.COM

Suppose the program is executed for depth-first search as follows: CourseNana.COM

$ python3 puzzle.py dfs 1,2,5,3,4,0,6,7,8 CourseNana.COM

This should result in the solution path: CourseNana.COM

The output file will contain exactly the following lines: CourseNana.COM

path to goal: [‘Up’, ‘Left’, ‘Left’] cost of path: 3
nodes expanded: 181437
search depth: 3
CourseNana.COM

max search depth: 66125 running time: 5.01608433 max ram usage: 4.23940217 CourseNana.COM

More test cases are provided in the FAQs. CourseNana.COM

Note on Correctness CourseNana.COM

All variables, except running time and max 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. CourseNana.COM

CourseNana.COM

As running time and max 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. Use the following piece of code to calculate max ram usage: CourseNana.COM

import resource
dfs start ram = resource.getrusage(resource.RUSAGESELF).ru maxrss
dfs ram = ( resource . getrusage ( resource .RUSAGE SELF). ru maxrss
dfs start ram )/(2∗∗20) CourseNana.COM

Our grading script is working on a linux environment. For windows users, please change you max ram usage calcu- lation code so it is linux compatible during submission. You can test you code on linux platforrm using services such as Google Colab. CourseNana.COM


CourseNana.COM

V. Implementation and Testing CourseNana.COM

For your first programming project, we are providing hints and explicit instructions. Before posting a question on the discussion board, make sure your question is not already answered here or in the FAQs. CourseNana.COM

1. Implementation CourseNana.COM

You will implement the following three algorithms as demonstrated in lecture. In particular: CourseNana.COM

  • Breadth-First Search. Use an explicit queue, as shown in lecture.
  • Depth-First Search. Use an explicit stack, as shown in lecture.
  • A-Star Search. Use a priority queue, as shown in lecture. For the choice of heuristic, use the Manhattan priority function; that is, the sum of the distances of the tiles from their goal positions. Note that the blanks space is not con-
    sidered an actual tile here.

2. Order of Visits CourseNana.COM

In this assignment, where an arbitrary choice must be made, we always visit child nodes in the “UDLR” order; that is, [‘Up’, ‘Down’, ‘Left’, ‘Right’] in that exact order. Specifically: CourseNana.COM

·       Breadth-First Search. Enqueue in UDLR order; de-queuing results in UDLR order. CourseNana.COM

·       Depth-First Search. Push onto the stack in reverse-UDLR order; popping off results in UDLR order. CourseNana.COM

·       A-Star Search. Since you are using a priority queue, what happens with duplicate keys? How do you ensure nodes are retrieved from the priority queue in the desired order? CourseNana.COM

3. Submission Test Cases CourseNana.COM

Run all three of your algorithms on the following test cases: CourseNana.COM

Test Case 1 CourseNana.COM

$python3 puzzle.py bfs 3,1,2,0,4,5,6,7,8 $python3 puzzle.py dfs 3,1,2,0,4,5,6,7,8 $python3 puzzle.py ast 3,1,2,0,4,5,6,7,8 CourseNana.COM

Test Case 2 CourseNana.COM

$python3 puzzle.py bfs 1,2,5,3,4,0,6,7,8 $python3 puzzle.py dfs 1,2,5,3,4,0,6,7,8 $python3 puzzle.py ast 1,2,5,3,4,0,6,7,8 CourseNana.COM

Make sure your code passes at least these test cases and follows our formatting exactly. The results of each test are assessed by 8 items: 7 are listed in Section IV. What Your Program Outputs. The last point is for code that executes and produces any output at all. Each item is worth 0.75 point. CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
US代写,Columbia University代写,COMS 4701代写,Artificial Intelligence代写,Search代写,Breadth-First Search代写,Depth-First Search代写,A-Star Search代写,BFS代写,DFS代写,A* Search代写,COMS4701代写,Python代写,US代编,Columbia University代编,COMS 4701代编,Artificial Intelligence代编,Search代编,Breadth-First Search代编,Depth-First Search代编,A-Star Search代编,BFS代编,DFS代编,A* Search代编,COMS4701代编,Python代编,US代考,Columbia University代考,COMS 4701代考,Artificial Intelligence代考,Search代考,Breadth-First Search代考,Depth-First Search代考,A-Star Search代考,BFS代考,DFS代考,A* Search代考,COMS4701代考,Python代考,UShelp,Columbia Universityhelp,COMS 4701help,Artificial Intelligencehelp,Searchhelp,Breadth-First Searchhelp,Depth-First Searchhelp,A-Star Searchhelp,BFShelp,DFShelp,A* Searchhelp,COMS4701help,Pythonhelp,US作业代写,Columbia University作业代写,COMS 4701作业代写,Artificial Intelligence作业代写,Search作业代写,Breadth-First Search作业代写,Depth-First Search作业代写,A-Star Search作业代写,BFS作业代写,DFS作业代写,A* Search作业代写,COMS4701作业代写,Python作业代写,US编程代写,Columbia University编程代写,COMS 4701编程代写,Artificial Intelligence编程代写,Search编程代写,Breadth-First Search编程代写,Depth-First Search编程代写,A-Star Search编程代写,BFS编程代写,DFS编程代写,A* Search编程代写,COMS4701编程代写,Python编程代写,USprogramming help,Columbia Universityprogramming help,COMS 4701programming help,Artificial Intelligenceprogramming help,Searchprogramming help,Breadth-First Searchprogramming help,Depth-First Searchprogramming help,A-Star Searchprogramming help,BFSprogramming help,DFSprogramming help,A* Searchprogramming help,COMS4701programming help,Pythonprogramming help,USassignment help,Columbia Universityassignment help,COMS 4701assignment help,Artificial Intelligenceassignment help,Searchassignment help,Breadth-First Searchassignment help,Depth-First Searchassignment help,A-Star Searchassignment help,BFSassignment help,DFSassignment help,A* Searchassignment help,COMS4701assignment help,Pythonassignment help,USsolution,Columbia Universitysolution,COMS 4701solution,Artificial Intelligencesolution,Searchsolution,Breadth-First Searchsolution,Depth-First Searchsolution,A-Star Searchsolution,BFSsolution,DFSsolution,A* Searchsolution,COMS4701solution,Pythonsolution,