通过DFS算法，求解Maze的最短路径问题。
Problem Description
In this assignment, you are asked to find the shortest path to solve the maze problem. A maze generator written in Python, which can be found on Moodle, is provided for creating solvable m x n 2-dimensional mazes. The entry and exit locations of the maze are set at the cells at (0,0), i.e., top left corner, and (m-1, n-1), i.e., bottom right corner, respectively.
The maze generator uses the Cell and Maze classes to accomplish its tasks. Each cell has up to 4 connecting neighbors at the east, south, west, and north directions. Some cells have less than 4 neighbors. For example, the cell at (0, m-1) has neighbors at its south (1, m-1) and (0, m-2) west only. Absence of neighbor at a particular direction is represented by None. Such information is stored in a 4-element list called neighbor in each instance the Cell class. Whether there is a passage between two neighboring cells is recorded in another list of Boolean values called wall.
Each instance of Maze is composed of m x n instances of Cell in terms of a list of rows of instances of Cell, i.e., a list of lists. The generate() method is used internally by the Maze constructor when a Maze instance is created. The method uses a depth-first search to generate a solvable maze. Additional code is included in the method to ensure each cell in the maze is at least connected to one neighboring cell. A __str__() method is provided for displaying a maze graphically.
Assignment Requirements
Students are required to develop a Python program to find the shortest path that connects the start cell at (0,0) and goal cell at (m-1, n-1) of the maze using the breadth-first search and the A* algorithms. The solvers may be implemented as methods of the Maze class or in whatever ways a student thinks appropriate. The two search algorithms to be implemented must use the Maze and Cell classes. Students must NOT convert the maze data into other maze representations. Special purpose Python modules such as NumPy and NetworkX are not allowed to be used. The quality of the shortest path found by the two algorithms in terms of the path length (which should be the same), the number of moves that each search algorithm has taken, the average runtime required by each of the algorithms for solving 50 problem instances of 20x20 mazes should be discussed. Students also need to find out the average runtime required by two algorithms for solving 50 instances of 8x8, 10x10, and 15x15 mazes, then discuss the observed results in light of the theoretical worst-case time complexity of the two algorithms found in books or on the Internet.
The main body of the report is limited to 8 pages which should describe the program design with program fragments and relevant description, test results (with the details given in an appendix if needed), and the algorithms’ run-time behaviors. An illustration the proper working of the algorithm, and a full listing of program code must be included in an appendix.
Submission Requirements
Submit the above-mentioned report and Python program (in .ipynb or .py extension with brief comments), to Moodle.
Weighting and Assessment Criteria
Grading will be based on solution correctness and completeness, and efficiency of the submitted solution including choice of appropriate data structures, as well as the quality of the documentation.