Masalah Salesman Keliling: Python, C++ Algoritma

Apa yang dimaksud dengan Traveling Salesman Problem (TSP)?

Masalah Penjual Keliling (Travelling Salesman Problem/TSP) adalah masalah optimasi kombinatorial klasik dalam ilmu komputer teoretis. Diberikan sebuah graf kota, TSP menanyakan jalur terpendek yang mengunjungi setiap simpul tepat sekali dan kembali ke kota asal.

Pernyataan masalah tersebut memberikan daftar kota beserta jarak antara setiap pasangan kota.

Tujuan: Mulailah dari kota asal, kunjungi setiap kota lain tepat satu kali, dan kembali ke kota awal. Tujuannya adalah menemukan rute pulang pergi terpendek.

Contoh TSP

Perhatikan grafik di bawah ini di mana 1, 2, 3, dan 4 mewakili kota-kota, dan bobot pada setiap sisi mewakili jarak antara kota-kota tersebut.

Tujuannya adalah untuk menemukan rute terpendek yang dimulai dari kota asal, mengunjungi setiap kota lain tepat satu kali, dan kembali ke kota asal.

Untuk grafik di atas, rute optimalnya adalah 1-2-4-3-1Biaya tur terpendek adalah 10 + 25 + 30 + 15 = 80.

Solusi Berbeda untuk Masalah Traveling Salesman

Masalah Penjual Keliling (Travelling Salesman Problem) diklasifikasikan sebagai NP-hard karena tidak ada algoritma waktu polinomial yang diketahui dapat menyelesaikannya secara tepat. Kompleksitasnya meningkat secara eksponensial dengan jumlah kota.

Ada beberapa cara untuk menyerang TSP. Pendekatan yang paling umum adalah:

Pendekatan Brute Force: Metode sederhana menghitung setiap kemungkinan rute dan membandingkannya. Jumlah rute dalam grafik dengan n kota adalah n!, yang membuat metode brute force menjadi sangat mahal secara komputasi untuk wilayah yang lebih besar dari sekitar sepuluh kota.

Metode Branch and Bound: Masalah tersebut dipecah menjadi sub-masalah, dan solusi dari sub-masalah tersebut digabungkan menjadi solusi optimal. Pemangkasan yang efektif akan membuang rute parsial yang tidak dapat mengalahkan biaya terbaik saat ini.

Tutorial ini mendemonstrasikan pendekatan pemrograman dinamis, yang merupakan versi memoisasi dari branch and bound dan sesuai dengan algoritma Bellman-Held-Karp.

Pemrograman Dinamis: Ini adalah metode tepat yang mencari solusi optimal dengan menggunakan kembali tumpang tindih.ping Hasil submasalah. Ini lebih lambat daripada yang mendekati optimal. metode serakah, namun selalu menghasilkan rute yang optimal secara global.

Kompleksitas komputasi dari pendekatan ini adalah O(N² × 2^N), yang akan kita bahas lebih lanjut di artikel ini.

Metode Tetangga Terdekat: Pendekatan heuristik serakah yang selalu melompat ke kota terdekat yang belum dikunjungi. Pendekatan ini jauh lebih murah daripada pemrograman dinamis tetapi tidak menjamin rute optimal, sehingga digunakan untuk solusi yang mendekati optimal ketika kecepatan lebih penting daripada minimum yang tepat.

Algoritma Traveling Salesman Problem

Kami menggunakan pendekatan pemrograman dinamis untuk menyelesaikan TSP. Sebelum memulai algoritma, mari kita pahami beberapa terminologi terlebih dahulu:

• Sebuah grafik G = (V, E) adalah himpunan simpul dan sisi.
• V adalah himpunan simpul.
• E adalah himpunan sisi.
• Simpul dihubungkan melalui tepian.
• Dist(i, j) menunjukkan jarak non-negatif antara simpul i dan j.

Misalkan S adalah himpunan bagian kota yang diambil dari {1, 2, 3, …, n} di mana i dan j adalah dua kota dalam himpunan bagian tersebut. Maka cost(i, S, j) adalah panjang jalur terpendek yang dimulai dari i, mengunjungi setiap kota di S tepat sekali, dan berakhir di j.

