METODE GREEDY, DIVIDE AND CONQUER

METODE GREEDY

     Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

a. Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.

Contoh kasus algoritma greedy :

Misalkan tersedia koin : 1, 3, 5.

Uang senilai X=8 dapat di tukar dengan cara :

§  1+1+1+1+1+1+1+1 = 8 (8 koin)

§  1+1+1+1+1+3=8 (6 koin)

§  1+1+1+5=8 (4 koin)

§  1+1+3+3=8 (4 koin)

§  3+5=8 (2 koin)                                    solusi optimal.

Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

 METODE GREEDY banyak digunakan dalam berbagai penyelesaian maslah, antara lain adalah :

1.    Optimal Storage on Tapes Problem

2.    Kanpsack Problem

3.    Minimum Spanning Tree Problem

4.    Shortest Path Problem

Knapsack Problem

Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Contoh kasus knapsack

§  w₁ = 10;  p₁ = 2

§  w₂ = 5;     p₂ = 3

§  w₃ = 15;   p₃ = 5

§  w₄ = 7;     p₄ = 7

§  w₅ = 6;     p₅ = 1

§  w₆ = 18;   p₆ = 4

§  w₇ = 3;     p₇ = 1

M = 15

Jawaban :    

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi/wi	profit	weight	density
1	2	10	5	1	1	1	1
2	3	5	1,7	1	1	0	1
3	5	15	3	1	0	1	1
4	7	7	1	0	0	0	0
5	1	6	6	1	1	1	1
6	4	18	4,5	1	1	1	1
7	1	3	3	0	1	1	0
Total bobot :				15	11	13	15
Total keuntungan :				54	42	52	54

Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkanweight dan density tidak memberikan solusi optimal.

b. Elemen Algoritma Greedy

        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.

c. Skema Umum Algoritma Greedy

        Misal kita mengasumsikan elemen algoritma greedy sebagai berikut :

    Himpunan Kandidat = C,

    Himpunan Solusi = S,

    Fungsi Seleksi = select(),

    Fungsi Kelayakan = feasible(),

    Fungsi Solusi = solution(), dan

    Fungsi Obyektif = objective().

        Skema umum dari algoritma greedy dapat kita tuliskan :

- Inisialisasi S dengan kosong.

- Pilih sebuah kandidat dari C (dengan select()).

- Kurangi C dengan kandidat yang telah terpilih di atas.

- Periksa apakah kandidat yang dipilih tersebut bersama ? sama dengan S membentuk solusi yang         layak (dengan feasible()). Jika ya, masukkan kandidat ke S; jika tidak buang kandidat tersebut dan      tidak perlu ditelaah lagi.

- Periksa apakah S yang sudah terbentuk telah memberikan solusi yang lengkap (dengan solution()).      Jika ya, berhenti; jika tidak, ulangi dari langkah 2.

Sumber :  

http://stephanusar.blogspot.com/2012/11/pengertian-metode-greedy-dan-algoritma.html

https://kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/

   

   DIVIDE AND CONQUER

   Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.

   

   Skema umum Algoritma Divide and Conquer

   Contoh kasus dan pemyelesaian

>> Persoalan Minimum dan Maksimum (MinMaks)

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 :

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.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.

COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

=======================================================

Penyelesaian dengan Algoritma Divide and Conquer secara umum :

=======================================================

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

- SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.

- DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai                            jumlah titik yang sama

- CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

- Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

  Pasangan titik terdekat terdapat di bagian PLeft.

  Pasangan titik terdekat terdapat di bagian PRight.

 Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

   Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

Sumber : 

http://wawanhermawan74.blogspot.com/2012/10/contoh-kasus-algoritma-divide-and.html