Strategi Algoritma dan Macam-macam Algoritma

Source :

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 oleh matematikawan .

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 :

--

--

--

Interested and learn about programming, web development, and machine learning

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Agung Prabowo

Agung Prabowo

Interested and learn about programming, web development, and machine learning

More from Medium

The Dream of Open Data and the Ethics of APIs

Diagram of Web of Document vs Web of Things

Simplified Synchronization of Oracle Sequences when doing Database Migration with GoldenGate

What is return load in fleet management?

The Fresh Graduate Virtual Career Boot Camp — 2022

Fresh Graduate Bootcamp 2022