GitHub - kwjesse/TravelingSalesperson: This project implements a branch and bound algorithm to find solutions to the traveling salesperson problem (TSP) giving me exposure to NP-complete problems. The branch and bound algorithm finds a reduced cost matrix to determine the lower-bound and then performs a depth-first search which expands the most promising partial path first in order to identify a final solution quickly. A breadth-first search was not chosen because all possible paths must be explored before reaching a final solution resulting in a slow algorithm.

kwjesse / TravelingSalesperson Public

Notifications You must be signed in to change notification settings
Fork 0
Star 1

This project implements a branch and bound algorithm to find solutions to the traveling salesperson problem (TSP) giving me exposure to NP-complete problems. The branch and bound algorithm finds a reduced cost matrix to determine the lower-bound and then performs a depth-first search which expands the most promising partial path first in order t…

1 star 0 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
.gitignore		.gitignore
Proj5GUI.py		Proj5GUI.py
TSPClasses.py		TSPClasses.py
TSPReport-Wilsdon.pdf		TSPReport-Wilsdon.pdf
TSPSolver.py		TSPSolver.py
Table.PNG		Table.PNG
Table.xlsx		Table.xlsx
pseudocode.txt		pseudocode.txt
which_pyqt.py		which_pyqt.py