代写CMPT 310、代写Python语言编程

日期：2022-10-09 08:27

Assignment 1

Instructions:

● You can do this assignment individually or in a team of two. If you are doing it in a

group, only one submission per group is required. Self enrolled groups are available

on canvas.

● You may submit multiple times until the deadline. Grade penalties will be

imposed for late submissions (see the course outline for the details).

● Always plan before coding.

● For coding questions - Use function-level and inline comments throughout your

code. We will not be specifically grading documentation. However, remember that

you will not be able to comment on your code unless sufficiently documented. Take

the time to document your code as you develop it properly.

● We will carefully analyze the code submitted to look for plagiarism signs,

so please do not do it! If you are unsure about what is allowed, please talk

to an instructor or a TA.

● Make sure that in your answers, you clearly indicate the exact section you are

answering.

● You will submit one .zip file.

o For theoretical questions - Your submission must be formatted as a single

PDF file; other types of submissions (non-pdf, multiple files, etc.) will not be

graded. Your name(s) and student number(s) must appear at the top of the

first page of your submission.

o Please put all your files (pdf + code) in one folder. Compress these into a

single archive named a1.zip and submit it on Canvas before the due date

listed there.

Question 1 [25 marks]: Search Algorithms

Consider the problem of finding the shortest path from a1 to a10 in the following directed

graph. The edges are labelled with their costs. The nodes are labelled with their heuristic

values. Expand neighbours of a node in alphabetical order, and break ties in alphabetical

order as well. For example, suppose you are running an algorithm that does not consider

costs, and you expand a; you will add the paths <a,b> and <a,e> to the frontier in such a

way that <a,b> is expanded before <a,e>.

Figure 1: Graph

Note: You may need more rows than given in the table.

(a) [4 marks] Use breadth-first search to find the shortest path from a1 to a10, show all

paths explored for each step.

Node

explored

path

(b) [6 marks] Use lowest-cost-first search to find the shortest path from a1 to a10, show all

paths explored, and their costs, for each step.

Node

explored

Cost Path

(c) [12 marks] Use A* search to find the shortest path from a1 to a10, show all paths

explored, and their values of f(n), for each step.

(Note that f(n) = g(n) + h(n), where g(n) is the cost of the path from the start node to the

current node n, h(n) is the heuristic value of the current node n)

Iteration Node(s) Actual path

cost

Heuristic

cost

Total cost Path(s)

(d) [3 marks] Out of BFS, LCFS, A*, which search algorithm do you think is most efficient

for the above example? Justify your reasoning.

Question 2: [25 marks] Game

For this activity, you are going to play the Seashell game. The dots are closed seashells.

The rules of the game are to use the seashells to jump over other seashells like in checkers,

which in turn will open the seashell that has been jumped over. The seashells can also be

moved into the empty spot adjacent to it but will not open any shells. The goal is to do this

for all the seashells to win the game.

You can play the game here: https://www.novelgames.com/en/seashell/

Fig 2. Seashell board

Now, you are going to represent seashells as a search problem. (Use the labels provided in

Fig 2 for referring to spaces on the board).

(a) [4 points] How would you represent a node/state?

(b) [2 points] In your representation, what is the goal node?

(c) [3 points] How would you represent the arcs?

(d) [3 points] How many possible board states are there? Note: this is not the same as

the number of “valid” or “reachable” game states, which is a much more

challenging problem.

(e) [6 marks] Write out the first three levels (counting the root as level 1) of the search

tree based on the labels in Figure 3. (Only label the arcs; labelling the nodes would

be too much work).

(f) [3 marks]What kind of search algorithm would you use for this problem? Justify

your answer.

(g) [4 marks] Would you use cycle-checking? Justify your answer.

Ques 3. [25 marks] Programming 1

For this question, you get a chance to play with some heuristics. We have provided you

with the code needed for this activity. There are two files:

- search.py

- Util.py

These files are available on canvas. Go through the code and understand it, including

the Problem class that it inherits from.

In search.py, we have added a new StagePuzzle class, which is a modified version of the

EightPuzzle class. We call our modified puzzle as StagePuzzle since our puzzle is like a

champion stage, as shown below.

StagePuzzle

