Materi tentang Uninformed dan Informed Search pada Algoritma Kecerdasan Buatan (AI) (+ Video Materi)

Assalamu‘alaikum wr. wb.

Halo gais! Jika sebelumnya telah membahas tentang Apa itu Kecerdasan Buatan atau Artificial Intelligence. Sekarang, waktunya kita membahas tentang Algoritma Dasar dalam AI, yaitu Uninformed dan Informed Search.

Ilustrasi Uninformed dan Informed Search pada Algoritma Kecerdasan Buatan (AI)

PENGERTIAN

Sumber Materi : Radenrakha.blogspot.com dan Trivusi.web.id

A. Informed Search

Teknik pencarian Informed Search menggunakan informasi spesifik atau informasi tambahan untuk memberikan saran tentang cara memecahkan masalah. Jenis strategi pencarian ini sebenarnya mencegah algoritme tersandung saat melacak tujuan atau arah ke solusi yang diharapkan.

Informed Search memiliki keunggulan biaya ketika optimalitas dicapai dengan biaya pencarian yang lebih rendah. Temukan biaya jalur optimal dalam grafik dengan menerapkan strategi yang memasukkan node n paling menjanjikan ke dalam Fungsi Heuristik h(n).

Kemudian fungsi mengembalikan bilangan real non-negatif yang merupakan estimasi biaya jalur yang dihitung dari node n ke node tujuan n. Bagian terpenting dari teknik Informed Search di sini adalah fungsi Heuristik yang memungkinkan algoritma mendapatkan informasi tambahan tentang masalah tersebut.

Ini membantu menemukan jalur ke tujuan melalui node tetangga yang berbeda. Algoritma yang termasuk dalam Informed Search, di antaranya: heuristic depth-first, heuristic breadth-first search, greedy search, graph search, dan A* search.

B. Uninformed Search

Berbeda dengan Informed Search, Uninformed Search melakukan pencarian dengan cara hanya memberikan definisi masalah tetapi tidak ada langkah lebih lanjut untuk menemukan solusi untuk masalah tersebut.

Tujuan utama dari pencarian jenis ini adalah untuk membedakan antara keadaan target dan non-target sampai menemukan tujuan dan melaporkan penerusnya. Strategi ini juga dikenal sebagai pencarian buta (blind search).

Adapun contoh algoritma pencarian uninformed search adalah Depth First Search, Uniform Cost Search, dan Breadth First Search.

PERBANDINGAN (JENIS-JENIS)

Sumber Materi : Javatpoint.com (Uninformed Search Algorithm), Javatpoint.com (Informed Search Algorithm), Radenrakha.blogspot.com, Socs.Binus.ac.id, Geeksforgeeks.org

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.

A. Informed Search

1. Greedy Best First Search

Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

Proses ekspansi dengan menggunakan algoritma Greedy Best First Search adalah dengan merujuk pada nilai estimasinya yaitu h(n). Berbeda halnya dengan nilai g(n) yang diakumulasikan, nilai h(n) tidak diakumulasikan. Proses eksplorasi akan berjalan seperti berikut ini :

f = {S};
f = {A, C, K};       // 2, 4, 5
f = {B, C, K};       // 3, 4, 5
f = {G, C, H, K};    // 0, 4, 4, 5
f = {C, H, K};       // 4, 4, 5

Proses yang dilakukan pada Greedy Best First Search sama seperti Uniform Cost Search, namun parameter yang digunakan hanya nilai estimasinya.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 4 kali, dan path yang dilalui dengan menggunakan algoritma Greedy Best First Search adalah S-A-B-G.

Dengan bantuan pencarian terbaik pertama, pada setiap langkah, kita dapat memilih simpul yang paling menjanjikan. Dalam algoritme pencarian pertama terbaik, kami memperluas simpul yang paling dekat dengan simpul tujuan dan biaya terdekat diperkirakan dengan fungsi heuristik, yaitu :

f(n)= g(n)

Di mana, h(n)= perkiraan biaya dari node n ke tujuan.

Algoritma Greedy terbaik pertama yang diimplementasikan oleh priority queue.

2. A* Search (A-Star Search) Algorithm

Eksplorasi node dari metode A* dilakukan dengan cara menjumlahkan kombinasi nilai path g(n) dan nilai estimasi h(n). Penjumlahan dari nilai tersebut akan dibandingkan untuk menentukan node mana dulu yang akan dieksplorasikan. Prosesnya akan berjalan sebagai berikut ini :

