ALGORITMA DEPTH FIRST SEARCH

DFS (Depth First Search) adalah algoritma pencarian/penelusuran graf atau pohon dengan cara menyusuri simpul (node) sedalam mungkin terlebih dahulu sebelum kembali (backtrack) dan mencoba jalur lain.

Ibaratnya ketika kita menelusiri labirin dan kita memilih untuk menjelajahi lorong terdalam kemudian mudur ketika tidak ada jalan lagi. Berikut adalah cara kerja algoritma DFS.

Mulai dari simpul awal (root atau source node).
Tandai simpul tersebut sebagai dikunjungi.
Telusuri tetangga simpul itu satu per satu:
- Jika ada tetangga yang belum dikunjungi, lanjut DFS ke sana (rekursi / stack)
- Jika semua tetangga sudah dikunjungi atau tidak ada jalan lagi, backtrack (kembali ke simpul sebelumnya).
Ulangi sampai semua simpul yang terhubung sudah dikunjungi.

Kali ini penulis akan menyelesaikan masalah TSP menggunakan algoritma DFS.

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

Algoritma DFS untuk masalah TSP ini bekerja dengan:

Memulai dari titik A.
Telusuri jalur selanjutnya dengan DFS.
Simpan semua jalur yang telah mengunjungi semua kota beserta jaraknya.
Jika selanjutnya ada yang lebih kecil dari jarak minimum yang disimpan maka update jarak minimumnya.
jika selanjutnya ada yang lebih besar dari jarak minimum maka langsung backtracking.
Setelah semua jalur ditelusuri, ambil jalur dengan jarak minimum.

Pseudo Code


    Deklarasi:
    kota = 5
    namaKota = [ "A", "B", "C", "D", "E" ]
    jarakAntarKota = matriks jarak 5x5
    biayaOptimal = ∞
    pilihanOptimal = array kosong

    Prosedur utama:
    buat array penanda[kota], isi dengan false
    buat array jalur[kota]

    tandai kota pertama (A) sebagai sudah dikunjungi
    masukkan A ke jalur[0]

    DFS(penanda, jalur, kedalaman=1, biayaSaatIni=0)

    cetak biayaOptimal
    cetak rute pilihanOptimal + kembali ke A


    Prosedur DFS(penanda, jalur, kedalaman, biayaSaatIni):
    saatIni = jalur[kedalaman - 1]

    // pruning: hentikan jika biaya sudah lebih besar dari solusi terbaik
    jika biayaSaatIni >= biayaOptimal:
        return

    // basis: jika semua kota sudah dikunjungi
    jika kedalaman == kota:
        biayaTotal = biayaSaatIni + jarakAntarKota[saatIni][A]
        jika biayaTotal < biayaOptimal:
            biayaOptimal = biayaTotal
            salin jalur ke pilihanOptimal
        return

    // coba kunjungi semua kota yang belum dikunjungi
    untuk setiap next dari 0 sampai kota-1:
        jika penanda[next] == false:
            penanda[next] = true
            jalur[kedalaman] = next
            DFS(penanda, jalur, kedalaman + 1, biayaSaatIni + jarakAntarKota[saatIni][next])
            penanda[next] = false   // backtrack

Algoritma DFS pada TSP bekerja dengan langkah-langkah berikut:

