algoritma greddy dan brute force

1.         Algoritma Greddy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah;

pada setiap langkah:

A. mengambil pilihan yang terbaik yangdapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

B. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Karakteristik Algoritma Greddy

•         Greedy = rakus, tamak, loba, …

•         Prinsip greedy: “take what you can get now!”.

•         Algoritma greedy membentuk solusi langkah per langkah (step by step).

•         Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi.

•         Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

Contoh penerapan algoritma greddy

•         Tinjau masalah penukaran uang:

            Strategi greedy: 

                        Pada setiap langkah, pilihlah koin dengan nilai

           terbesar dari himpunan koin yang tersisa.

•         Misal: A = 32, koin yang tersedia: 1, 5, 10, dan 25

            Langkah 1: pilih 1 buah koin 25  (Total = 25)

            Langkah 2: pilih 1 buah koin 5    (Total = 25 + 5 = 30)

            Langkah 3: pilih 2 buah koin 1    (Total = 25+5+1+1= 32) 

•         Solusi: Jumlah koin minimum = 4     (solusi optimal!)

2.      Algoritma Brute Force

·         Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.

·         Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way).

Karakteristik Brute Force

·         Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).

·         Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih cerdas dan lebih mangkus.

·         Untuk masalah yang ukurannya kecil, kesederhanaan brute force biasanya lebih diperhitungkan daripada ketidakmangkusannya.

           

Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus.