Traveling Salesperson Problem

1. Introduction

Traveling Salesperson Problem: TSP is a problem that tries to find a tour of minimum cost that visits every city once. In this visualization, it is assumed that the underlying graph is a complete graph with (near-)metric distance (meaning the distance function satisfies the triangle inequality) by taking the distance of two points and round it to the nearest integer.

2. Visualisasi

View the visualisation of TSP algorithm here.

Originally, all edges in the input graph are colored with the grey.

Throughout the visualization, traversed edge will be highlighted with orange.

3. Masukan

Terdapat dua metode berbeda untuk menggambar graf masukan:

  1. Gambar Graf: Anda dapat meletakkan beberapa titik dalam kotak gambar, tetapi anda tidak boleh menggambar edge agar properti (hampir) metrik dari graf terpenuhi. Setelah anda selesai menggambar titik-titik, seluruh edge akan digambar secara otomatis.
  2. Graf Contoh: Anda dapat memilih dari daftar graf yang ada.

4. Bruteforce

Bruteforce: It tries all (V-1)! permutation of vertices (not all V! since it does not matter where we start from). It enumerates all possibilities by doing a dfs search with parameters similar to those of Held-Karp algorithm, that is, the DFS search will return the value of the tour starting from current vertex to all vertices that we have not already visited.

Time complexity: O(V * (V - 1)!) = O(V!).

5. Pemrograman Dinamis

Dynamic Programming: It uses a widely known algorithm called Held-Karp. In this visualization, it is implemented as a DFS search that is the same with the bruteforce algorithm, but with memoization to cache the answers. This dramatically brings down the run time complexity to O(2^V * V^2).

Time complexity: O(2^V * V^2).

Note that for N = 10, this algorithm takes roughly ~(100 * 2^10) = 102K operations while the bruteforce algorithm takes roughly ~(10!) = 3628800 operations, around 30 times faster.

6. Penaksiran

Approximation: There are two approximation algorithms available, a 2-approximation algorithm and a 1.5-approximation algorithm that is also well known as Christofides Algorithm.