BLIND SEARCH
Metode pencarian dan pelacakan adalah hal penting dalam kecerdasan buatan atau kita sebut dengan AI. Dalam kecerdasan buatan lebih di fokuskan dalam hal pencarian, karena AI harus dapat mencari solusi / jawaban atas suatu permasalahn dalam sekumpulan kemungkinan ruang keadaan.
Di dalam kecerdasan buatan kita mengenal 2 metode pencarian dan pelacakan diantaranya adalah :
1) Pencarian buta(Blind Search) : Dalam metode pencarian buta ini dibagi menjadi 2 yaitu :
Breadth - First Search : Metode ini akan mulai mencari dari node yang paling kiri, kemudian berpindah ke-node se-level dengannya, dan berulang - ulang trus hingga menemukan solusi yang dimaksud.
- Keuntungan metode Breadth First Search adalah : pasti menemukan solusi yang dicari, tidak akan mengalami jalan buntu / tidak menemukan solusi.
- Kelemahan metode Breadth-First Search adalah : memerlukan memori yang cukup besar, karena metode ini mengecek keseluruhan node yang ada dan membutuhkan waktu yang lebih untuk mengecek semua node yang ada tersebut.
Depth First Search : Metode ini dimulai dari semua node-node anaknya kemudian berpindah ke node-node se-level nya.
Keuntungan metode Depth First
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi
Kekurangan metode Depth First
- Memungkinkan tidak ditemukannya tujuan yang diharapkan
- Hanya akan mendapatkan 1 solusi pada setiap pencarian
2) Pencarian terbimbing (Heuristic search) : Dalam metode pencarian terbimbing atau kita sebut Heuristic search terbagi menjadi 4 macam yaitu :
- Pembangkit & Pengujian
- Hill Climbing
- Best First Search (BFS)
- Simulated Annealing
Pembangkit & Pengujian
Pembangkit & Pengujian : Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Terdapat kelemahan dalam metode ini :
- Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
- Membutuhkan waktu yang cukup lama dalam pencariannya
Hill Climbing
Hill Climbing adalah metode ini hampir sama dengan metode pembangkitan & pengujian, namun memiliki perbedaan dalam hal proses pengujian dilakukan. Hill Climbing menggunakan fungsi heuristik dalam hal pencarian.
Algoritma Simple Hill Climbing :
1.Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2.Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
3.Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
4.Evaluasi keadaan baru tersebut.
5.Jika keadaan baru merupakan tujuan, keluar.
6.Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7.Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Algoritma Steepest Ascent Hill Climbing :
Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.
Contoh Penerapan BFS
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 :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- 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.
- Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
ABOUT THE AUTHOR
Jika ada pertanyaan tentang artikel diatas mohon untuk berkomentar dibawah, terima kasih sudah membaca artikel ini jangan lupa untuk subscribe atau follow blogger gue ya!
0 komentar:
Posting Komentar