Informatika XI. Berbagai Algoritma untuk Menyelesaikan Masalah

Berbagai Algoritma untuk Menyelesaikan Masalah


1. Algoritma Rekursi

Rekursi adalah fungsi yang memanggil dirinya sendiri sebagai subprogram untuk menyelesaikan program yang kompleks. Pada metode perulangan (iterasi), satu proses dapat dilakukan secara berulang-ulang (dalam bentuk perulangan) untuk menyelesaikan suatu masalah. Rekursi bekerja dengan cara berbeda. Rekursi melakukan pendekatan penyelesaian masalah dengan cara membuat suatu fungsi yang menjalankan suatu proses, kemudian proses tersebut dipanggil oleh dirinya sendiri secara berulang-ulang. Proses suatu fungsi memanggil dirinya sendiri dikenal dengan proses rekursi dan fungsi yang memanggil dirinya sendiri disebut dengan fungsi rekursif.


2. Algoritma Greedy

Kata greedy dalam bahasa Indonesia artinya tamak, sesuatu yang negatif. Namun dalam pemrograman, greedy diartikan sebagai mendapatkan hasil yang maksimal. Algoritma greedy adalah algoritma yang mempunyai pendekatan sederhana dan efisien untuk menyelesaikan permasalahan yang diberikan dengan cara membuat pilihan terbaik setiap waktu, tanpa memikirkan hasil akhir. Ketika bekerja, ada dua prinsip yang mendasari algoritma greedy, yaitu:

a. jika dalam setiap langkah membuat pilihan terbaik, maka hasil akhir akan memberikan hasil yang terbaik juga,

b. algoritma greedy tidak mengenal adanya reverse atau mengubah keputusan yang sudah dibuat, karena itu algoritma greedy akan bekerja menyelesaikan permasalahan dari arah atas ke bawah (top-bottom).


3. Algoritma Pemrograman Dinamis

Algoritma pemrograman dinamis (dynamic programming) adalah sebuah algoritma teknik optimalisasi yang digunakan untuk menyelesaikan masalah kompleks dengan cara memecah-mecah masalah kompleks menjadi masalah yang lebih kecil dan sederhana. Algoritma ini sepintas terlihat sama dengan algoritma divide and conquer, tetapi keduanya memiliki perbedaan. Pada agloritma divide and conquer masalah dipecah dan diselesaikan secara independen, kemudian solusi-solusi tersebut dikombinasikan sehingga menjadi satu solusi besar yang utuh. Sedangkan, pada algoritma dynamic programming, masalah dipecah-pecah menjadi masalah kecil yang memiliki ketergantungan (keterkaitan) antara yang satu satu dengan yang lain (dependent).

Cara kerja dari dynamic programming dapat dibagi menjadi tiga tahapan logika.

a. Memecah masalah. Algoritma akan memecah masalah menjadi submasalah yang lebih kecil dan sederhana.

b. Menyelesaikan masalah. Algoritma kemudian melakukan proses perulangan untuk menyelesaikan submasalah. Solusi dari setiap submasalah kemudian disimpan. Proses menyimpan solusi dari submasalah tersebut dikenal dengan istilah memoization. Setiap solusi dari submasalah akan digunakan kembali jika diperlukan ketika harus menyelesaikan masalah yang sama.

c. Menyelesaikan masalah utama. Sebagai langkah akhir, algoritma akan mengidentifikasi dan menyelesaikan masalah utama.


4. Algoritma Divide and Conquer

Sesuai dengan namanya, algoritma divide and conquer (pecah dan selesaikan) adalah algoritma yang bekerja dengan cara memecah masalah yang besar dan kompleks menjadi bagian-bagian kecil, menyelesaikan masalah tersebut secara independen, kemudian menyatukan solusi-solusinya. Teknik pemecahan masalah ini membuat algoritma divide and conquer mampu menyelesaikan hampir semua masalah dengan baik. Meskipun dalam pencarian solusi sama-sama memecah masalah kompleks menjadi submasalah yang lebih kecil, algoritma divide and conquer memiliki perbedaan dengan algoritma pemrograman dinamis. Pada algoritma pemrograman dinamis, solusi dari submasalah digunakan untuk menyelesaikan masalah utama, sedangkan pada algoritma divide and conquer, solusi dari submasalah merupakan bagian dari solusi masalah utama.

Ketika menyelesaikan masalah, algoritma divide and conquer mempunyai tiga tahapan berikut.

a. Memecah masalah (divide). Pada tahap ini, algoritma memecah masalah menjadi bagian-bagian yang lebih kecil. Dengan demikian, masalah menjadi lebih sederhana dan mudah diselesaikan. Tahapan memecah masalah dapat dilakukan berkali-kali sampai masalah cukup kecil dan sederhana.

b. Selesaikan (conquer). Pada tahap ini, masing-masing masalah diselesaikan secara independen. Jika memungkinkan masalah dapat diselesaikan secara paralel.

c. Menyatukan solusi. Pada tahap ini, masing-masing solusi yang diperoleh dari bagian-bagian masalah disatukan sehingga menjadi solusi yang utuh dari keseluruhan masalah yang ada.


5. Algoritma Runut Balik

Algoritma runut balik (backtracking) adalah algoritma yang bekerja dengan cara menguji setiap kemungkinan solusi sampai ditemukan solusi yang terbaik dari sebuah permasalahan. Disebut runut balik karena algoritma ini akan melakukan perunutan balik ke tingkat keadaan sebelumnya, jika ditemukan penelusuran yang dilakukan bukan solusi yang diinginkan.

Share this post