Metode Greedy dan Divide & Conquer

Pada pembahasan kali ini saya akan membahas tentang algoritma greedy dan divide & conquer. Pertama Algoritma Greedy adalah salah satu jenis algoritma, algoritma greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiap langkahnya atau local maxium. Algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Metode ini banyak digunakan dalam berbagai penyelesaian masalah.

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah. Pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Contoh masalah dengan penyelesain

Contoh 1: 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!)

Pada masalah penukaran uang :

• Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
• Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
• Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
• Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
• Fungsi obyektif: jumlah koin yang digunakan minimum.

Pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang optimal.  

Contoh 2 : tinjau masalah penukaran uang.

  (a) Koin: 5, 4, 3, dan 1
        Uang yang ditukar = 7
        Solusi greedy:  7 = 5 + 1 + 1      ( 3 koin) - tidak optimal
        Solusi optimal: 7 = 4 + 3        ( 2 koin)

  (b) Koin: 10, 7, 1
        Uang yang ditukar: 15
        Solusi greedy:  15 = 10 + 1 + 1 + 1 + 1 + 1    (6 koin)
        Solusi optimal: 15 = 7 + 7 + 1            (hanya 3 koin)

  (c)  Koin: 15, 10, dan 1
        Uang yang ditukar: 20
        Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1    (6 koin)
        Solusi optimal: 20 = 10 + 10            (2 koin)

Kedua 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 masalah (secara rekursif).

• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

- Skema umum Algoritma Divide and Conquer

 

Contoh masalahan dengan penyelesaiannya

- Persoalan Minimum dan Maksimum (MinMaks)

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.