Pengertian dan Contoh Algoritma Generate and Test

Dalam bidang ilmu Artificial Intelligence atau kecerdasan buatan, metode pencarian dan pelacakan merupakan suatu hal penting dalam suatu sistem. Karena pencarian dan pelacakan ini adalah hal yang menentukan keberhasilan sistem tersebut.

Sebuah algoritma pencarian bermakna sebagai sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat berdasarkan evaluasi dari beberapa kemungkinan solusi.

Masalah pencarian merupakan masalah yang umum diterapkan pada sistem kecerdasan buatan. Salah satu metode pencarian heuristik dalam terminologi kecerdasan buatan yang cukup dikenal adalah Generate and Test.

Daftar Isi

Definisi Generate and Test

Algoritma Generate and Test merupakan algoritma paling sederhana dalam teknik pencarian heuristik. Generate and test adalah suatu teknik penyelesaian masalah pada komputer dengan cara menyusun daftar penyelesaian yang mungkin dan menguji satu persatu untuk menentukan solusi yang tepat.

Dalam Generate and Test, terdapat dua prosedur penting yaitu generate (membangkitkan) yaitu membangkitkan semua solusi yang mungkin dan test (pengujian) yaitu menguji solusi yang dibangkitkan tersebut.

Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Nilai pengujiannya berupa jawaban “YA” atau “TIDAK”.

Metode penelusuran depth-first search adalah metode penelusuran yang dimulai dari akar (level 0) dan penelusuran dilanjutkan dengan melacak node yang berada paling kiri pada level dibawahnya sampai level paling bawah. Apabila tidak ditemukan goal, maka penelusuran dilanjutkan pada level satu dan terus menuju level yang paling bawah, sampai ditemukan goal. 

Backtracking merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian dalam ruang status. Backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada.

Backtracking ini berbasis pada algoritma DFS (Depth First Search). Prinsip dasar backtracking adalah mencoba semua kemungkinan solusi yang ada. Pada konsep dasarnya backtracking semua solusi dibuat dalam bentuk pohon solusi dan kemudian pohon tersebut ditelusuri secara DFS sehingga ditemukan solusi yang terbaik yang diinginkan.

Flowchart Algoritma Generate and Test

Alur untuk Generate and Test tersebut adalah :  

1. Bangkitkan suatu solusi yang mungkin. Untuk beberapa permasalahan, pembangkitan ini berarti membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal. 
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya. Caranya dengan membandingkan titik yang dipilih atau titik akhir suatu lintasan yang dipilih dengan kumpulan tujuan yang dapat diterima atau diharapkan. 
3. Jika solusi telah diperoleh maka keluar. Jika tidak, maka ulangi kembali langkah pertama. 

Contoh Penerapan Algoritma Generate and Test

Contoh implementasi algoritma pada aplikasi penentuan identitas kalimat bahasa Arab. Aplikasi pembelajaran ini kalimat bahasa Arab akan dipecah berdasarkan spasi menjadi perkata, kemudian setiap kata akan dicari ciri-cirinya menggunakan metode Generate and Test.  

Alur proses aplikasi penentuan identitas kalimat bahasa Arab yaitu pengguna memasukkan kalimat bahasa Arab yang benar kemudian kalimat tersebut dipecah berdasarkan spasi menjadi per kata, selanjutnya setiap kata dicocokkan dengan kata pengecualian, jika benar maka selesai jika tidak maka dicari ciri-ciri identitas kata yang sesuai dengan kaidah yang telah dimasukkan dalam sistem menggunakan metode Generate and Test.

Berikut flowchart aplikasi penentuan identitas kalimat bahasa Arab pada jumlah ismiyah:

Alur dalam flowchart di atas memodelkan masukan ke sistem dan keluaran dari sistem dalam aplikasi penentuan identitas kata bahasa Arab pada jumlah ismiyah ini. Berikut penjelasan diagram tersebut:  

1. Input kalimat  

Masukan berupa kalimat bahasa Arab dengan susunan jumlah ismiyah yang benar.  

2. Pemecahan kalimat  

Pada proses ini kalimat yang diinputkan akan dipecah berdasarkan spasi menjadi perkata.  

3. Pengecekan kata pengecualian  

Contoh: محمد , مكة  

Pada proses ini setiap kata akan di cek menggunakan metode Generate and Test apakah kata tersebut termasuk pada kata pengecualian.  

4. Pencocokan ciri identitas kata bahasa Arab  

Pada proses ini setiap kata akan di cek ciri-cirinya apakah sesuai dengan kaidah nahwu menggunakan metode Generate and Test kemudian akan diketahui identitas kata tersebut beserta penjelasannya. Pada proses ini penentuan ciri-ciri identitas kata bahasa Arab terbagi menjadi empat, yaitu: identitas kata, bilangan kata, jenis kata, dan kedudukan kata didalam kalimat.  

5. Menampilkan hasil output program  

Output dari aplikasi ini adalah pejelasan tentang identitas kata bahasa Arab sesuai dengan kaidah Nahwu atau ciri identitas kalimat bahasa Arab. 

Rancangan Generate and Test 

Algoritma Generate and Test pada sistem ini bisa digambarkan dalam flowchart berikut: 

Permasalahan dalam aplikasi penentuan identitas kata bahasa Arab ini adalah bagaimana cara mengidentifikasi karakter atau ciri-ciri yang ada pada kata, lalu ditentukan identitas kata sesuai dengan ciri-ciri kata tersebut.

Pada contoh ini metode Generate and Test diterapkan pada dua permasalahan yaitu pencarian ciri-ciri identitas kata bahasa Arab yang sesuai dengan kaidah yang telah ditetapkan dalam sistem dan pelacakan kata pengecualian.

Berikut ciri-ciri identitas kata pada aplikasi penentuan identitas kalimat bahasa Arab pada jumlah ismiyah berdasarkan kitab nahwu wadhih:

Trivusi Ikatlah ilmu dengan menulis. Menebar manfaat dengan berbagi :)

Berbagi :