Traveling Salesperson Problem

1. Introduction

Traveling Salesperson Problem: TSP adalah masalah di mana kita mencari tour dengan ongkos minimum yang mengunjungi tiap 'kota' sekali. Dalam visualisasi ini, graf yang mendasarinya diasumsikan sebagai graf komplet dengan jarak yang (hampir) metrik (di mana jaraknya memenuhi pertidaksamaan segitiga) dengan mengambil jarak antara dua titik dan membulatkannya ke bilangan bulat terdekat.

2. Visualisasi

Lihat visualisasi algoritma TSP di sini.

Pada awalnya, semua sisi dalam graf masukan diberi warna abu-abu.

Selama visualisasi, sisi yang dikunjungi akan diberi warna oranye.


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.