Algoritma Menggunakan Metode Greedy dan Divide And Conquer
- Metode Greedy
Metode greedy adalah metode yang
digunakan untuk memecahkan persoalan optimasi. Ada 2 macam persoalan
optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita
bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau
maksimum dari sekumpulan alternatif solusi yang ada.
Sebagai contoh dari penyelesaian masalah dengan algoritma greedy, mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta:
Jalur dari
Titik A ke B
Dari peta yang ditampilkan di atas,
dapat dilihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem
peta pada gambar secara otomatis telah memilih jalur terpendek (berwarna biru).
Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma
greedy.
Langkah pertama yang harus kita lakukan tentunya adalah
memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta.
Jika dilihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya
hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu
pada masing-masing titik tersebut. Misalnya, peta di atas dapat dengan titik-titik penghubung seperti berikut:
kemudian kita membuat sketsa dari dari
masing-masing titik tersebut seperti gambar yang ada disebelahnya.
Untuk mencari jarak terpendek dari A ke B, sebuah algoritma
greedy akan menjalankan langkah-langkah seperti berikut:
1. Mulai dari titik awal (A). Ambil seluruh titik yang dapat
dikunjungi.
2. Lalu kita lihat, bahwa jarak yang terderkat dari titik A
adalah C, maka kita ambil jalur menjuju titik C.
3. Setelah itu, kita pindahkan titiknya menjadi di C. Kemudian kita
pilih local maksimumnya di titik D karena jaraknya lebih dekat dibandingkan ke
titik H.
4. Selanjutnya, kita pindahkan titiknya menjadi di D, dari titik
D menuju titik H lalu kemudian ke titik F dan sampai pada titik B.
Dengan menggunakan algoritma greedy pada graph di atas, hasil
akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi
jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang
sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan
solusi yang optimal, dikarenakan pencarian local
maximum pada setiap langkahnya, tanpa memperhatikan
solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma
greedy dapat memberikan solusi yang kurang optimal
- Metode Divide And Conquer
Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya
pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk
kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and
conquer.
Contoh kasus dalam kehidupan sehari-hari yang dapat dilakukan
dengan menggunakan metode divide and conquer adalah ketika kita ingin membagi
kelompok untuk melakukan kegiatan bersih-bersih.
Misalkan di sebuah kelas terdapat 30 orang siswa. Dari 30 orang siswa tersebut kita bagi
menjadi beberapa kelompok, dan setiap kelompok mempunyai tugasnya
masing-masing. Seperti 5 orang siswa menyapu lantai, 3 orang di sisi sebelah
kiri dan 2 orang disebelah kanan. 5 siswa mengepel, dengan 2 orang sebelah
kiri, 1 orang di barisan tengah dan 2 orang lagi disebelah kanan. 4 orang siswa
membersihkan AC, 2 siswa membersihkan AC yang pertama dan sisanya membersihkan
AC yang kedua. 6 orang siswa membereskan kursi. 10 siswa mengelap jendela, 5
orang jendela bagian dalam dan 5 orang jendela bagian luar.
Dengan melakukan pembagian seperti ini, maka akan memudahkan
kita untuk membersihkan kelas, serta dapat mempercepat pekerjaan.
Kelas : 1IA24
Sumber :
No comments:
Post a Comment