Algoritma 4 : Menggunakan DFS (depth First Search) Untuk menyelesaikan Traveling Sales Problem (TSP)

Algoritma Graf : Depth First Search

    Graf adalah struktur data yang digunakan untuk merepresentasikan hubungan antar objek, terdiri dari simpul (vertex) dan sisi (edge). Graf banyak digunakan dalam berbagai bidang, seperti jaringan komputer, peta jalan, hingga media sosial. Untuk menelusuri dan memahami isi graf, salah satu algoritma yang paling sering digunakan adalah DFS (Depth-First Search).

    Algoritma DFS bekerja dengan menjelajahi simpul sedalam mungkin sebelum kembali dan mencoba jalur lain. DFS sederhana namun sangat berguna, misalnya untuk mengecek keterhubungan simpul, menemukan jalur, mendeteksi siklus, hingga menjadi dasar bagi algoritma graf yang lebih kompleks.

• Setiap Node mewakili entitas (contoh: orang, perangkat, lokasi)
• Setiap Edge mewakili hubungan antar entitas (contoh: pertemanan, koneksi kabel, jalur jalan)

Jenis Graf

• Graf Terarah (Directed Graph)
  Hubungan punya arah. Misal: Alice mengirim email ke Bob ≠ Bob mengirim email ke Alice.
• Graf Tak Terarah (Undirected Graph)
  Hubungan dua arah. Misal: Alice berteman dengan Bob, otomatis Bob juga berteman dengan Alice.
• Graf Berbobot (Weighted Graph)
  Setiap sisi punya nilai, misalnya jarak, biaya, atau waktu tempuh.
• Graf Siklik & Asiklik
  • Siklik: Ada jalur yang bisa kembali ke titik awal.
  • Asiklik: Tidak ada jalur kembali.

Menyelesaikan Traveling Sales Problem dengan Algoritma DFS

Masalah: Ada seorang sales yang harus mengunjungi semua kota (A, B, C, D, E) sekali saja, lalu pulang ke kota awal (A). Dia ingin mencari rute dengan jarak paling pendek.

Data jarak antar kota:

• A ke B = 2 km, A ke C = 9 km, A ke D = 10 km, A ke E = 7 km
• B ke C = 6 km, B ke D = 4 km, B ke E = 3 km
• C ke D = 8 km, C ke E = 5 km
• D ke E = 6 km

Representasi dalam Graf

Masalah ini bisa direpresentasikan dalam bentuk graf berbobot:

Penggunaan Algoritma DFS dalam penyelesaian TSP

DFS digunakan untuk mengeksplorasi semua kemungkinan jalur yang mungkin dilalui oleh sales.

• Mulai dari kota A.
• Kunjungi kota berikutnya yang belum dikunjungi.
• Lanjutkan sampai semua kota dikunjungi.
• Setelah semua kota dikunjungi, kembali ke A.
• Simpan total jarak perjalanan.
• Bandingkan semua rute untuk mencari yang paling pendek.

Setelah melakukan perhitungan jarak setiap rute, didapati bahwa jalur optimal adalah:

A → B → D → C → E → A
Total = 26 Km

Contoh Kode Java

import java.util.*;

public class dfsAlgoritma {
    static int kota = 5;
    static String[] namaKota = {"A", "B", "C", "D", "E"};
    static int[][] jarakKota = {
            // A  B  C  D  E
            {0, 2, 9, 10, 7},  // A
            {2, 0, 6, 4, 3},   // B
            {9, 6, 0, 8, 5},   // C
            {10, 4, 8, 0, 6},  // D
            {7, 3, 5, 6, 0}    // E
    };

    static int biayaOpti = Integer.MAX_VALUE;
    static int[] pilihanTerbaik;

    public static void main(String[] args) {
        boolean[] penanda = new boolean[kota];
        penanda[0] = true;

        int[] jalur = new int[kota];
        jalur[0] = 0;

        dfs(penanda, jalur, 1, 0);

        System.out.println("Biaya optimal : " + biayaOpti);
        System.out.print("Rute Optimal  : ");
        for (int i = 0; i < kota; i++) {
            System.out.print(namaKota[pilihanTerbaik[i]] + " -> ");
        }
        System.out.println(namaKota[0]);
    }

    static void dfs(boolean[] penanda, int[] jalur, int kedalaman, int biayaSaatIni) {
        int saatIni = jalur[kedalaman - 1];
        if (biayaSaatIni >= biayaOpti) return;

        if (kedalaman == kota) {
            int biayaTotal = biayaSaatIni + jarakKota[saatIni][0];
            if (biayaTotal < biayaOpti) {
                biayaOpti = biayaTotal;
                pilihanTerbaik = Arrays.copyOf(jalur, kota);
            }
            return;
        }

        for (int next = 0; next < kota; next++) {
            if (!penanda[next]) {
                penanda[next] = true;
                jalur[kedalaman] = next;
                dfs(penanda, jalur, kedalaman + 1, biayaSaatIni + jarakKota[saatIni][next]);
                penanda[next] = false;
            }
        }
    }
}

Hasil Run Kode program

Pseudocode

Prosedur TSP_DFS(Graf, KotaSekarang, Jalur, Biaya):

   
 
    jika semua kota sudah dikunjungi maka
        Total = Biaya + jarak dari KotaSekarang ke KotaAwal
        kembalikan (Jalur + [KotaAwal], Total)

    RuteTerbaik = kosong
    BiayaTerbaik = tak hingga

  
    untuk setiap Tetangga dari KotaSekarang lakukan
        jika Tetangga belum ada di Jalur maka
            (Rute, TotalBiaya) = TSP_DFS(
                                   Graf, 
                                   Tetangga, 
                                   Jalur + [Tetangga], 
                                   Biaya + jarak dari KotaSekarang ke Tetangga
                                 )

            if TotalBiaya < BiayaTerbaik maka
                BiayaTerbaik = TotalBiaya
                RuteTerbaik = Rute
            else
            lanjut ke tetangga berikutnya
            
    return (RuteTerbaik, BiayaTerbaik)