## 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.

**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.

**Do not submit folders, or zip files, even if you think it will help.**

**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 **

**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).

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 **

**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 claried 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 datale 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:

*×*4, and optimal solutions at depth 4 or less.*×*4, and optimal solutions at depth 8 or less.*×*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.