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

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.

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.

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.

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

Algoritma Greedy terbaik pertama yang diimplementasikan oleh priority queue.

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.

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 :

Kelebihan :

Kekurangan :

Kelebihan :

Kekurangan :

Kelebihan :

Kekurangan :