Lecturer Name: David McQuaid
Student Name: Marcos Vinicius de Oliveira
Student Number: 2023323
- Answer question 1 and 2
- All answers in a Jupyter notebook
- Written answers and diagrams in Mark-up
- Runnable code
- References in HARVARD Style
- Name it as
Marcos Vinicius de Oliveira_AI_CA2.ipynb - Upload a CCT Assessment Cover Page
A puzzle has multiple ways of reaching the end solution. Fig. 1 shows a graph that represents all possible routes to the solution. The starting point of the game is represented by A, the solution is represented by S. The other points in the graph are possible intermediary stages.
A. The graph in Fig. 1 is a visualisation of the problem.
- (i) Identify the differences between a graph and a tree.
- (ii) Explain in detail how the graph is an abstraction of the problem.
- (iii) Identify the advantages of using a visualisation such as the one shown in Fig. 1.
B. Demonstrate how Dijkstra’s algorithm would find the shortest path to the solution in Fig.1 through diagrams and written explanation of each stage.
The creator of the puzzle has been told that the A* algorithm is more efficient at finding the shortest path because it uses heuristics. Compare the performance of Dijkstra’s algorithm and the A* search algorithm, referring to heuristics, to find the shortest path to the problem by implementing both algorithms programmatically and comparing the solutions generated in Mark-down. Refer to the complexity of the algorithms and compare the actual time it takes for the solutions to be processed.
The answers to question 1 and 2 is into the archive called Marcos Vinicius de Oliveira_AI_CA2.ipynb and uploaded on Moodle.
Belwariar, R. (2018). A* Search Algorithm - GeeksforGeeks. [online] GeeksforGeeks. Available at: https://www.geeksforgeeks.org/a-search-algorithm [Accessed 28 Oct. 2023].
Development Team, M. (2023). Gallery - Matplotlib 3.4.2 Documentation. [online] matplotlib.org. Available at: https://matplotlib.org/stable/gallery/index.html [Accessed 12 Nov. 2023].
Navone, E.C. (2020). Dijkstra’s Shortest Path Algorithm - a Detailed and Visual Introduction. [online] freeCodeCamp.org. Available at: https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/ [Accessed 26 Oct. 2023].
Vaghani, R. (2019). Difference between Graph and Tree. [online] GeeksforGeeks. Available at: https://www.geeksforgeeks.org/difference-between-graph-and-tree/ [Accessed 25 Oct. 2023].
Please note that this project is part of CCT College, however, it may contain some part of the code that may be copyrighted, if so, please contact me so I can delete or give due to copyright. All references about this project are in the "References" section above.
Please note this project is non-profit and not intended to be monetized.
Built with 💙 by 2023323@Marcos Oliveira