The desired final state of our puzzle is as follows:

StagePuzzle Final State

(a) [5 marks] Write a function called make_rand_StagePuzzle() that returns a new instance

of a StagePuzzle problem with a random initial state that is solvable. Note

that StagePuzzle has a method called check_solvability that you should use to help ensure

your initial state is solvable.

(b) [5 marks] Write a function called display(state) that takes a StagePuzzle state (i.e. a

tuple that is a permutation of (0, 1, 2, …, 9)) as input and prints a neat and readable

representation of it. 0 is blank and should be printed as a * character.

For example, if state is (0, 3, 2, 1, 8, 7, 4, 6, 5, 9), then display(state) should print:

* 3

2 1 8 7

4 6 5 9

(c) [15 marks] Create 8 (more would be better!) random StagePuzzle instances (using your

code from above) and solve each of them using the algorithms below. Each algorithm

should be run on the exact same set of problems to make the comparison fair.

For each solved problem, record:

● the total running time in seconds

● the length (i.e. number of tiles moved) of the solution

● that total number of nodes that were removed from the frontier

You will probably need to modify the A* function named “astar_search” in the provided

code to get all this data.

Note:

● The time it takes to solve random StagePuzzle instances can vary from less than a

second to hundreds of seconds. So solving all these problems might take some time!

● The result function in StagePuzzle class does not necessarily check the requested

action’s feasibly before doing it. It is your responsibility to check the actions

feasibilities before doing them. You can also edit the StagePuzzle class and add new

functions if you need them.

● Make sure to add the comments in the code.

The algorithms you should test are:

● A*search using the misplaced tile heuristic (this is the default heuristic in the

StagePuzzle class)

● A* search using the Manhattan distance heuristic. Please implement your version of

the Manhattan heuristic.

o Be careful: there is an incorrect Manhattan distance function in

tests/test_search.py. So, don’t use that!

● A*search using the max of the misplaced tile heuristic and the Manhattan distance

heuristic

Summarize all your results in a single table for comparing the three heuristic functions

you used. Based on your data, which algorithm is the best? Explain how you came to you

conclusion.

Total running

time

Solution

length

Removed frontier

nodes

Misplaced tile heuristic

Manhattan distance

heuristic

Max of two heuristics

Below is a sample solution:

Your observations < >

Hints

● When you are testing your code, you might want to use a few hard-coded problems

that don't take too long to solve. Otherwise, you may spend a lot of time waiting

for tests to finish!

- One easy way to time code is to use Python's standard ``time.time()` function, e.g.::

import time

def f():

start_time = time.time()

# ... do something ...

elapsed_time = time.time() - start_time

print(f'elapsed time (in seconds): {elapsed_time}s')

Python has other ways to do timing, e.g. check out the ``timeit`` module.

Question 4: [25 marks] Programming II - You can do (a) in any programming language.

TAs would be able to help you with python only.

(a) [20 marks] In this problem, you need to input a 2*2 rubik’s cube and solve it using

A* searching algorithm. The transition between the states is the same as real moves

on a rubik’s cube (ie. in each step, one of the facets can be turned clockwise or

counterclockwise and there are 12 choices in total). Consider the cube as the

following image.

The colors are numbered as Orange=1, Green=2, White=3, Blue=4, Red=5, and Yellow=6.

You input the facets of the initial state of the cube with the following order:

For example, the input for the above state is:

4 4 2 2

1 3 5 6

1 1 5 5

6 3 6 3

4 2 2 4

3 1 6 5

You need to output the moves by specifying the number of the facet and its direction (ie.

clockwise vs counterclockwise). For example:

Turn Facet#1 Clockwise

Turn Facet#2 Counterclockwise

…

After finding the solution, you should also print the number of explored nodes and depth

of the found goal node. Use the following heuristic function for the A* algorithm.

h(n) = 4 * (number of facets with 4 different colors)

+ 2 * (number of facets with 3 different colors)

+ number of facets with 2 different colors

For instance, the value of the heuristic function for the previous example is 12.

Below is a sample output:

(b) [5 marks] Do you think that the solutions found by this algorithm are always

optimal? why?

Note:

For specific help related to Python - Drop-in TAs programming OH.