辅导CMPT 310、辅导Python语言编程

日期：2022-10-10 07:25

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 and to the frontier in such a
way that is expanded before .
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.