Sebagai contoh, cost(1, {2, 3, 4}, 1) menunjukkan jalur terpendek di mana:

• Kota awal adalah 1
• Kota 2, 3, dan 4 hanya dikunjungi satu kali
• Titik akhirnya adalah 1

Rekurensi pemrograman dinamisnya adalah:

• set cost(i, {}, i) = 0, yang berarti kita mulai dan berakhir di i dengan biaya nol.
• Ketika |S| > 1, tentukan cost(i, S, 1) = ∞ untuk i ≠ 1, karena biaya tur yang sebenarnya belum diketahui.
• Mulai dari kota 1, pilih kota berikutnya sehingga cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] untuk i ∈ S ke i ≠ j.

Untuk grafik di atas, matriks kedekatannya adalah sebagai berikut:

Berikut cara kerja algoritma tersebut:

Langkah 1) Perjalanan dimulai di kota 1, mengunjungi setiap kota lain sekali, dan kembali ke kota 1.

Langkah 2) S adalah himpunan bagian dari kota-kota. Untuk setiap |S| > 1, inisialisasi cost(i, S, 1) = ∞. di sini cost(i, S, j) menunjukkan sebuah perjalanan yang dimulai dari i, mengunjungi kota-kota di S sekali, dan mencapai j. Kita mulai dari tak terhingga karena jaraknya tidak diketahui pada titik ini. Jadi nilainya adalah:

cost(2, {3, 4}, 1) = ∞ Artinya kita mulai dari kota 2, melewati kota 3 dan 4, dan sampai ke kota 1, dengan biaya yang tidak diketahui. Demikian pula:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Langkah 3) Untuk setiap himpunan bagian dari S, hitung:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Di mana j ∈ S ke i ≠ j.

Itulah rute dengan biaya minimum yang dimulai dari i, mengunjungi sebagian kota sekali, dan kembali ke j. Karena rute dimulai dari kota 1, biaya optimalnya adalah cost(1, {other cities}, 1).

Mengerjakan Pola Berulang Langkah demi Langkah

Sekarang S = {1, 2, 3, 4}. Ada empat elemen, jadi jumlah himpunan bagiannya adalah 2^4 = 16Himpunan bagian tersebut adalah:

1) |S| = 0: {Φ}

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}}

Karena tur dimulai di kota 1, kita dapat mengabaikan setiap himpunan bagian yang berisi kota 1 saat menghitung biaya perantara.

Perhitungan algoritma berlangsung sebagai berikut:

1) |S| = :

• biaya(2, Φ, 1) = jarak(2, 1) = 10
• biaya(3, Φ, 1) = jarak(3, 1) = 15
• biaya(4, Φ, 1) = jarak(4, 1) = 20

2) |S| = 1:

