Qumeric / tsp-suboptimal Public

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

Implementation of some simple TSP solvers (nearest neighbor, ant algortihm, n! bruteforce, annealing imitation, 2.0-optimal, branch and bound (broken ATM))

CC0-1.0 license

1 star 1 fork Branches Tags Activity

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 11 Commits
include		include
src		src
test		test
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
LICENSE		LICENSE
README.md		README.md
diff_ev.py		diff_ev.py
draw.py		draw.py

Repository files navigation

Travelling Salesman Problem Solvers

Implementation of several algorithms for TSP, namely:

Simple bruteforce
Branch and bound
Ant algorithm
Simulated annealing
Closest neighbour (O(n^2) and O(n^3) variants)
2-OPT solution (euler cycle on MST)
Christofides algorithm

Todo

Add unit tests
Publish quality/speed analysis

Ideas

Grouping (just like sqrt-decomposition (https://habrahabr.ru/post/151151)
Greedy approximation
Elite ants

About

Implementation of some simple TSP solvers (nearest neighbor, ant algortihm, n! bruteforce, annealing imitation, 2.0-optimal, branch and bound (broken ATM))

CC0-1.0 license

Report repository

Releases

No releases published

Packages

No packages published

Languages