LANZURI.COM: Pengertian algoritma: Algoritma Backtracking, Algoritma String Matching google.com, pub-8290688651244715, DIRECT, f08c47fec0942fa0

Monday, March 25, 2019

Pengertian algoritma: Algoritma Backtracking, Algoritma String Matching


Pengertian algoritma

Yang dimaksud dengan algoritma adalah urutan-urutan langkah yang dinyatakan dengan cara jelas dan tidak rancu/ambigu untuk memecahkan suatu permasalahan jika ada pemecahannya dalam rentang waktu tertentu. Artinya, setiap langkah harus dapat dikerjakan dan mempunyai efek tertentu. Arti yang lebih modern untuk algoritma agak mirip kepada kata resep, proses, metode, teknik, prosedur, rutin, kecuali bahwa kata “algoritma” itu sendiri memiliki arti sesuatu yang sedikit berbeda.

Komponen Utama Dalam Algoritma yaitu:

1. Finiteness.
algoritma harus selalu berada diakhir setelah sejumlah langkah berhingga.
2. Definiteness.
Setiap-tiap langkah dari sebuah algoritma harus diartikan secara tepat, tindakan
yang di muat harus dengan teliti dan sudah jelas ditentukan untuk setiap keadaan.
3. Input.
Algoritma mempunyai nol atau lebih masukan atau disebut input, sebagai contoh, banyaknya
masukan diberikan di awal sebelum algoritma mulai.
4. Output.
Algoritma mempunyai satu ataupun lebih keluaran, sebagai contohnya, banyaknya
keluaran memiliki hubungan yang ditentukan terhadap masukan.
5. Effectiveness.
Pada umumnya sebuah algoritma juga diharapkan untuk efektif.


Pengertian Algoritma Backtracking

Salah satu algoritma yang dapat dipakai untuk mempermudah pencarian anagram suatu kata adalah algoritma backtracking. Selain algoritma bactracking, pembuatan anagram juga membutuhkan algoritma string matching yang tepat, karena kata-kata dalam sebuah anagram harus memiliki makna, dalam hal ini algoritma string matching yang tepat dapat membantu untuk mencari kata yang dibuat dalam database kamusyang tersedia, sehingga anagram dapat dibuat dengan lebih cepat dan efektif.

Algoritma backtracking pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Golomb, dan Baumert menyajikan uraian umum tentang backtracking dan penerapannya dalam berbagai persoalan dan aplikasi. Algoritma backtracking atau runut balik merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada (Aho, Hopcroft, dan Ullman, 1983, hal:327). Sebab itu algoritma ini berbasis pada algoritma Depth-First Search (DFS), maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar secara preorder.

Algoritma backtracking mempunyai prinsip dasar kemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebut secara DFS sampai ditemukan solusi yang layak. Nama backtrack didapatkan dari sifat algoritma ini yang memanfaat karakteristik himpunan solusinya yang sudah disusun menjadi suatu pohon solusi.

Penggunaan terbesar backtrack adalah untuk membuat AI (Artificial Intelligence) pada board games. Dengan algoritma backtracking ini program dapat menghasilkan pohon sampai dengan kedalaman tertentu dari current status dan memilih solusi yang akan membuat langkah-langkah yang dapat dilakukan oleh user akan menghasilkan pohon solusi baru dengan jumlah pilihan langkah terbanyak..

kegunaan yang paling terkenal dari algoritma backtrack dari suatu masalah “statik” adalah untuk memecahkan masalah N-Queen problem dan maze solver. Apakah itu yang dimaksud dengan N-Queen problem adalah bagaimana cara meletakkan bidak Queen catur sebanyak N buah pada papan catur atau pada papan ukuran NxN sedemikian rupa sehingga tidak ada satu bidak pun yang mampu memangsa bidak lainnya dengan saru gerakan. Meskipun mungkin terdapat lebih dari satu solusi untuk masalah ini, tetapi pencarian semua solusi biasanya tidak terlalu diperlukan, tetapi untuk beberapa kasus tertentu diperlukan pencarian semua solusi sehingga didapatkan solusi yang optimal.

Maze solver ialah bagaimana cara menemukan/mencari jalan keluar dari suatu maze atau labirin yang diberikan. Pada maze yang sederhana dimana field yang dibentuk dapat direpresentasikan dalam bentuk biner dan pada setiap petak maksimal terdapat 4 kemungkinan: atas, kanan, bawah, dan kiri. Untuk masalah ini biasanya solusi pertama yang ditemukan bukanlah solusi yang paling optimal sehingga untuk mendapatkan hasil yang optimal dibutuhkan pencarian terhadap seluruh kemungkinan solusi. Hal ini disebabkan oleh urutan pencarian yang telah ditetapkan dalam program apakah menyelidiki kemungkinan ke arah atas dahulu atau ke arah lainnya dahulu (Putra, Sardjito, Lawrence, 2006, hal:1).

Algoritma String Matching (Pencocokan String)

Algoritma string matching adalah sebuah algoritma yang digunakan dalam pencocokkan suatu pola kata tertentu terhadap suatu kalimat atau teks panjang. Algoritma string matching sendiri dapat dilakukan dengan beberapa cara tertentu, antara lain cara Brute Force dan cara Knuth-Morris-Pratt (KMP) (Brassard dan Bratley, 1988, hal:211).

Algoritma-algoritma pencocokan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya, yaitu :

1.Dari yang paling alami, dari sebalah kiri ke sebelah kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:
a)Algoritma Brute Force
Cara Brute Force dilakukan dengan membandingkan seluruh elemen karakter pada pola dengan kalimat atau teks panjang, dimulai pada elemen karakter pertama pada kalimat tersebut. Jika tidak sesuai maka pembandingan dimulai dengan elemen kedua dari kalimat tersebut.
b) Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt Cara KMP dilakukan dengan menghitung fungsi pinggiran dari pola terlebih dulu dan kemudian akan dilakukan perbandingan antara pola dan elemen pertama dari kalimat, jika tidak sesuai, maka perbandingan tidak dilakukan pada elemen kedua, namun tergantung dari nilai yang akan dikeluarkan oleh fungsi pinggiran tersebut (Baase, 1988, hal:213).

2.Dari sebelah kanan ke sebelah kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah: Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka

3.Dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:
a)Algoritma Colussi
b)Algoritma Crochemore-Perrin

pembahasan diatas merupakan pengertian dan penjelasan tentang pengertian algoritma, komponen algoritma, Algoritma backtracking serta pengertian dan penjelasan dari Algoritma String Matching (Pencocokan String).

No comments:

Post a Comment