ECE4010 Homework 1
Part I: Programming [75 points]
Visit the blackboard page and download the zip archive.
You need to have Python 3.6 or above installed on your machine
This assignment requires you to complete the implementations of
1. Class StackFrontier
2. Class QueueFrontier
3. solve function defined in Class Maze
Once you’ve complete all the required functions, should be able to run python maze.py
mazeN.txt, where N denote the index of maze in the folder.
For each maze, run your code based on DFS and BFS, respectively. And posted the solution
that is stored in maze.png.
Part II: Written Problem [25 points]
Q1. [5 pts] Between depth first search (DFS) and breadth first search (BFS), which will
find a shorter path through a maze?
Q2. [5pts] The following question will ask you about the below maze. Grey cells indicate
walls. A search algorithm was run on this maze, and found the yellow highlighted path
from point A to B. In doing so, the red highlighted cells were the states explored but that
did not lead to the goal.
Of the four search algorithms discussed in lecture — depth-first search, breadth-first
search, greedy best-first search with Manhattan distance heuristic, and A* search with
Manhattan distance heuristic — which one (or multiple, if multiple are possible) could be
the algorithm used?
Q3. [5 pts] Why is depth-limited minimax sometimes preferable to minimax without a
depth limit?
Q4. [10 pts] The following question will ask you about the Minimax tree below, where the
green up arrows indicate the MAX player and red down arrows indicate the MIN player.
The leaf nodes are each labelled with their value.
a. [5 pts] What are the value of the nodes in the above figure, if we use Minimax?
b. [5 pts] If you are the MAX player, what is your best action (left, middle, or right)
請加QQ：99515681 或郵箱：99515681@qq.com WX：codehelp
