Masalah Salesman Keliling: Python, C++ Algoritma
Sarah Chen
Apa yang dimaksud dengan Traveling Salesman Problem (TSP)?
Traveling Salesman Problem (TSP) adalah masalah kombinatorik klasik dalam ilmu komputer teoretis. Soal tersebut meminta untuk mencari jalur terpendek dalam suatu graf dengan syarat mengunjungi semua node hanya satu kali dan kembali ke kota asal.
Rumusan masalah memberikan daftar kota beserta jarak antar kota.
Tujuan: Untuk memulai dari kota asal, kunjungi kota lain satu kali saja, dan kembali lagi ke kota asal. Target kami adalah menemukan jalur terpendek untuk menyelesaikan rute pulang pergi.
Contoh TSP
Di sini diberikan grafik dimana 1, 2, 3, dan 4 mewakili kota-kota, dan bobot yang terkait dengan setiap sisi mewakili jarak antara kota-kota tersebut.
Tujuannya adalah untuk menemukan jalur terpendek untuk tur yang dimulai dari kota asal, melintasi grafik hanya mengunjungi kota atau node lain satu kali, dan kembali ke kota asal.
Untuk grafik di atas, rute optimal adalah mengikuti jalur biaya minimum: 1-2-4-3-1. Dan rute terpendek ini akan memakan biaya 10+25+30+15 =80
Solusi Berbeda untuk Masalah Traveling Salesman
Travelling Salesman Problem (TSP) tergolong masalah NP-hard karena tidak memiliki algoritma waktu polinomial. Kompleksitasnya meningkat secara eksponensial seiring bertambahnya jumlah kota.
Ada beberapa cara untuk menyelesaikan masalah travelling salesman (sdt). Beberapa solusi populer adalah:
Pendekatan brute force adalah metode yang naif untuk memecahkan masalah penjual keliling. Dalam pendekatan ini, pertama-tama kita menghitung semua kemungkinan jalur dan kemudian membandingkannya. Banyaknya jalur pada suatu graf yang terdiri dari n kota adalah n! Secara komputasi, sangat mahal untuk menyelesaikan masalah travelling salesman dengan pendekatan brute force ini.
Metode cabang-dan-terikat: Masalah dipecah menjadi sub-masalah dalam pendekatan ini. Solusi dari masing-masing sub-masalah tersebut akan memberikan solusi optimal.
Tutorial ini akan mendemonstrasikan pendekatan pemrograman dinamis, versi rekursif dari metode cabang-dan-terikat, untuk memecahkan masalah travelling salesman.
Pemrograman dinamis adalah suatu metode untuk mencari solusi optimal dengan menganalisis semua rute yang mungkin. Ini adalah salah satu metode solusi tepat yang memecahkan masalah travelling salesman melalui biaya yang relatif lebih tinggi dibandingkan dengan metode serakah yang memberikan solusi mendekati optimal.
Kompleksitas komputasi dari pendekatan ini adalah PADA(N^2 * 2^N) yang dibahas kemudian dalam artikel ini.
Metode tetangga terdekat adalah pendekatan greedy berbasis heuristik di mana kita memilih simpul tetangga terdekat. Pendekatan ini secara komputasi lebih murah daripada pendekatan dinamis. Namun, pendekatan ini tidak menjamin solusi optimal. Metode ini digunakan untuk solusi yang mendekati optimal.
Algoritma Traveling Salesman Problem
Kami akan menggunakan pendekatan pemrograman dinamis untuk menyelesaikan Traveling Salesman Problem (TSP).
Sebelum memulai algoritme, mari kenali beberapa terminologi:
- Graf G=(V, E), yang merupakan himpunan titik dan sisi.
- V adalah himpunan simpul.
- E adalah himpunan sisi-sisinya.
- Simpul dihubungkan melalui tepian.
- Dist(i,j) menunjukkan jarak non-negatif antara dua simpul, i dan j.
Anggaplah S adalah himpunan bagian dari kota-kota dan termasuk dalam {1, 2, 3, …, n} dengan 1, 2, 3…n adalah kota-kotanya dan i, j adalah dua kota dalam himpunan bagian tersebut. Sekarang biaya(i, S, j) didefinisikan sedemikian rupa sebagai panjang jalur terpendek yang mengunjungi node di S, yang memiliki titik awal dan akhir masing-masing sebagai i dan j.
Misalnya, biaya (1, {2, 3, 4}, 1) menunjukkan panjang jalur terpendek dimana:
- Kota awal adalah 1
- Kota 2, 3, dan 4 hanya dikunjungi satu kali
- Titik akhirnya adalah 1
Algoritma pemrograman dinamis adalah:
- Tetapkan biaya(i, , i) = 0, artinya kita memulai dan mengakhiri di i, dan biayanya adalah 0.
- Kapan |S| > 1, kita definisikan cost(i, S, 1) = ∝ dimana i !=1 . Karena awalnya kita tidak mengetahui pasti biaya untuk mencapai kota i ke kota 1 melalui kota lain.
- Sekarang, kita harus mulai dari 1 dan menyelesaikan turnya. Kita perlu memilih kota berikutnya sedemikian rupa-
biaya(i, S, j)=biaya minimum (i, S−{i}, j)+dist(i,j) dengan i∈S dan i≠j
Untuk gambar yang diberikan, matriks ketetanggaan akan menjadi sebagai berikut:
| dist(i,j) | 1 | 2 | 3 | 4 |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
Mari kita lihat cara kerja algoritma kami:
Langkah 1) Kami sedang mempertimbangkan perjalanan kami mulai dari kota 1, mengunjungi kota lain satu kali dan kembali ke kota 1.
Langkah 2) S adalah himpunan bagian kota. Menurut algoritma kami, untuk semua |S| > 1, kami akan menetapkan jarak cost(i, S, 1) = ∝. Di sini cost(i, S, j) berarti kita mulai dari kota i, mengunjungi kota-kota S sekali, dan sekarang kita berada di kota j. Kami menetapkan biaya lintasan ini sebagai tak terhingga karena kami belum mengetahui jaraknya. Jadi, nilainya adalah sebagai berikut:
Biaya (2, {3, 4}, 1) = ∝ ; notasi tersebut menunjukkan bahwa kita mulai dari kota 2, melewati kota 3, 4, dan mencapai 1. Dan biaya jalurnya tidak terhingga. Demikian pula-
biaya(3, {2, 4}, 1) = ∝
biaya(4, {2, 3}, 1) = ∝
Langkah 3) Sekarang, untuk semua subset S, kita perlu menemukan yang berikut ini:
biaya(i, S, j)=biaya minimum (i, S−{i}, j)+dist(i,j), dimana j∈S dan i≠j
Itu berarti jalur biaya minimum untuk memulai dari i, melewati subkumpulan kota sebanyak satu kali, dan kembali ke kota j. Mengingat perjalanan dimulai dari kota 1, biaya jalur optimal adalah= biaya(1, {kota lain}, 1).
Mari cari tahu bagaimana kita bisa mencapainya:
Sekarang S = {1, 2, 3, 4}. Ada empat elemen. Jadi jumlah himpunan bagiannya adalah 2^4 atau 16. Himpunan bagian tersebut adalah-
1) |S| = Batal:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
Saat kita memulai dari 1, kita dapat membuang himpunan bagian yang mengandung kota 1.
Perhitungan algoritma:
1) |S| = :
biaya (2, Φ, 1) = dist(2, 1) = 10
biaya (3, Φ, 1) = dist(3, 1) = 15
biaya (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
biaya (2, {3}, 1) = dist(2, 3) + biaya (3, Φ, 1) = 35+15 = 50
biaya (2, {4}, 1) = dist(2, 4) + biaya (4, Φ, 1) = 25+20 = 45
biaya (3, {2}, 1) = dist(3, 2) + biaya (2, Φ, 1) = 35+10 = 45
biaya (3, {4}, 1) = dist(3, 4) + biaya (4, Φ, 1) = 30+20 = 50
biaya (4, {2}, 1) = dist(4, 2) + biaya (2, Φ, 1) = 25+10 = 35
biaya (4, {3}, 1) = dist(4, 3) + biaya (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
biaya (2, {3, 4}, 1) = min [ dist[2,3]+Biaya(3,{4},1) = 35+50 = 85,
dist[2,4]+Biaya(4,{3},1) = 25+45 = 70 ] = 70
biaya (3, {2, 4}, 1) = min [ dist[3,2]+Biaya(2,{4},1) = 35+45 = 80,
dist[3,4]+Biaya(4,{2},1) = 30+35 = 65 ] = 65
biaya (4, {2, 3}, 1) = min [ dist[4,2]+Biaya(2,{3},1) = 25+50 = 75
dist[4,3]+Biaya(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
biaya (1, {2, 3, 4}, 1) = min [ dist[1,2]+Biaya(2,{3,4},1) = 10+70 = 80
dist[1,3]+Biaya(3,{2,4},1) = 15+65 = 80
dist[1,4]+Biaya(4,{2,3},1) = 20+75 = 95 ] = 80
Jadi solusi optimalnya adalah 1-2-4-3-1
Kode semu
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, … , n} of size s
Cost (s, S, 1) = Infinity
for all i Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Implementasi di C/C++
Berikut implementasinya C++:
#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
int min_cost = MAX;
while(next_permutation(vertex.begin(), vertex.end()))
{
int current_cost = 0;
int j = s;
for (int i = 0; i < vertex.size(); i++) {
current_cost += graph[j][vertex[i]];
j = vertex[i];
}
current_cost += graph[j][s];
min_cost = min(min_cost, current_cost);
return min_cost;
}
}
int main()
{
int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };
int s = 0;
cout << tsp(graph, s) << endl;
return 0;
}
Keluaran:
80
Implementasi di Python
from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_cost = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
current_cost += graph[k][j]
k = j
current_cost += graph[k][s]
min_cost = min(min_cost, current_cost)
return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))
Keluaran:
80
Solusi Akademik untuk TSP
Ilmuwan komputer telah menghabiskan waktu bertahun-tahun mencari algoritma waktu polinomial yang lebih baik untuk Travelling Salesman Problem. Hingga saat ini, masalahnya masih NP-hard.
Meskipun beberapa solusi berikut diterbitkan dalam beberapa tahun terakhir yang telah mengurangi kompleksitas hingga tingkat tertentu:
- TSP simetris klasik diselesaikan dengan Metode Sufiks Nol.
- Algoritma Optimasi berbasis Biogeografi didasarkan pada strategi migrasi untuk menyelesaikan masalah optimasi yang dapat direncanakan sebagai TSP.
- Algoritma Evolusi Multi-Tujuan dirancang untuk menyelesaikan beberapa TSP berdasarkan NSGA-II.
- Sistem Multi-Agen menyelesaikan TSP di N kota dengan sumber daya tetap.
Penerapan Masalah Traveling Salesman
Traveling Salesman Problem (TSP) diterapkan di dunia nyata baik dalam bentuknya yang paling murni maupun yang dimodifikasi. Beberapa di antaranya adalah:
- Perencanaan, logistik, dan pembuatan microchip: Masalah penyisipan chip secara alami muncul di industri mikrochip. Masalah-masalah tersebut dapat direncanakan sebagai masalah travelling salesman.
- sekuensing DNA: Sedikit modifikasi pada masalah travelling salesman dapat digunakan dalam pengurutan DNA. Di sini, kota mewakili fragmen DNA, dan jarak mewakili ukuran kemiripan antara dua fragmen DNA.
- Astronomi: Travelling Salesman Problem diterapkan oleh para astronom untuk meminimalkan waktu yang dihabiskan untuk mengamati berbagai sumber.
- Masalah kontrol optimal: Perumusan Travelling Salesman Problem dapat diterapkan pada permasalahan pengendalian optimal. Mungkin ada beberapa kendala lain yang ditambahkan.
Analisis Kompleksitas TSP
- Kompleksitas Waktu: Ada total 2N submasalah untuk setiap node. Jadi jumlah total submasalahnya adalah N*2N. Masing-masing submasalah memerlukan waktu linier untuk menyelesaikannya. Jika node asal tidak ditentukan, kita harus menjalankan loop untuk N node.
Jadi total kompleksitas waktu untuk solusi optimal adalah Jumlah node * Jumlah submasalah * waktu untuk menyelesaikan setiap submasalah. Kompleksitas waktu dapat didefinisikan sebagai O(N2 * 2^N).
- Kompleksitas Ruang: Pendekatan pemrograman dinamis menggunakan memori untuk menyimpan C(S, i), dimana S adalah subset dari himpunan simpul. Totalnya ada 2N subset untuk setiap node. Jadi, kompleksitas ruangnya adalah O(2^N).
Selanjutnya, Anda akan mempelajari tentang Saringan Algoritma Eratosthenes
