CONTINUOUS ASSESSMENT – MAZE
This CA is worth 30% of your overall module mark.
Submission deadline is 29th April 2022.
PROBLEM DESCRIPTION:
Copyright By PowCoder代写 加微信 powcoder
You task is to implement in Prolog, and evaluate, three different search algorithms for
finding a path in a maze. The algorithms you are asked to implement are:
Depth-first OR breath-first search
Iterative-deepening search
A* – you have to decide on a suitable heuristic for A*
You are allowed to use and modify the code from the labs.
A sample maze is shown in Figure 1: some squares are
free to move to (white), others are blocked with a wall
(black), so you have to walk around them. From the
current square you can move left, right, up and down (no
movement on diagonal).
You don’t have to print the maze in Prolog, it’s sufficient
to print the list of moves from START to GOAL, e.g.
Figure 1 Sample maze.
[(3,3), (3,2), (4,2), (5,2), (5,3), (5,4), (5,5), (4,5), (3,5), (2,5), (1,5)]
where the bottom left corner of the maze is (1,1), top left is (1,5), bottom right is (5,1)
and top right is (5,5), the start point is (3,3) and the goal is (1,5).
You should be able to run your algorithm for different start and goal positions.
In addition to your Prolog code you should also submit a short document briefly
discussing your representation of the maze and any design decisions taken (e.g. do
you specify for each square is it empty or it contains a wall, or do record the walls only
and if a square doesn’t contain a wall it is therefore empty). In your documentation
discuss the solutions for each algorithm when applied to two mazes (you can use the
two sample ones included in this document, or you can use another maze that may
illustrate your points better). Also include an illustration of the path the algorithm
followed through the maze to the goal. Discuss the performance of the different
algorithms.
You should write your code to be as flexible as possible and to work for a new maze
setup with minimal changes.
SUBMISSION:
Deadline for submissions 29th April 2022. Marks will be deducted for late submissions.
Submit your assignment through Brightspace, and include your Prolog code and the
document describing how you approached the problem and what your findings are
PLAGIARISM:
Plagiarism is a serious offence – do not use other people’s code, as well as do not
share your files with others and do not share them online (e.g. public github)!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com