Algoritma pencarian merupakan fondasi utama dalam bidang Kecerdasan Buatan atau Artificial Intelligence (AI). Dari sekian banyak algoritma yang ada, Bidirectional Search muncul sebagai solusi cerdas untuk mengoptimalkan efisiensi pencarian pada struktur data graf yang besar. Artikel ini akan membahas secara mendalam mengenai konsep, mekanisme, hingga contoh soal Bidirectional Search untuk membantu Anda memahami cara kerja algoritma ini secara komprehensif.
Apa Itu Bidirectional Search
Bidirectional Search adalah algoritma pencarian jalur yang bekerja dengan menjalankan dua pencarian secara simultan. Pencarian pertama dilakukan dari titik awal (start node) ke arah depan (forward), sementara pencarian kedua dilakukan dari titik tujuan (goal node) ke arah belakang (backward). Pencarian ini akan berhenti ketika kedua pencarian tersebut bertemu di sebuah titik tengah (fringe).
Alasan utama penggunaan Bidirectional Search adalah efisiensi waktu. Dalam algoritma pencarian tradisional seperti Breadth First Search (BFS), jika faktor percabangan adalah $b$ dan jarak solusi adalah $d$, maka kompleksitas waktunya adalah $O(b^d)$. Namun, dengan membagi pencarian menjadi dua bagian, masing-masing pencarian hanya perlu menempuh jarak $d/2$. Hal ini mengubah kompleksitas menjadi $O(b^{d/2} + b^{d/2})$, yang secara signifikan lebih kecil daripada $O(b^d)$.
Baca juga: Contoh Soal Tes Perbankan Syariah dan Pembahasan Lengkap untuk Persiapan
Karakteristik dan Syarat Penggunaan
Sebelum masuk ke contoh soal, penting untuk memahami bahwa tidak semua masalah bisa diselesaikan dengan Bidirectional Search. Ada beberapa syarat yang harus dipenuhi:
- State tujuan (goal state) harus diketahui secara spesifik. Jika tujuannya abstrak (misalnya dalam permainan catur di mana tujuannya adalah skakmat tanpa menentukan posisi bidak yang spesifik), algoritma ini sulit diterapkan.
- Operator atau langkah harus bersifat reversible (bisa dibalik). Artinya, kita harus bisa menghitung node mana saja yang dapat mencapai node saat ini dalam arah mundur.
- Harus ada metode yang efisien untuk mengecek apakah dua pencarian telah bertemu pada node yang sama.
Mekanisme Kerja Bidirectional Search
Bayangkan sebuah graf yang menghubungkan titik-titik lokasi. Proses pencarian akan dimulai dengan dua antrean (queue). Antrean A memulai dari titik awal, dan Antrean B memulai dari titik tujuan. Pada setiap langkah, algoritma akan mengekspansi satu level pada kedua sisi. Setiap kali sebuah node baru dikunjungi, algoritma akan memeriksa apakah node tersebut sudah pernah dikunjungi oleh pencarian dari arah berlawanan. Jika ya, jalur telah ditemukan.
Contoh Soal Bidirectional Search 1: Pencarian Jalur Graf Sederhana
Misalkan kita memiliki sebuah graf dengan node-node sebagai berikut:
- Node awal: A
- Node tujuan: E
- Hubungan antar node:
- A terhubung ke B dan C
- B terhubung ke D
- C terhubung ke D
- D terhubung ke E
Tugas: Temukan jalur dari A ke E menggunakan Bidirectional Search.
Langkah 1: Inisialisasi
- Pencarian Depan (Forward): Queue_F = {A}
- Pencarian Belakang (Backward): Queue_B = {E}
- Visited_F = {A}
- Visited_B = {E}
Langkah 2: Ekspansi Level 1
- Forward: Ekspansi A. Tetangga A adalah {B, C}. Tambahkan ke Queue_F dan Visited_F.
- Queue_F = {B, C}
- Visited_F = {A, B, C}
- Backward: Ekspansi E. Tetangga yang bisa mencapai E adalah {D}. Tambahkan ke Queue_B dan Visited_B.
- Queue_B = {D}
- Visited_B = {E, D}
Langkah 3: Pemeriksaan Pertemuan
- Cek apakah ada irisan antara Visited_F dan Visited_B.
- Visited_F ∩ Visited_B = {A, B, C} ∩ {E, D} = Kosong.
- Lanjutkan ekspansi.
Langkah 4: Ekspansi Level 2
- Forward: Ekspansi B. Tetangga B adalah {D}.
- Cek apakah D ada di Visited_B? Ya, D ada di Visited_B.
- Pertemuan Terdeteksi: Algoritma berhenti karena node D ditemukan oleh kedua pencarian.
Hasil: Jalur ditemukan melalui titik temu D. Jalur lengkapnya adalah A -> B -> D -> E.
Contoh Soal Bidirectional Search 2: Masalah Rute Kota
Diberikan sebuah peta kota kecil dengan jarak antar titik yang dianggap seragam (menggunakan BFS pada kedua sisi).
- Kota Asal: Jakarta (J)
- Kota Tujuan: Surabaya (S)
- Koneksi:
- J terhubung ke Bandung (B) dan Semarang (SM)
- B terhubung ke Yogyakarta (Y)
- SM terhubung ke Yogyakarta (Y) dan Surabaya (S)
Langkah-langkah Penyelesaian:
- Mulai dari Jakarta (J) di sisi depan dan Surabaya (S) di sisi belakang.
- Sisi Depan: J diekspansi menjadi B dan SM. (Kunjungi: J, B, SM)
- Sisi Belakang: S diekspansi menjadi SM. (Kunjungi: S, SM)
- Cek Pertemuan: Node SM telah dikunjungi oleh kedua sisi.
- Jalur ditemukan: Jakarta -> Semarang -> Surabaya.
Dalam contoh ini, pencarian selesai dalam 2 langkah ekspansi. Jika menggunakan BFS biasa, kita mungkin harus mengekspansi Bandung dan Yogyakarta sebelum akhirnya mencapai Surabaya melalui Semarang, yang memakan lebih banyak langkah memori.
Analisis Kompleksitas
Untuk memahami mengapa contoh soal di atas penting, mari kita tinjau secara matematis. Jika kita memiliki graf dengan branching factor (b) sebesar 10 dan kedalaman solusi (d) adalah 6:
- Pencarian satu arah (BFS): $10^6 = 1.000.000$ node yang mungkin diekspansi.
- Bidirectional Search: $10^3 + 10^3 = 1.000 + 1.000 = 2.000$ node yang diekspansi.
Perbedaan antara 1.000.000 dan 2.000 menunjukkan efisiensi luar biasa yang ditawarkan oleh algoritma ini dalam memecahkan masalah pencarian rute atau state-space.
Kelebihan dan Kekurangan Bidirectional Search
Meskipun efisien secara waktu, ada beberapa hal yang perlu diperhatikan dalam implementasi nyata:
Kelebihan:
- Reduksi waktu secara eksponensial.
- Sangat efektif untuk masalah dengan ruang pencarian (search space) yang luas.
- Menjamin jalur terpendek jika menggunakan Breadth First Search pada kedua sisi.
Kekurangan:
- Membutuhkan memori yang besar karena semua node dari kedua pencarian harus disimpan dalam memori untuk pengecekan tabrakan (collision).
- Implementasi lebih rumit karena harus mengelola dua proses pencarian dan menghitung “pendahulu” untuk pencarian mundur.
- Sulit diterapkan jika goal state tidak tunggal atau tidak diketahui secara pasti.
Implementasi dalam Kode Program (Pseudocode)
Bagi Anda yang sedang mempelajari pemrograman AI, berikut adalah logika dasar atau pseudocode untuk mengimplementasikan contoh soal di atas:
Plaintext
function BidirectionalSearch(start, goal):
queue_f = [start]
queue_b = [goal]
visited_f = {start: null}
visited_b = {goal: null}
while queue_f is not empty and queue_b is not empty:
# Ekspansi dari depan
current_f = queue_f.pop(0)
for neighbor in neighbors(current_f):
if neighbor not in visited_f:
visited_f[neighbor] = current_f
queue_f.append(neighbor)
if neighbor in visited_b:
return construct_path(visited_f, visited_b, neighbor)
# Ekspansi dari belakang
current_b = queue_b.pop(0)
for neighbor in predecessors(current_b):
if neighbor not in visited_b:
visited_b[neighbor] = current_b
queue_b.append(neighbor)
if neighbor in visited_f:
return construct_path(visited_f, visited_b, neighbor)
Baca juga: Rektor Universitas Teknokrat Indonesia Salurkan Donasi untuk Korban Bencana Sumatera melalui ICMI
Kesimpulan
Bidirectional Search merupakan teknik optimasi yang sangat kuat dalam dunia ilmu komputer. Melalui contoh soal yang telah dibahas, terlihat jelas bahwa membagi pencarian menjadi dua arah dapat menghemat sumber daya komputasi secara signifikan. Meskipun memiliki tantangan dalam hal penggunaan memori, algoritma ini tetap menjadi pilihan utama untuk sistem navigasi, pemecahan puzzle seperti Rubik’s Cube, dan analisis jaringan sosial.
Memahami Bidirectional Search bukan hanya tentang menghafal rumus, tetapi tentang memahami logika bagaimana sebuah masalah besar dapat dipecah menjadi dua masalah kecil yang lebih mudah dikelola. Dengan latihan rutin pada berbagai variasi graf, Anda akan semakin mahir dalam menentukan kapan saat yang tepat untuk menggunakan strategi pencarian dua arah ini dalam proyek pengembangan perangkat lunak atau riset AI Anda.
Penulis: Aripin
Post Comment