The project aims to create visual outputs for popular graph algorithms like DFS,BFS and NP-HARD problems like Travelling Salesman Problem and Graph colouring problems using NetworkX graph library of Python. It is not just limited to getting a visual output, but the algorithms will be optimised to its best by using heuristics for non-polynomial time algorithms. The project aims to create a better understanding of the working of the algorithms, in-depth understanding of the application of heuristics to improve the computation time and usage of the later to our advantage in optimising the algorithm. It could be used by analysts as well as students and teachers, as a teaching aid. It could definitely serve all the applications of Np-hard problems like- School scheduling, Tourist Itineraries, etc.
DFS,BFS and NP-Hard algorithms have been there for years now and it has been coded out in every programming language as well. This project aims in visulization of them, to create a better understanding. Solving most of the above mentioned algorithm using brute force-technique might give the optimal solution, however, as the problem size increases, the search for an optimal solution will no longer be worth the effort. Hence, by involving heuristics, we aim to improve the time complexity while arriving at a good solution( need not be optimal always). (Heuristics is used, to predict how close the end of path is to a solution, so that the paths which are judged to be closer to a solution are extended first.)
It includes: