Hai Sobat LITE, Apa kalian sudah tau nih contoh penerapan pencarian algoritma pada strategi Uninformed Search? Nah, sebelumnya kalian harus tahu dulu nih apa sih Searching yang dimaksut dalam algoritma itu?
Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.
Pada Algoritma searching di dalam kecerdasan buatan terbagi menjadi 2 nih, diantaranya yaitu Uninformed Search Algorithm dan Informed Search Algorithm. Kali ini kita akan fokus pada contoh penerapan pencarian algoritma pada Uninformed Search nih.
1. Breadth First Search (BFS)
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul - simpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerluka-n sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.
- Contoh Penerapan
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.
Deskripsi
- P = Petani
- Sy = Sayuran
- K = Kambing
- Sg = Serigala
- 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 Penyelesaiannya :
- 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.
2. Uniform Cost Search (UCS)
Uniform Cost Search adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).
Dalam implementasi algoritma ini , melibatkan semua node yang berhubungan dengan root node, dan meletakannya dalam priority queue untuk mencapai node tujuan. Dimana node – node yang dipilih merupakan node yang berharga terkecil.
Ilustrasi jalannya algoritma Uniform Cost Search dapat digambarkan sebagai berikut :
Seperti tampak pada gambar, initial state terletak pada node start, kemudian untuk mencapai node berikutnya, algoritma ini memilih jalur yang memilki harga terkecil diantara dua node di depannya. Begitu seterusnya, dilakukan pengecekan node yang memilki harga terkecil hingga sampai pada goal state.
- Contoh Penerapan
Pada permasalahan diatas telah ditentukan jarak antara node. maka pada ucs akan membuka node yang memiliki nilai/cost antar node yang terendah. Pada gambar diatas jika kita buka
Karena nilai c dan a sama maka teserah mau buka yang mana lebih dahulu. Seandainya kita mebuka c maka kita teruskan pencariannya, jika kita buka
maka kita buka node d, lalu akan didapat
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a setelah kita buka node a akan di dapat
dari kasus diatas dapat kita lihat, ada banyak cara unuk mendapatkan solusi. namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari UCS.
3. Depth First Search (DFS)
Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
- Contoh Penerapan
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.
- 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 Penyelesaiannya :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
- 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
4. Depth Limited Search
Depth Limited Search merupakan salah satu algoritma pencarian dalam menemukan solusi dengan pencarian yang berusaha mengatasi kelemahan DFS dengan membatasi kedalaman maksimum. Algortima ini dijalankan dengan membangkitkan pohon pencarian secara dinamis. Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree.
Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisialisasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor. Sebelum menggunakan DLS, terlebih dahulu harus diketahui berapa level maksimum dari suatu solusi.
Langkah-langkah dalam Dept Limited Search adalah sebagi berikut:
- Pertama yaitu tentukan kedalaman simpul yang akan dicari
- Kunjungi simpul a atau simpul awal.
- lalu kunjungi simpul b yang bertetangga dengan simpul a, yang berada di kedalaman pohon <= batas.
- Ulangi Dept Limited Search mulai dari simpul b ke simpul yang bertetangga. (Mencari simpul dari atas kebawah lalu ke tetangga dari b dst.)
- Ketika mencapai simpul kedalaman s sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir.
- Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi dalam kedalaman ponon <= batas.
- Contoh Penerapan
Bila simpul awal adalah 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 4, 8, 5, 3, 6,.7
Penjelasan secara singkat adalah jika kedalaman 3 adalah 5,6,7 maka untuk sampai pada kedalaman 3 simpul-simpul mana saja yang akan dilalui untuk pertama yaitu 1,2,5 lalu simpul kedua yaitu 1,3,6 dan ketiga adalah 1,4,7 dan hasil akir ditulis satu kali saja tidak perlu mengulang angka. Maka hasilnya adalah 1,2,3,4,5,6,7.
5. Iterative Deepening Search
Iterative Deepening search merupakan metode yang berusaha menggabungkan keuntungan BFS (Complete dan Optimal) dengan keuntungan DFS (Space Complexity yang rendah). Tetapi konsekuensinya adalah Time Complexity-nya menjadi tinggi. Perhatikan gambar 1
Pencarian dilakukan secara iteratif (menggunakan penelusuran DFS) dimulai dari batasan level 1. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 2. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
- Contoh Penerapan
.png)
Carilah rute untuk mencapai kota Bucharest dari kota Arad!
.png)
Pada contoh kasus kali ini solusi akan ditemukan pada level ke 4 atau pada saat iterasi dari ℓ sama dengan 4. seperti berikut
.png)