Pencarian dimulai dari A lalu menuju B lalu ke C ke D dan terakhir ke E mengikuti prinsip DFS.
Jalur pertama disimpan A->B->C->D->E lalu total jarak ditambah dengan jarak E ke A sebagai tanda bahwa salesman telah kembali ke kota A. jarak minimum saat ini 29.
DFS telah mencapai dasar, maka kita lakukan backtracking dari E ke D.
Karena semua kota tetangga D telah dikunjungi kecuali E, maka backtracking dilakukan sekali lagi menuju C.
Dari C kemudian menuju kota yang belum dikunjungi yaitu E lalu D.
Jalur Kedua disimpan yaitu A->B->C->E->D kemudian total jarak ditambah dengan jarak D ke A.
Jarak dari jalur kedua adalah 29 yang sama dengan jarak minimum saat ini maka tidak perlu mengganti jarak minimum.
Lakukan backtracking lagi hingga semua jalur ditelusuri. Hasil yang didapatkan secara berurutan adalah sebagai berikut.
- A->B->C->D->E->A = 2 + 6 + 8 + 6 + 7 = 29
- A->B->C->E->D->A = 2 + 6 + 5 + 6 + 10 = 29
- A->B->D->C->E->A = 2 + 4 + 8 + 5 + 7 = 26
- A->B->D->E->C->A = 2 + 4 + 6 + 5 + 9 = 26
- A->B->E->C->D->A = 2 + 3 + 5 + 8 + 10 = 28
- A->B->E->D->C->A = 2 + 3 + 6 + 8 + 9 = 28
- A->C->B->D->E->A = 9 + 6 + 4 + 6 + 7 = 32
- A->C->B->E->D->A = 9 + 6 + 3 + 6 + 10 = 34
- A->C->D->B->E->A = 9 + 8 + 4 + 3 + 7 = 31
- A->C->D->E->B->A = 9 + 8 + 6 + 3 + 2 = 28
- A->C->E->B->D->A = 9 + 5 + 3 + 4 + 10 = 31
- A->C->E->D->B->A = 9 + 5 + 6 + 4 + 2 = 26
- A->D->B->C->E->A = 10 + 4 + 6 + 5 + 7 = 32
- A->D->B->E->C->A = 10 + 4 + 3 + 5 + 9 = 31
- A->D->C->B->E->A = 10 + 8 + 6 + 3 + 7 = 34
- A->D->C->E->B->A = 10 + 8 + 5 + 3 + 2 = 28
- A->D->E->B->C->A = 10 + 6 + 3 + 6 + 9 = 34
- A->D->E->C->B->A = 10 + 6 + 5 + 6 + 2 = 29
- A->E->B->C->D->A = 7 + 3 + 6 + 8 + 10 = 34
- A->E->B->D->C->A = 7 + 3 + 4 + 8 + 9 = 31
- A->E->C->B->D->A = 7 + 5 + 6 + 4 + 10 = 32
- A->E->C->D->B->A = 7 + 5 + 8 + 4 + 2 = 26
- A->E->D->B->C->A = 7 + 6 + 4 + 6 + 9 = 32
- A->E->D->C->B->A = 7 + 6 + 8 + 6 + 2 = 29
Perlu diperhatikan bahwa algoritma DFS pada TSP ini akan melakukan backtracking otomatis ketika total jarak dari jalur sudah sama atau lebih dari jarak minimum. Jadi terkadang Jalur tidak ditelusuri hingga akhir.
Hasil yang penulis dapatkan adalah A->B->D->C->E->A = 2 + 4 + 8 + 5 + 7 = 26.

selanjutnya penulis akan mengimplementasikannya pada code java.

Code Java


    import java.util.*;

    public class dfs {
        static int kota = 5;
        static String[] namaKota = {"A", "B", "C", "D", "E"};
        static int[][] jarakAntarKota = {
            //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 biayaOptimal = Integer.MAX_VALUE;
        static int[] pilihanOptimal;

        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 :"+biayaOptimal);
            System.out.print("Rute Optimal :");
            for (int i = 0; i < kota; i++) {
                System.out.print(namaKota[pilihanOptimal[i]]+"->");
            }
            System.out.println(namaKota[0]);

        }

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

            if (kedalaman == kota) {
                int biayaTotal = biayaSaatIni + jarakAntarKota[saatIni][0];
                if (biayaTotal < biayaOptimal) {
                    biayaOptimal = biayaTotal;
                    pilihanOptimal = 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 + jarakAntarKota[saatIni][next]);
                    penanda[next] = false;
                }
            }
        }
    }

Setelah penggunaan kode tersebut, penulis akhirnya mendapatkan output yaitu:

OUTPUT


            Biaya optimal :26
            Rute Optimal :A->B->D->C->E->A

            Process finished with exit code 0

Setelah penulis menyelesaikan masalah TSP dengan menggunakan algoritma DFS, penulis mengambil kesimpulan bahwa algoritma DFS dapat lebih optimal dan efisien dalam menyelesaikan TSP dibandingkan algoritma Brute Force dan algoritma Greedy yang telah dibuat oleh penulis sebelumnya. Hasil yang didapatkan sama optimalnya dengan algoritma brute force, akan tetapi algoritma DFS jelas lebih efisien dari algoritma brute force.

Cari Blog Ini

Wahyu Anugrah