CPSC5610代做、data代写、代做Python程序语言、代写Python

日期：2020-10-06 10:57

CPSC5610 – Artificial Intelligence

Assignment 1: Problem Solving by State-Space Search

Goals for this assignment

1. Understand the components of a search-based problem solver and see several

implementations

2. Apply concepts of state-space search to several different problems

3. Understand the power of heuristics applied to state-space search problems

Problem 1: PacMan Search Agent

You will work on the Search Agent problems in the Berkeley AI Pacman projects. The page for that

problem is here.

You will complete questions Q1 through Q7.

Problem 2: Pancake Sort

Pancake sort is a sorting algorithm that is especially popular in job interviews because it's simple, and

most of the time candidates have not studied it an algorithms class.

A "flip" of an arry works as follows: if you flip array A at index i

? The elements with an index of 0 to i are reversed

? The elements with an index i+1 or greater are not changed

For example

flip([3, 1, 4, 5, 2], 2) => [4, 1, 3, 5, 2]

flip([3, 1, 4, 5, 2], 0) => [3, 1, 4, 5, 2]

flip([3, 1, 4, 5, 2], 4) => [2, 5, 4, 1, 3]

The pancake sort problem is: take as input an array of elements – assume integers for this assignment,

and return a sequence of flip operations that, when applied to the input array, results in an array that is

in sorted order.

For example

Begin [3, 1, 4, 5, 2]

flip_1 [1, 3, 4, 5, 2]

flip_3 [5, 4, 3, 1, 2]

flip_4 [2, 1, 3, 4, 5]

flip_1 [1, 2, 3, 4, 5]

You will start with the search framework we developed in class. You must use this framework for your

solution. After that you may only add a new

? World state definition class

? Problem definition class

? Evaluation instance (if you implement a heuristic)

You will develop a function solvePancakeSort that takes a list of integers as input, and returns a list

of strings, each one describing a "flip move." In addition your function will return the same stats tuple

returned by aStarSearch. Here is an example of the mapping from input list to output solution.

[3, 1, 4, 5, 2]) => ["flip_1", "flip_3", "flip_4", "flip_1"]

For extra credit, see how much you can improve the performance using heuristics. Look at this paper,

and see whether you can implement its heuristic and how well the heuristic does. I will give up to 5

points extra credit for heuristics that are empirically better than uninformed search (i.e. you have to

demonstrate that your heuristic outperforms DFS and BFS.

Work on a heuristic is worth a maximum of 5 points, but your total score on the assignment cannot

exceed 100 points.

The notebook pancakeSearch.ipynb provides additional detail, and a template for handing in your

work.

Problem 3: Solving the Strimko Puzzle Using Search

Strimko is a number game like Sudoko in that one starts with a game board partially filled with numbers;

to solve the game, numbers are assigned to empty cells. Notice in this example, the board has four

rows, four columns, and four "chains" or "streams," which are connected sequences of cells. The term

"chain" and "stream" are interchangeable – different sources use these two terms to mean the same

thing.

Rows, columns and chains all have the same length (for example 4 for a 4x4 game) and every cell

appears in exactly one chain. To solve the puzzle, assign a number to every cell so that the numbers in

each row, column, and chain are distinct. The left figure is a valid initial board, the right figure is a

solved board. Ignore the R1 and C1 labels to the sides.

You will start with the generic search framework we used in the Search Lab, and build a problem solver

for Strimko using the state-space search implementation.

Here are some requirements about how we will represent the game.

A Strimko problem has two components: the initial board, and the chains.

For a problem of size n, the initial board will be represented by a Python nested list: it will be a list of n

elements, each of which is a list of n elements. Zero will be used to denote empty cells. For the

example above, the initial game board would be represented like this:

[[0,0,0,1], [0,0,2,0], [0,4,0,0], [0,0,0,0]]

The chains will be represented by a list of length n, each element of which is a list of length n of 2-tuples,

each representing a coordinate pair. A coordinate pair is (row, column) and 0-based. The chains for the

example board above would be:

[[(0,0), (1,1), (2,0), (0,2)],

[(1,0), (0,1), (1,2), (0,3)],

[(3,0), (2,1), (3,2), (2,3)],

[(3,1), (2,2), (1,3), (3,3)]]

The order in which coordinates appear in the chains is not significant.

You will develop a function solveStrimko that takes as input two required arguments, an initial board

and chains respectively, and returns a solution game board if one exists, or None otherwise. In addition

your function will return the same stats tuple returned by aStarSearch.

Notice that the A-star search function returns a list of "actions," but your solveStrimko function must

return a game board. You must write the code to convert a list of actions to a game board.

You may assume that the initial board and chains are legal in the sense that the chains and initial

assignment of values obey the rules

Heuristic – Extra Credit

You can receive up to 5 points for this section, but not to exceed 100 points for the assignment.

Develop a heuristic that should guide the A-Star search algorithm to a solution quickly. The point of this

part is just to get you to formulate some heuristic, and implement it within the search framework. The

heuristic can be simple, and it might not work any better than an informed strategy. (Sometimes they

just don't, and that's the way it goes.) Document your solution as follows:

? What is the idea behind your heuristic

? How did you implement it

? How did it run compared to the best uninformed algorithm

The notebook strimko.ipynb provides additional detail, and a template for handing in your work.

Handin Details

Please hand in the following (online Canvas submission)

? A single Zip archive, containing five files. The files are

o search.py, searchAgents.py (for the Pacman problems)

o pancakeSearch.ipynb (for the Strimko problem)

o strimko.ipynb (for the Strimko problem)

o Retrospective.pdf

? Your Retrospective.pdf file must contain the following material

o Your name

o For each of the three questions

? Is your solution fully working or not?

? Was there anything particularly noteworthy or challenging about the

question

o How much time did you spend on the assignment overall?

o Overall how would you evaluate the homework in terms of understanding and

applying concepts discussed in class