Skip to content

Competitive C++ solution to the Travelling Salesperson 2D problem, that includes the implementation of 6 algorithms: greedy, Clarke-Wright, Christofides, 2-opt, 3-opt, and Lin-Kernighan (k-opt). Done as part of the project assignment in the *DD22440 Advanced Algorithms* course at KTH, by Prof. Danupon Nanongkai.

Notifications You must be signed in to change notification settings

istresec/kth-aa

Repository files navigation

Travelling Salesperson 2D

Ivan Stresec*, Frano Rajič*

Project report | Problem definition

Codebase contains a competitive C++ solution with 6 algorithms implemented: greedy, Clarke-Wright, Christofides, 2-opt, 3-opt, and Lin-Kernighan (k-opt). Solved as part of the project assignment in the DD22440 Advanced Algorithms course at KTH, by Prof. Danupon Nanongkai.

Problem from kth.kattis.com: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Getting started

Consult the CMakeLists.txt file as well as the src/main.cpp, to get started.

About

Competitive C++ solution to the Travelling Salesperson 2D problem, that includes the implementation of 6 algorithms: greedy, Clarke-Wright, Christofides, 2-opt, 3-opt, and Lin-Kernighan (k-opt). Done as part of the project assignment in the *DD22440 Advanced Algorithms* course at KTH, by Prof. Danupon Nanongkai.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published