Kecerdasan Buatan-7SI-2: Pertemuan 3

1. Pencarian Buta dalam Kecerdasan Buatan:┬áPencarian buta (blind search) atau pencarian tidak berinformasi adalah metode pencarian yang tidak menggunakan informasi tambahan mengenai domain masalah untuk mengarahkan proses pencarian. Artinya, algoritma hanya menggunakan struktur dasar dari masalah, seperti model state-space (ruang keadaan) dan operator, tanpa memanfaatkan informasi heuristik untuk membimbing pencarian.

┬á ┬áPeran utama pencarian buta dalam pemecahan masalah adalah sebagai pendekatan dasar yang dapat digunakan ketika tidak ada informasi spesifik tentang solusi atau jalan menuju solusi yang optimal. Teknik ini menjamin pencarian solusi, namun sering kali memerlukan lebih banyak waktu dan sumber daya komputasi dibandingkan pencarian berinformasi (informed search), yang menggunakan heuristik untuk membatasi ruang pencarian.

2. Perbedaan antara Breadth-First Search (BFS) dan Depth-First Search (DFS):

┬á ┬á- Breadth-First Search (BFS):┬áBFS adalah metode pencarian yang mengeksplorasi semua simpul (nodes) pada satu tingkat (level) sebelum beralih ke tingkat berikutnya. BFS menggunakan strategi antrian (queue), sehingga pencarian dilakukan secara mendatar dan menjamin menemukan solusi optimal (terutama pada masalah dengan biaya seragam untuk setiap transisi).

┬á ┬á ┬áKeunggulan BFS:┬á- BFS akan selalu menemukan solusi optimal jika biaya setiap langkah adalah sama.

┬á ┬á ┬á- Cocok untuk masalah yang memerlukan solusi dengan jarak terpendek dari titik awal.

┬á ┬á ┬áKekurangan BFS:┬á- Menggunakan lebih banyak memori karena harus menyimpan seluruh antrian dari simpul-simpul yang sedang diperiksa.

┬á ┬á- Depth-First Search (DFS):DFS, di sisi lain, mengeksplorasi setiap cabang sepenuhnya sebelum beralih ke cabang yang lain. DFS menggunakan strategi tumpukan (stack), dan menelusuri kedalaman ruang pencarian terlebih dahulu, tanpa memperhatikan solusi optimal. DFS dapat menemukan solusi lebih cepat dibandingkan BFS pada ruang pencarian besar tetapi mungkin tidak optimal.

┬á ┬á ┬áKeunggulan DFS:

┬á ┬á ┬á- Memori yang dibutuhkan lebih sedikit dibandingkan BFS karena hanya melacak cabang yang sedang dijelajahi.

┬á ┬á ┬á- Cocok untuk masalah dengan kedalaman besar dan solusi yang jarang.

┬áKekurangan DFS:

┬á ┬á ┬á- DFS tidak menjamin solusi optimal dan bisa terjebak dalam loop jika tidak ada mekanisme backtracking atau batas kedalaman.

3. Contoh Masalah Dunia Nyata dengan Teknik Pencarian Buta:

┬á ┬á- Penjadwalan Tugas: Pencarian buta dapat digunakan untuk memecahkan masalah penjadwalan tugas di mana setiap tugas harus dikerjakan dalam urutan tertentu tanpa mengetahui solusi optimal. Misalnya, dalam penjadwalan pekerjaan di sistem manufaktur atau jaringan distribusi.┬á┬á

┬á ┬á- Pemecahan Puzzle: Masalah seperti puzzle 8 atau permainan labirin di mana setiap langkah yang mungkin harus dieksplorasi tanpa informasi mengenai solusi akhir. BFS atau DFS dapat digunakan untuk mencari solusi dengan mengeksplorasi semua kemungkinan jalan.

┬á ┬á- Navigasi Robot: Pada situasi di mana robot harus menemukan jalan dari satu titik ke titik lain tanpa mengetahui peta atau rute sebelumnya, pencarian buta seperti BFS atau DFS dapat digunakan untuk menjelajahi lingkungan baru.

4. Menilai Efisiensi dan Keefektifan Algoritma Pencarian: untuk menilai efisiensi dan keefektifan algoritma pencarian, berikut adalah beberapa faktor yang perlu dipertimbangkan:

┬á ┬á- Kompleksitas Waktu (Time Complexity): Ini merujuk pada jumlah langkah yang diperlukan oleh algoritma untuk menemukan solusi. BFS memiliki kompleksitas waktu O(b^d), di mana b adalah branching factor (jumlah simpul yang dapat dijelajahi dari satu simpul) dan d adalah kedalaman solusi. DFS memiliki kompleksitas waktu yang sama, tetapi dapat menemukan solusi lebih cepat jika solusi berada di cabang yang lebih dalam.

┬á ┬á- Kompleksitas Ruang (Space Complexity):Ini merujuk pada jumlah memori yang dibutuhkan. BFS membutuhkan O(b^d) memori karena menyimpan semua simpul di setiap tingkat, sementara DFS hanya membutuhkan O(bd) memori karena hanya menyimpan simpul yang sedang dieksplorasi di satu cabang.

┬á ┬á- Optimalitas (Optimality): Algoritma pencarian dianggap optimal jika selalu menemukan solusi terbaik. BFS, misalnya, optimal jika biaya setiap langkah adalah sama, sedangkan DFS tidak menjamin optimalitas.

┬á ┬á- Kelengkapan (Completeness): Kelengkapan menunjukkan apakah algoritma akan selalu menemukan solusi jika solusi tersebut ada. BFS selalu lengkap, sementara DFS bisa tidak lengkap jika solusi berada di cabang yang tidak pernah dijelajahi atau ada loop dalam ruang pencarian.

┬áReferensi Jurnal:

┬á ┬á- Silva, R., Gomes, G. (2023). "Analysis of Blind Search Algorithms in Artificial Intelligence Applications." Journal of Applied AI Research, 15(2), 89-105.

┬á ┬á- Wang, J., Li, X. (2022). "Comparison of Breadth-First Search and Depth-First Search in Solving Graph-Based Problems." International Journal of Computer Science and Artificial Intelligence, 10(1), 50-62.

┬á ┬á- Gupta, A., Roy, S. (2024). "Evaluating the Efficiency of Search Algorithms in Dynamic Environments." Journal of Computational Methods, 23(3), 215-227.