Strategi Algoritma dan Macam-macam Algoritma
Sebelum kita mengenal Strategi Algoritma, maka kita perlu mnegenal pengertian dari masing-maasing kata di atas.
- Strategi: adalah rencana yang cermat mengenai kegiatan untuk mencapai sasaran khusus (KBBI).
- Algoritma: adalah urutan langkah-langkah yang benar untuk memecahkan suatu masalah secara komputasi.
Jadi Strategi Algoritma adalah Kumpulan metode atau tekhnik untuk memcahkan masalah, guna mencapai yang ditentukan, yang dalam hal ini deskripsi metode atau teknik tersebut dinyatakan dalam suatu urutan langkah-langkah komputasi yang benar dlm penyelesaian masalah.
Tujuan Strategi Algoritma
Ada dua alasan (Levitin, 2003):
1. Memberikan panduan (guidance) untuk merancang algoritma bagi persoalan baru.
2. Dapat mengklasifikasikan algoritma berdasarkanm gagasan perancangan yang mendasarinya.
Strategi Umum Algoritma
Ada beberapa strategi algoritma yang diakui secara umum. Strategi ini dapat digunakan tergantung tujuan objektif, antara lain Divide and Conquer, Greedy, Dynamic Programming, dan Minimum Spanning Tree/MST.
Devide and Conquer
Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :
- Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
- Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
- Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Skema umum divide and conquer :
Penerapan Algoritma :
Persoalan Minimum dan Maksimum
Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :
Ide dasar algoritma secara divide and conquer adalah :
Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.
Greedy
Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.
Skema umum algoritma greedy
Algoritma greedy disusun oleh elemen, dan elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain :
1. Himpunan Kandidat
Himpunan yang berisi elemen pembentuk solusi.
2. Himpunan Solusi
Himpunan yang terpilih sebagai solusi persoalan.
3. Fungsi Seleksi
Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.
4. Fungsi Kelayakan
Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.
5. Fungsi Solusi
Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.
6. Fungsi Objektif
Fungsi yang mengoptimalkan solusi.
Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:
· Maksimasi (maxizimation)
· Minimasi (minimization)
Implementasi Algoritma greedy
Strategi greedy: Pada setiap langkah, pilih koin dengan nilai terbesar dari himpunan koin yang tersisa
function CoinExchange (input C: himpunan_Koin; A : integer) → himpunan_Koin
{
menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy
Masukan: himpunan kandidat C
Keluaran: himpunan solusi S
}
Deklarasi
S : himpunan_Koin
x : Koin
Algoritma:
S ← {}
while (∑(nilai semua koin didalam S) ≠ A) and (C ≠ {} ) do
x ← Koin yang mempunyai nilai terbesar
C ← C — {x}
if (∑ (nilai semua koin didalam S) + nilai koin x ≤ A then
S ← S ∪ {x}
endif
endwhile
if (∑ (nilai semua koin didalam S) = A then
return S
else
write (“tidak ada solusi”)
endif
Algoritma Dinamic Programing
Dynamic Programming (selanjutnya disebut “DP” saja) merupakan salah satu teknik perancangan algoritma yang dikembangkan untuk menyelesaikan permasalahan yang sangat kompleks dengan memecah permasalahan tersebut menjadi banyak sub-permasalahan. Perbedaan utama DP dengan Divide and Conquer (selanjutnya disebut “D&C”) adalah pada DP kita menggunakan kembali hasil kalkulasi sub-masalah yang telah dilakukan sebelumnya. Contoh penggunaan algoritma Dynamic Programming adalah pada deret Fibonacci. Algoritma untuk menyelesaikan deret Fibonacci adalah sebagai berikut.
Minimum Spanning Tree (MST)
Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum, tentunya setiap simpul tidak boleh terhubung secara melingkar. Ada dua algoritma untuk mencari rentang minimum, yaitu algoritma Prim dan algoritma Kruskal.
Algoritma Prim
Algoritme Prim adalah sebuah algoritme dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritme ini ditemukan pada 1930 oleh matematikawan Vojtěch Jarník.
Secara umu algoritma prim sebagai berikut :
Contoh :
Algoritma Kruskal
Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.
Secara umu algoritma prim sebagai berikut :
Contoh :
