Postingan Baru

Algoritma 5: Menggunakan BFS (Breadth First Search) Untuk menyelesaikan Traveling Sales Problem (TSP)

Posted by Wahyuni Lestari Yasin pada tanggal
Penjelasan BFS (Breadth-First Search)

Breadth-First Search (BFS)

Penjelasan, contoh, penyelesaian kasus, pseudocode, kode contoh, dan hasil output

Apa itu BFS

BFS (Breadth-First Search) adalah algoritma penelusuran graf yang bekerja dengan cara menjelajahi simpul (node) secara bertingkat (level by level).

Proses ini menggunakan struktur data queue (antrian).

Kapan BFS Digunakan

BFS sangat berguna pada kondisi tertentu, terutama saat bekerja dengan graf dan pohon.

  • Menemukan jalur terpendek pada graf tak berbobot.
  • Melakukan level-order traversal pada pohon.
  • Memeriksa apakah suatu graf terhubung atau tidak.
  • Menentukan jarak minimum dari satu simpul ke simpul lain.
  • Pencarian solusi dalam permainan atau puzzle yang bisa dimodelkan sebagai graf.

Nah pada postingan kali ini kita akan menggunakan algoritma BFS untuk menyelesaikan Traveling Sales Problem (TSP).

Definisi BFS

Breadth First Search (BFS) adalah algoritma penelusuran graf yang bekerja dengan cara menelusuri simpul secara melebar (level demi level) mulai dari simpul awal. Proses ini menggunakan struktur data queue (antrian) untuk memastikan bahwa simpul-simpul yang berada pada level yang sama dikunjungi terlebih dahulu sebelum melanjutkan ke level berikutnya.

Konsep dasar BFS

  1. Mulai dari simpul sumber, kunjungi semua tetangga pada jarak 1.
  2. Kemudian kunjungi tetangga dari tetangga (jarak 2), dan seterusnya — traverse per-level.
  3. Gunakan struktur data queue dan array/struktur untuk menandai node yang sudah dikunjungi.

Pseudocode

Input: 
  - kota[] : daftar nama kota
  - jarak[][] : matriks jarak antar kota
  - awal : kota awal (misalnya A)

Proses:
  buat antrian kosong
  masukkan ke antrian: ( [awal], 0 )   // rute berisi kota awal, biaya = 0

  ruteTerbaik ← null
  biayaTerbaik ← tak hingga

  SELAMA antrian tidak kosong:
      (rute, biaya) ← keluarkan dari antrian

      JIKA semua kota sudah dikunjungi:
          totalBiaya ← biaya + jarak[kotaTerakhir][awal]
          JIKA totalBiaya < biayaTerbaik:
              biayaTerbaik ← totalBiaya
              ruteTerbaik ← rute + [awal]
      JIKA BELUM:
          kotaTerakhir ← rute[kota terakhir]
          UNTUK setiap kota i yang belum dikunjungi:
              ruteBaru ← rute + [i]
              biayaBaru ← biaya + jarak[kotaTerakhir][i]
              masukkan (ruteBaru, biayaBaru) ke antrian

Output:
  tampilkan ruteTerbaik
  tampilkan biayaTerbaik

Contoh penyelesaian kasus

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 Masalah

  1. Node = kota (A, B, C, D, E).
  2. BFS state = urutan kunjungan + total jarak sejauh ini.
  3. Tujuan = semua kota dikunjungi tepat sekali, lalu kembali ke A.

Contoh kode


import java.util.*;

public class BFSTSP {
    static String[] kota = {"A", "B", "C", "D", "E"};
    static int jumlahKota = kota.length;

    // Matriks jarak antar kota
    static int[][] jarak = {
        {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 class Perjalanan {
        List rute;
        int biaya;

        Perjalanan(List rute, int biaya) {
            this.rute = rute;
            this.biaya = biaya;
        }
    }

    public static void main(String[] args) {
        cariRuteTerpendek(0);
    }

    static void cariRuteTerpendek(int awal) {
        Queue antrian = new LinkedList<>();
        antrian.add(new Perjalanan(Arrays.asList(awal), 0));

        int biayaTerbaik = Integer.MAX_VALUE;
        List ruteTerbaik = null;

        while (!antrian.isEmpty()) {
            Perjalanan sekarang = antrian.poll();
            List rute = sekarang.rute;
            int biaya = sekarang.biaya;

            if (rute.size() == jumlahKota) {
                int totalBiaya = biaya + jarak[rute.get(rute.size()-1)][awal];
                if (totalBiaya < biayaTerbaik) {
                    biayaTerbaik = totalBiaya;
                    ruteTerbaik = new ArrayList<>(rute);
                    ruteTerbaik.add(awal);
                }
            } else {
                int terakhir = rute.get(rute.size()-1);
                for (int i = 0; i < jumlahKota; i++) {
                    if (!rute.contains(i)) {
                        List ruteBaru = new ArrayList<>(rute);
                        ruteBaru.add(i);
                        int biayaBaru = biaya + jarak[terakhir][i];
                        antrian.add(new Perjalanan(ruteBaru, biayaBaru));
                    }
                }
            }
        }

        System.out.print("Rute terpendek: ");
        for (int i = 0; i < ruteTerbaik.size(); i++) {
            System.out.print(kota[ruteTerbaik.get(i)]);
            if (i < ruteTerbaik.size()-1) System.out.print(" -> ");
        }
        System.out.println("\nTotal jarak: " + biayaTerbaik + " km");
    }
}

Kesimpulan

Penerapan algoritma Breadth First Search (BFS) dalam penyelesaian Travelling Salesman Problem (TSP) mampu menemukan rute terpendek dengan cara mengeksplorasi semua kemungkinan perjalanan secara sistematis. Walaupun BFS menjamin solusi optimal, kelemahannya adalah kompleksitas yang cukup besar karena semua jalur dicoba satu per satu.

Komentar

Posting Komentar