f = {S};
f = {A, C, K};  // 4, 5, 7
f = {C, K, B};  // 5, 7, 7
f = {D, K, B};  // 5, 7, 7
f = {E, K, B};  // 5, 7, 7
f = {F, K, B};  // 5, 7, 7
f = {G, K, B};  // 5, 7, 7
f = {K, B};     // 7, 7

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 7 kali, dan path yang dilalui dengan menggunakan algoritma A* Search adalah S-C-D-E-F-G.

Dalam algoritma pencarian A*, kita menggunakan Heuristik pencarian serta biaya untuk mencapai node. Oleh karena itu kami dapat menggabungkan kedua biaya sebagai berikut, dan jumlah ini disebut sebagai Angka Kebugaran (Fitness Number).

Untuk melihat Program untuk A* Algorithm, silakan lihat di sini (Geeksforgeeks.org).

B. Uninformed Search

Algoritma ini tidak memberikan informasi apapun tentang permasalah yang ada, tetapi hanya berfokus memberikan informasi tentang algorima tersebut. Algoritma ini juga disebut Blind Search. Istilah Blind Search berpedoman bahwa, teknik pencarian ini tidak memiliki informasi tambahan lain selain dari yang disediakan.

Yang dilakukan oleh algorima ini adalah melakukan generate dari successor dan membedakan goal state dari non-goal state. Pencarian ini dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.

Adapun macam-macam Uninformed Search Algorithm adalah sebagai berikut :

1. Breadth First Search (BFS)

Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

Penelusuran Ekspansi Node pada Breadth First Search (BFS)

Kelebihan :

• BFS akan memberikan solusi jika ada solusi.
• Jika ada lebih dari satu solusi untuk masalah yang diberikan, maka BFS akan memberikan solusi minimal yang membutuhkan langkah paling sedikit.

Kekurangan :

• Ini membutuhkan banyak memori karena setiap level pohon harus disimpan ke dalam memori untuk memperluas level berikutnya.
• BFS membutuhkan banyak waktu jika solusinya jauh dari simpul akar.

Untuk melihat Program untuk Breadth First Search (BFS), silakan lihat di sini (Geeksforgeeks.org).

2. 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.

Penelusuran Ekspansi Node pada Depth First Search (DFS)

Kelebihan :

• DFS membutuhkan lebih sedikit memori karena hanya perlu menyimpan setumpuk node di jalur dari node root ke node saat ini.
• Dibutuhkan lebih sedikit waktu untuk mencapai node tujuan daripada Algoritma BFS (jika melintasi jalur yang benar).

Kekurangan :

• Ada kemungkinan banyak negara terus berulang, dan tidak ada jaminan untuk menemukan solusinya.
• Algoritma DFS digunakan untuk pencarian jauh ke dalam dan kadang-kadang mungkin menuju loop tak terbatas.

Untuk melihat Program untuk Depth First Search (DFS), silakan lihat di sini (Geeksforgeeks.org).

3. Uniform Cost Search (UCS)

Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.

Selain menjalankan fungsi Algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

Kelebihan :

• Pencarian biaya seragam optimal karena pada setiap keadaan jalan dengan biaya paling sedikit dipilih.

Kekurangan :

• Itu tidak peduli dengan jumlah langkah yang terlibat dalam pencarian dan hanya memperhatikan biaya jalur. Karena itu, algoritma ini mungkin macet dalam loop tak terbatas.

Untuk melihat Program untuk Uniform Cost Search (UCS), silakan lihat di sini (Geeksforgeeks.org).

4. Depth Limited Search

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.

Kelebihan :

• Pencarian dengan kedalaman terbatas hemat memori.

Kekurangan :

• Pencarian dengan kedalaman terbatas juga memiliki kelemahan berupa ketidaklengkapan.
• Mungkin tidak optimal jika masalahnya memiliki lebih dari satu solusi.

VIDEO

Untuk memahami lebih lanjut terkait dengan Uninformed dan Informed Search, lihatlah Video-video YouTube di bawah ini.

Itulah Materi tentang Uninformed dan Informed Search pada Algoritma Kecerdasan Buatan (AI) yang telah saya paparkan. Mohon maaf apabila ada kesalahan apapun. 

Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.