• biaya(2, {3}, 1) = jarak(2, 3) + biaya(3, Φ, 1) = 35 + 15 = 50
• biaya(2, {4}, 1) = jarak(2, 4) + biaya(4, Φ, 1) = 25 + 20 = 45
• biaya(3, {2}, 1) = jarak(3, 2) + biaya(2, Φ, 1) = 35 + 10 = 45
• biaya(3, {4}, 1) = jarak(3, 4) + biaya(4, Φ, 1) = 30 + 20 = 50
• biaya(4, {2}, 1) = jarak(4, 2) + biaya(2, Φ, 1) = 25 + 10 = 35
• biaya(4, {3}, 1) = jarak(4, 3) + biaya(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• biaya(2, {3, 4}, 1) = min [ jarak(2, 3) + biaya(3, {4}, 1) = 35 + 50 = 85, jarak(2, 4) + biaya(4, {3}, 1) = 25 + 45 = 70 ] = 70
• biaya(3, {2, 4}, 1) = min [ jarak(3, 2) + biaya(2, {4}, 1) = 35 + 45 = 80, jarak(3, 4) + biaya(4, {2}, 1) = 30 + 35 = 65 ] = 65
• biaya(4, {2, 3}, 1) = min [ jarak(4, 2) + biaya(2, {3}, 1) = 25 + 50 = 75, jarak(4, 3) + biaya(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• biaya(1, {2, 3, 4}, 1) = min [ jarak(1, 2) + biaya(2, {3, 4}, 1) = 10 + 70 = 80, jarak(1, 3) + biaya(3, {2, 4}, 1) = 15 + 65 = 80, jarak(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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

Implementasi di C/C++

Berikut implementasinya di C++Versi di bawah ini memperbaiki kesalahan awal pada sumbernya. return bug, yang muncul setelah permutasi pertama alih-alih menghitung semua tur.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

The Python implementasi mencerminkan C++ versi ini mengoreksi sumbernya. from itertools, import kesalahan ketik koma, salah tempat return di dalam lingkaran bagian dalam, dan lekukan yang tidak pada tempatnya s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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

Para ilmuwan komputer telah menghabiskan puluhan tahun mencari algoritma waktu polinomial yang lebih baik untuk Masalah Penjual Keliling (Travelling Salesman Problem/TSP). Sejauh ini, TSP masih termasuk dalam kategori NP-hard.

Beberapa teknik yang telah dipublikasikan mengurangi kompleksitas praktis untuk keluarga contoh TSP tertentu:

• Masalah TSP simetris klasik diselesaikan oleh Metode Akhiran Nol.
• The Algoritma Optimasi Berbasis Biogeografi menggunakan strategi migrasi untuk menyelesaikan masalah optimasi yang sesuai dengan TSP.
• The Algoritma Evolusi Multiobjektif dirancang untuk TSP multi-objektif dan dibangun berdasarkan NSGA-II.
• The Sistem Multi-Agen Pendekatan ini menyelesaikan TSP untuk N kota dengan sumber daya komputasi tetap.
• The Heuristik Lin-Kernighan dan penggantinya LKH Menghadirkan tur dengan akurasi 2-3% dari optimal untuk kasus-kasus dengan jutaan kota.
• Kerukunan menggunakan bidang potong dan metode branch-and-cut untuk menghitung optimasi yang tepat untuk contoh benchmark dengan puluhan ribu kota.

Penerapan Masalah Traveling Salesman

Masalah Penjual Keliling (Travelling Salesman Problem) muncul di dunia nyata baik dalam bentuk murni maupun yang dimodifikasi. Beberapa aplikasi utamanya adalah:

• Perencanaan, logistik, dan pembuatan mikrochip: Masalah penyisipan chip dalam industri mikrochip dimodelkan sebagai varian TSP untuk meminimalkan waktu tempuh lengan robot.
• Pengurutan DNA: TSP yang dimodifikasi digunakan dalam pengurutan DNA di mana kota-kota mewakili fragmen DNA dan jarak mewakili kemiripan antar fragmen.
• Astronomi: Para astronom menggunakan TSP untuk meminimalkan waktu yang dihabiskan untuk menggerakkan teleskop di antara target pengamatan.
• Kontrol optimal: Formulasi TSP memodelkan masalah kendali optimal di mana beberapa kendala harus dipenuhi sambil meminimalkan biaya penelusuran.
• Pengiriman jarak jauh: Amazon, UPS, dan aplikasi pengiriman makanan memecahkan varian TSP dinamis untuk mengatur urutan pemberhentian bagi pengemudi.
• Pengambilan di gudang: Robot dan petugas pemetik mengikuti rute yang dioptimalkan oleh TSP yang mempersingkat waktu tempuh di dalam pusat distribusi.

Analisis Kompleksitas TSP

• Kompleksitas Waktu: Pendekatan pemrograman dinamis Held-Karp menyelesaikan 2^N himpunan bagian untuk setiap simpul awal, memberikan N × 2^N submasalah. Setiap submasalah membutuhkan waktu linier untuk digabungkan. Jika simpul asal tidak ditentukan, diperlukan perulangan luar atas N simpul. Kompleksitas waktu totalnya adalah O(N² × 2^N).
• Kompleksitas Ruang: Tabel DP menyimpan C(S, i) untuk setiap himpunan bagian S dari himpunan simpul. Ada 2^N himpunan bagian per simpul, sehingga kompleksitas ruangnya adalah O(N × 2^N), yang sering ditulis sebagai O(2^N) ketika N dianggap tetap.

Selanjutnya, pelajari tentang Saringan Algoritma Eratosthenes.

Pertanyaan Umum Demo Slot