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 exactly 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 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: Mencoba seluruh permutasi yang ada (V-1)! dari semua simpul (tidak semua V! karena tidak peduli di mana kita mulai). Algoritma ini akan mencoba seluruh kemungkinan yang ada dengan pencarian DFS yang mirip dengan algoritma Held-Karp, di mana pencarian DFS akan menghasilkan ongkos dari tour yang berasal dari simpul saat ini ke semua simpul yang belum dikunjungi.

Kompleksitas waktu: O(V * (V - 1)!) = O(V!)

5. Pemrograman Dinamis

Pemrograman Dinamis: Menggunakan algoritma Held-Karp yang terkenal. Dalam visualisasi ini, algoritma tersebut diimplementasikan sebagai pencarian DFS yang sama dengan algoritma bruteforce, namun dengan memoization untuk menyimpan jawaban-jawaban yang ada. Perlu dicatat bahwa algoritma ini dapat berjalan dengan lebih efisien dengan kompleksitas O(2^V * V^2).

Kompleksitas waktu: O(2^V * V^2).

Untuk N = 10, algoritma ini memerlukan sekitar ~(100 * 2 ^ 10) = 102K operasi, sementara algoritma bruteforce memerlukan sekitar ~(10!) = 3268800 operasi, sekitar 30 kali lebih cepat.

6. Penaksiran

Approximation: Terdapat dua algoritma penaksiran untuk TSP, sebuah algoritma 2-approximation dan 1.5-approximation yang dikenal dengan nama algoritma Christofides.