Blind Search AI

BLIND SEARCHING

Blind Search merupakan pencarian asal yaitu, jika solusi pencarian sudah ditemukan, maka pencarian akan dihentikan.

Skema pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi].

Metode Pencarian Buta(Blind Search)

BFS (Breadth – First Search) : Metode ini akan mulai mencari dari node yang paling kiri, kemudian berpindah ke-node se-level dengannya, dan berulang – ulang terus hingga menemukan solusi yang dimaksud.

Keuntungannya :

• Tidak menemui jalan buntu.
• Jika ada suatu solusi, maka Breadth-first search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.

 

Kelemahannya :

• TABLE I. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.
• TABLE II. Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke-(n + 1).

DFS (Depth-first Search) : Metode ini sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.

Contoh Penerapan BFS & DFS

Studi Kasus : Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.

Permasalahannya : adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.

Deskripsi

P = Petani

Sy = Sayuran

K = Kambing

Sg = Serigala

Ruang Keadaan

Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)

Keadaan Awal

Daerah Asal = (P, Sy, K, Sg)

Daerah seberang = (0, 0, 0, 0)

Tujuan

Daerah Asal = (0, 0, 0, 0)

Daerah seberang = (P, Sy, K, Sg)

Metode Penyelesaian :

a. Berikut ini adalah algoritma BFS :

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
4. Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.

b. Menggunakan algoritma DFS :

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
4. Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.

Heuristic Searching AI

Sumber:

https://ululazmisetiawan.wordpress.com/2017/12/05/blind-searching-and-heuristic-searching/