CMPT 317
Fall 2020
Introduction to Artifificial Intelligence
计算机专业作业代写 You may discuss questions and problems with anyone, but the work you hand in for this assignment must be your own work.
Assignment 3
A* Search and Heuristics
Date Due: 2 October 2020, 11:59pm Total Marks: 15
General Instructions
- This assignment is individual work. You may discuss questions and problems with anyone, but the work you hand in for this assignment must be your own work.
- If you intend to use resources not supplied by the instructor, please request permission prior to starting. You should not use any resource that substantially evades the learning objectives for this assignment. You must provide an attribution for any external resource (library, API, etc) you use. If there’s any doubt, ask! No harm can come from asking, even if the answer is no.
- Each question indicates what the learning objective is, what to hand in, and how you’ll be evalu-ated.
- Do not submit folders, or zip files, even if you think it will help.
- Assignments must be submitted to Moodle.
Question 1 (15 points): 计算机专业作业代写
Purpose: To explore the effect of heuristics on A* search
AIMA Chapter(s): 3.5 – 3.6
For this question, you are provided with a code base that implements informed search in the context of the Kessel Run problem 1 . In particular, A* search is implemented. However, the provided implementation uses h(n) = 0 as its heuristic, eectively making it equivalent to simple Breadth-First-Search in this context.Your job is to devise two dierent heuristics to try to improve the performance of A* search on the Kessel Run problem. There are two parts to this task.
First, in a written document, describe the heuristics that you have devised in plain natural language. For each heuristic, you must also state whether the heuristic is admissible and provide a brief argument sup-porting your claim. This does not need to be at the level of a formal proof, but should be convincing and should demonstrate that you have thought critically about your chosen heuristics. 计算机专业作业代写
Second, implement your heuristics in the codebase, and then run the code and present the resulting per-formance data.
The codebase consists of multiple files, but the only one you should need to change is KesselRun.py. At the very bottom of this file are two Python classes: InformedProblemV1 and InformedProblemV2.Each of these contains a method called calc_h() which is where you will implement your heuristic. You may also need to examine other parts of KesselRun.py to see how the state is represented for the purpose of calculating h(n) for your heuristics (paricularly the constructor of the State class).
Employ your testing skills for this implementation! With search, there is a lot going on “under the hood.” De-vise simple problem state examples and make sure your heuristic calculation for each state is performing as expected. You don’t need to hand in this testing, but your results may be meaningless without it.Once you have implemented your heuristics, create tables of performance data as shown below. A top-level solver script is provided to you (tableKR.py). Run the script on all of the problem data files, using a time limit of 10 seconds. Include neatly formatted tables of this data in your written document.
What to Hand In
- Your document that includes a description of your heuristics along with an analysis of their admis-sibility, as well as your data tables for the results. You can use a plain text file, or you can submit a MSWord document, or PDF. Name your document a3q1 with an appropriate extension (e.g., txt, pdf,docx, etc).
- A file named a3q1_KesselRun.py containing the implementation of your heuristic. You do not need to hand in the other files in the codebase or the data files.
Be sure to include your name, NSID, student number, and course number at the top of each document or file. 计算机专业作业代写
1This problem was also used for a previous assignment. A review of the problem description follows if you need it.
Evaluation
- 2 marks: Your first heuristic is non-trivial and well-described
- 2 marks: Your analysis of the admissibility of your first heuristic is well-argued
- 2 marks: Your second heuristic is non-trivial and well-described
- 2 marks: Your analysis of the admissibility of your second heuristic is well-argued
- 2 marks: Your first heuristic is correctly implemented
- 2 marks: Your second heuristic is correctly implemented
- 3 marks: You included the five tables (one for each problem set) in a readable format.
Overview 计算机专业作业代写
The following is a description of the Kessel Run problem. The description is unchanged from Assignment 2, it is included here for convenience.
The Kessel Run Problem
Consider an 3 × 3 array of integers {0, · · · , 8} such as:
This is a kind of a puzzle, where we wish to allow rows to be shifted left or right, and columns to be shifted up or down. We will call these shifts unit rotations, for reasons that will be clari ed immediately.
A unit rotation is simply a shift in the contents of a row (or column) by one position. For example, we can rotate the row (0, 1, 2) one position to the right to get (2, 0, 1). Notice that the integer 2 that was on the end of the row moved to the front after the rotation to the right. Because the number 2 moved to the front of the row, we call it a rotation. Rotations of a row can be one position right, or one position left; rotations of a column can be one position up, or one position down. Because we only consider one position left, right,up, or down, we call it a unit rotation.
An example: suppose we start with the 3×3 array shown at the start of this section. Suppose we then perform two operations: first, shift row 0 left, then shift column 2 up. We should then end up with the following array:
Data Files 计算机专业作业代写
You will be given a series of data les representing Kessel Run problems. Each problem is on one line of the file. The exact details of the format will follow immediately, but basically, each problem will describe two arrays: a start state and an end state. Ultimately, our plan is to use search to gure out how many unit rotations it would take to turn the start state into the end state.
In the data file, the problem posed above will look like this:
The 0 on the left is the problem index. The index tells you nothing useful about the problem, but each index in a data le will be unique, and ordered in the data file. It’s just an identifier.
The next two numbers (3 and 3 in this case) give you m (the number of rows) and n (the number of columns) in the array for that problem.Finally, there will be two sets of m × n numbers. These represent the start and end array. Each array is linearized in row-major order, meaning the first n numbers form the first row of the array, the second n numbers form the second row, and so on. The two arrays are separated by an extra space in the files for human readability, but this isn’t important for reading them in a program. 计算机专业作业代写
There will be examples in which m ≠n, and there will be examples of varying difficulty in dierent data files.
Currently, the following data files are provided:
- a_easy.txt: a variety of sizes, with optimal solutions at depth 3.
- b_moderate.txt: problem instances are 4 × 4, and optimal solutions at depth 4 or less.
- c_hard.txt: problem instances are 4 × 4, and optimal solutions at depth 8 or less.
- d_veryhard.txt: problem instances are 5 × 5.
- e_puremadness.txt: problem instances are 5 × 5.
The file names are indicative of the average difficulty of problems in the files themselves. Here, the measure of difficulty is the expected depth of the optimal solution, but as the problems are randomly generated (by randomly choosing rotations for a given starting position), some problem instances may be less difficult than the average for the data set.
更多代写：国外网课代修 GRE保分价格 国际金融网课代上 计算机essay代写 管理学论文代写范文 统计学代考价格
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
