Metode-metode Pencarian Buta atau Blind/Un Informed Search Pada Artificial Intelligence

Metode Searching atau pencarian sangat banyak yang dapat diusulkan dalam menyelesaikan masalah. Semua metode pencarian itu dibagi kedalam dua kategori yaitu pencarian buta/tanpa informasi (Bilnd/Un-Informed Seacrh) dan pencarian dengan informasi (Heuristik/Informed Search)

Kita akan membahas sedikit mengenai kategori Metode Blind/Un Informed Search. Istilah blind artinya buta, metode ini dikatakan metode pencarian buta karena tidak ada infomasi awal yang digunakan dalam proses pencarian ini.

Berikut beberapa metode pencarian Blind/Un Informed Search ;

1. Breadth First Search (BFS)

BFS adalah proses pencarian pada semua simpul dalam setiap level secara berurutan yaitu dari kiri ke kanan. Jika pada satu level solusi belum ditemukan, pencarian akan dilanjutkan pada level berikutnya. BFS menjamin ditemukan solusi(Jika solusinya memang ada) dan solusi yang ditemukan adalah yang paling baik. BFS bisa dikatakan Complete dan optimal namun BFS harus menyimpan semua simpul yang dibangkitkan, dan hal ini terus dilakukan agar BFS dapat menelusuri setiap simpul hingga level bawah, sehingga BFS membutuhkan memori yang banyak untuk menyumpan semua simpul.

Misalkan b adalah jumlah simpul anak yang dimiliki olh suatu simpul dan d adalah kedalaman solusi maka jumlah simpul yang harus disimpan adalah sebanyak 0(b^d)

Contoh perhitungan untuk b= 10 dan d=8 maka BFS harus menyimpan sebanyak 10⁰ + 10¹ + 10²+10³ +10⁴ +10⁵ +10⁶ +10⁷ +10⁸ = 111.111.111  10⁸simpul. Jika diasumsikan dalam satu detik komputer membangkitkan 10⁶ simpul maka proses yang diperlukan menemukan solusi pada level 8 ada;ah 1000 detik (1,67 menit) jika satu simpul 100 bytes maka butuh 10¹⁰ memori penyimpanan atau 10 gigabytes.

Gambar 1: Contoh Pencarian BFS untuk masalah jurigen air

2. Depth First Search (DFS)

DFS adalah proses pencarian pada suatu simpul dari yang paling kiri dalam setiap level. Jika solusi belum didapatkan pada level terdalam sebelah kiri maka proses pencarian dilanjutkan pada simpul sebelah kanan, dan simpul kiri dapat dihapus dari memori.

Pencarian akan dilanjutkan pada level sebelumnya jika solusi tidak ditemukan juga pada level paling dalam. DFS memiliki kelebihan yaitu pemakaian memori yang lebih sedikit karena DFS hanya akan menyimpan sekitar bd simpul. Berdasarkan contoh pada BFS harus menyimpan 10⁸ simpul, maka DFS hanya menyimpan  1+10 +10+10+10+10+10+10+10 = 81 simpul

Sedangkan kelemahan DFS adalah tidak menjamin menemukan solusi jika pohon yang dibangkitkan memiliki leve yang sangat dalam (tak terhingga) yang artinya DFS tidak complete.

Gambar 2 : Penelusuran DFS untuk masalah jurigen air

3. Depth Limited Search (DLS)

DLS adalah metode yang berusaha untuk mengatasai kekurangan dari DFS yaitu dengan membatasi kedalaman maksimum dari suatu jalur solusi. Sebelum menggunakan DFS harus tahu terlebih dahulu jumlah level maksimum dari suatu solusi. Jika batasan kedalam terlalu kecil dibandingkan dengan level solusinya DLS tidak akan menemukan solusi.

4. Uniform Cost Search (UCS)

Konsep pada UCS tidak jauh berbeda dengan BFS. Jika BFS menggunakan urutan level terendah sampai tinggi namun UCS menggunakan urutan biaya dari yang kecil ke yang terbesar. Melalui total biaya terendah yang dihitung berdasarkan biaya dari simpul asal hingga tujuan UCS akan berusaha menemukan solusi.

Gambar a : Sebuah masalah pencarian rute dari kota S menuju G. Pada masalah ini digunakan basis data berupa biaya antara satu kota dengan kota lainnya.

Gambar b : Pembangkitan pohon menggunakan UCS. Angka pada setiap simpul menyatakan biaya atau g(n). Pada akhirnya UCS menemukan S-B-G sebagai rute dengan biaya minimum yaitu 10.

5. Interative Deepening Search (IDS)

Konsep IDS adalah menggabungkan kelebihan BFS yaitu Complet dan Optimal dengan kelebihan DFS yaitu hanya membutuhkan sedikit memori. Namun konsekuensinya adalah time complexitynya menjadi tinggi.

6. Bi Directional Search (BDS)

BDS adalah pencarian dua arah yaitu pencarian maju dan pencarian mundur.  Solusi telah ditemukan ketika dua arah pencarian membangkitkan simpul yang smaa dengan cara menggabungkan kedua jalur bertemu.

Itulah beberapa metode pencarian buta atau Blind/Un Informed Search pada Artificial Intelligent. Semoga bermanfaat.

#GarudaCyber23April/Ulti