Young Wu's Homepage

Lecture Note

* Slides
Lecture 15: Slides, With Quiz
Lecture 16: Slides, With Quiz
Annotated Lecture 15 Section 1: Slides
Annotated Lecture 16 Section 1: Slides
Annotated Week 8 Section 2: Part I, Part II

* Websites
All Search: Link
Google Map: Link
Robot Arm: Link, Link 2
Sheep Game: Link
Sliding Puzzle: Link
Water Jugs: Link
Professor Jerry Zhu's Slides (with Proofs etc): Link

* YouTube Video
To be added.

Written (Math) Problems

Submit on Canvas: PDF
Submit to M9 due July 29.

Programming Problem

* Short Instruction
(1) Download 5 rectangular orthogonal mazes from Maze Generator based on your wisc ID:
Type in your ID:
The size of the maze is:
(2) Solve the maze using iterative deepening search and A* search.

* Files to submit
(1) maze1.png, maze2.png, ... etc images (2 is enough) of the mazes with solution highlighted.
(2) output.txt contains the numbers of steps required (number of vertices expanded, comma separated) for IDS and A*, followed by a comma and one sequence of charaters in the set LRUD representing Left, Right, Up, Down. There should be a total of 5 lines and each line contains a string as the solution to one maze. For example, for a 2 x 2 empty maze, the line should be "3, 2, DR" or "3, 2, RD".
(3) code.

* Things to try
(1) Try different ways to store the maze (in a matrix, a graph, or a tree).
(2) Try different heuristic functions (Manhatan distance, Euclidean distance, or Chebyshev distance).
(3) (Not required) Try to implement BFS, DFS, BDS, UCS and compare the number of steps required.
(4) You can use the following canvas to generate and check the solution image.
Input the maze size (height x width): x
Input the initial state (row, column in the maze): (, )
Input the sequence of steps (characters LRUD):

More (nonessential) details and hints: PDF.

Last Updated: July 22, 2019 at 2:02 AM