Algoritma Breadth-First Search
Algoritma Breadth-First Search
Apa itu algoritma Algoritma Breadth-First Search
Algoritma Breadth-First Search (BFS) adalah salah satu algoritma pencarian graf yang paling mendasar. Sesuai namanya, "breadth-first" yang berarti "lebar-terlebih dahulu," algoritma ini menjelajahi semua simpul (atau node) pada level atau kedalaman yang sama sebelum melanjutkan ke level berikutnya yang lebih dalam.
Contohnya gini, ketika kamu memasuki sebuah rumah, pertama kamu akan masuk keruang tamu, kamu kemudian akan mengecek semua ruangan yang terhubung langsung ke ruangan tamu. Misal nih, ada tiga kamar dan satu dapur yang terhubung langsung dengan ruang tamu, kamu akan mengecek semua ruangan itu dan mengabaikan jika ada ruangan lain di dalam ruangan yang kamu kunjungi. Setelah kamu mengunjungi semua ruangan kamu akan mengunjungi ruangan pada ruangan yang terhubung dengan ruangan yang kamu telah kunjungi. Misalnya, dalam kamar satu, dua dan dapur terdapat wc. Kamu akan mengunjungi wc di tersebut entah kamu memulai dari dapur dulu, kamar satu dulu atau kamar dua dulu.
Bagaimana BFS Bekerja
Algoritma BFS bekerja dengan bantuan sebuah struktur data yang disebut antrean (queue). Antrean ini bekerja
dengan prinsip FIFO (First-In, First-Out), artinya data yang pertama masuk adalah data yang
pertama keluar.
Berikut adalah langkah-langkah sistematisnya:
- Inisialisasi:
- Pilih sebuah simpul awal (starting node) untuk memulai pencarian.
- Masukkan simpul awal ini ke dalam antrean.
- Tandai simpul awal sebagai "sudah dikunjungi" untuk menghindari penjelajahan berulang.
- Proses Antrean:
- Selama antrean tidak kosong, lakukan langkah-langkah berikut:
- Keluarkan simpul terdepan dari antrean. Sebut saja simpul ini 'U'.
- Lakukan operasi yang diinginkan pada simpul 'U' (misalnya, memeriksanya apakah itu tujuan yang dicari).
- Selama antrean tidak kosong, lakukan langkah-langkah berikut:
- Eksplorasi Tetangga:
- Periksa semua simpul tetangga (simpul yang terhubung langsung) dari 'U'.
- Untuk setiap tetangga yang belum pernah dikunjungi:
- Tandai tetangga tersebut sebagai "sudah dikunjungi".
- Masukkan tetangga tersebut ke dalam antrean.
- Selesai:
- Algoritma akan berhenti ketika antrean sudah kosong (artinya semua simpul yang terhubung telah dijelajahi) atau ketika tujuan pencarian telah ditemukan.
Menyelesaikan TSP dengan Algoritma BFS
Kali ini penulis akan menyelesaikan TSP berikut dengan menggunakan algoritma BFS.
Penulis akan menyelesaikan TSP diatas dengan menggunakan algoritma BFS dengan beberapa langkah.
- Melakukan inisialisasi
- Melakukan iterasi dengan algoritma BFS
- Menghitung jarak final
- Menganalisis jarak terpendek
Psuedo Code
// Definisi struktur data untuk menyimpan state pencarian
// (mirip seperti class State di Java)
STRUCTURE State
posisiSaatIni : INTEGER
jalur : LIST OF INTEGER
biaya : INTEGER
END STRUCTURE
// Fungsi utama untuk menjalankan algoritma
FUNCTION Solve_TSP_BFS(jarak, N, kotaAwal)
// 1. Inisialisasi
queue ← new Queue()
biayaTermurah ← INFINITY
jalurTerbaik ← NULL
// Buat state awal dan masukkan ke dalam antrean
jalurAwal ← [kotaAwal]
stateAwal ← new State(posisiSaatIni=kotaAwal, jalur=jalurAwal, biaya=0)
queue.enqueue(stateAwal)
// 2. Proses antrean selama tidak kosong
WHILE queue is not empty DO
// Ambil state terdepan dari antrean
stateSekarang ← queue.dequeue()
// 3. Cek apakah semua kota telah dikunjungi
IF size of stateSekarang.jalur == N THEN
// Hitung biaya total dengan kembali ke kota awal
biayaTotal ← stateSekarang.biaya + jarak[stateSekarang.posisiSaatIni][kotaAwal]
// Jika ditemukan rute yang lebih pendek, simpan
IF biayaTotal < biayaTermurah THEN
biayaTermurah ← biayaTotal
jalurTerbaik ← stateSekarang.jalur
// Tambahkan kota awal di akhir untuk melengkapi siklus
jalurTerbaik.add(kotaAwal)
END IF
// Lanjutkan ke iterasi berikutnya, karena rute ini sudah selesai
CONTINUE
END IF
// 4. Ekspansi ke kota tetangga yang belum dikunjungi
FOR kotaBerikutnya FROM 0 TO N-1 DO
// Cek apakah kotaBerikutnya sudah ada di jalur saat ini
IF kotaBerikutnya is NOT IN stateSekarang.jalur THEN
// Buat jalur dan biaya baru
jalurBaru ← copy of stateSekarang.jalur
jalurBaru.add(kotaBerikutnya)
biayaBaru ← stateSekarang.biaya + jarak[stateSekarang.posisiSaatIni][kotaBerikutnya]
// Buat state baru dan masukkan ke antrean
stateBaru ← new State(posisiSaatIni=kotaBerikutnya, jalur=jalurBaru, biaya=biayaBaru)
queue.enqueue(stateBaru)
END IF
END FOR
END WHILE
// 5. Tampilkan hasil akhir
PRINT "Rute terbaik ditemukan:", jalurTerbaik
PRINT "Jarak total:", biayaTermurah
END FUNCTION
Bagaimana Code Akan Bekerja
Berikut adalah bagaimana kode Anda akan berjalan, langkah demi langkah, untuk menemukan solusi.
- 1: Inisialisasi (Level 0)
- Mulai dari A: Sebuah State awal dibuat.
- posisiSaatIni: A (indeks 0)
- jalur: [A]
- biaya: 0
- Masukkan ke Antrean: State awal ini dimasukkan ke dalam antrean.
- Isi Antrean: [ (A, jalur:[A], biaya:0) ]
- Inisialisasi Biaya: biayaTermurah diatur ke nilai tak terhingga (Integer.MAX_VALUE).
- Mulai dari A: Sebuah State awal dibuat.
- 2: Eksplorasi Level 1 (Semua rute dengan 2 kota)
- Keluarkan dari Antrean: State terdepan, yaitu (A, jalur:[A], biaya:0), dikeluarkan dari antrean.
- Ekspansi ke Tetangga: Algoritma mencari semua tetangga A (B, C, D, E) dan membuat State baru untuk
masing-masing, lalu memasukkannya ke belakang antrean.
- Buat state ke B: (B, jalur:[A,B], biaya:2) -> Masuk antrean.
- Buat state ke C: (C, jalur:[A,C], biaya:9) -> Masuk antrean.
- Buat state ke D: (D, jalur:[A,D], biaya:10) -> Masuk antrean.
- Buat state ke E: (E, jalur:[A,E], biaya:7) -> Masuk antrean.
- Hasil Level 1: Antrean kini berisi semua kemungkinan rute yang terdiri dari dua kota.
- Isi Antrean: [ (B, [A,B], 2), (C, [A,C], 9), (D, [A,D], 10), (E, [A,E], 7) ]
- 3: Eksplorasi Level 2 (Semua rute dengan 3 kota)
- Keluarkan dari Antrean: State terdepan, (B, [A,B], 2), dikeluarkan. Tetangganya yang belum
dikunjungi (C, D, E) dieksplorasi.
- Buat state ke C: (C, [A,B,C], 2+6=8) -> Masuk antrean.
- Buat state ke D: (D, [A,B,D], 2+4=6) -> Masuk antrean.
- Buat state ke E: (E, [A,B,E], 2+3=5) -> Masuk antrean.
- Keluarkan Berikutnya: State berikutnya di antrean, (C, [A,C], 9), dikeluarkan dan dieksplorasi ke
tetangganya.
- Buat state ke B: (B, [A,C,B], 9+6=15) -> Masuk antrean.
- ... dan seterusnya.
- Keluarkan dari Antrean: State terdepan, (B, [A,B], 2), dikeluarkan. Tetangganya yang belum
dikunjungi (C, D, E) dieksplorasi.
- 4: Mencapai Solusi Pertama
- Setelah beberapa lama, sebuah State yang dikeluarkan dari antrean akan memiliki jalur yang lengkap (sudah berisi 5 kota), misalnya (E, jalur:[A,B,C,D,E], biaya:22).
- Kode kemudian memeriksa
if (s.jalur.size() == N). - Biaya total dihitung dengan menambahkan jarak kembali ke kota A: biayaTotal = 22 + jarak[E][A] = 22 + 7 = 29.
- Karena 29 lebih kecil dari biayaTermurah (yang masih tak terhingga), maka:
- biayaTermurah di-update menjadi 29.
- biayaTerbaik disimpan sebagai [A,B,C,D,E,A].
- 5: Menemukan Solusi Optimal
Kode BFS ini akan terus berjalan sampai antrean kosong. Ia akan terus menemukan semua jalur lengkap lainnya.- Nantinya, ia akan memproses State yang menghasilkan jalur A->B->D->C->E. Biaya parsialnya adalah 2 + 4 + 8 + 5 = 19.
- Ketika State (E, jalur:[A,B,D,C,E], biaya:19) dikeluarkan, biaya totalnya dihitung: biayaTotal = 19 + jarak[E][A] = 19 + 7 = 26.
- Karena 26 < 29, maka biayaTermurah di-update lagi menjadi 26, dan biayaTerbaik diganti dengan [A,B,D,C,E,A].
Code Java
import java.util.*;
public class BFS_TSP {
// Representasi graf dengan matriks jarak
static int[][] jarak = {
// 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 String[] kota = {"A", "B", "C", "D", "E"};
static int N = kota.length;
// Struktur state BFS
static class State {
int posisiSaatIni; // posisi sekarang
List jalur; // jalur yang sudah dikunjungi
int biaya; // total jarak sementara
State(int posisiSaatIni, List jalur, int biaya) {
this.posisiSaatIni = posisiSaatIni;
this.jalur = new ArrayList<>(jalur);
this.biaya = biaya;
}
}
public static void main(String[] args) {
int start = 0; // mulai dari kota A (indeks 0)
Queue queue = new LinkedList<>();
queue.add(new State(start, Arrays.asList(start), 0));
int biayaTermurah = Integer.MAX_VALUE;
List biayaTerbaik = null;
while (!queue.isEmpty()) {
State s = queue.poll();
// Jika sudah mengunjungi semua kota
if (s.jalur.size() == N) {
int biayaTotal = s.biaya + jarak[s.posisiSaatIni][start]; // kembali ke A
if (biayaTotal < biayaTermurah) {
biayaTermurah = biayaTotal;
biayaTerbaik = new ArrayList<>(s.jalur);
biayaTerbaik.add(start); // tambahkan kembali ke A
}
continue;
}
// Ekspansi ke tetangga yang belum dikunjungi
for (int next = 0; next < N; next++) {
if (!s.jalur.contains(next)) {
int biayaSaatIni = s.biaya + jarak[s.posisiSaatIni][next];
List jalurSaatIni = new ArrayList<>(s.jalur);
jalurSaatIni.add(next);
queue.add(new State(next, jalurSaatIni, biayaSaatIni));
}
}
}
// Tampilkan hasil terbaik
System.out.print("Rute terbaik (BFS): ");
for (int idx : biayaTerbaik) {
System.out.print(kota[idx] + " -> ");
}
System.out.println(" | Jarak total = " + biayaTermurah + " km");
}
}
Output
"C:\Program Files\Java\jdk-23\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA Community Edition 2024.3.5\lib\idea_rt.jar=52047" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath C:\Users\WhyuA\OneDrive\Documents\IntellijIDEAProjects\classAlgoritma\out\production\classAlgoritma BFS_TSP
Rute terbaik (BFS): A -> B -> D -> C -> E -> A -> | Jarak total = 26 km
Process finished with exit code 0
Setelah semua proses dan output telah ditemukan. Penulis mengambil kesimpulan bahwa algoritma BFS optimal dalam menyelesaikan TSP tapi tidak efisien. Bisa dikatakan bahwa algoritma BFS ini mirip dengan brute force tetapi dengan struktur iterasi yang lebih jelas. Dalam menyelesaikan TSP, algoritma BFS lebih baik dari greedy, sama dengan brute force dan tidak lebih baik dari DFS.
Komentar
Posting Komentar