tgs 4 resume dinamik dan greedy
Post on 02-Aug-2015
66 Views
Preview:
TRANSCRIPT
TUGAS RESUME STRATEGI ALGORITMA
METODE GREEDY DAN DYNAMIC PROGRAMMING
OLEH : NIHLAHTUZZAHRA
H12111103
Definisi Strategi Algortima
Strategi : rencana yang cermat mengenai kegiatan untuk mencapai sasaran khusus
Algoritma : urutan langkah-langkah untuk memecahkan suatu masalah
Strategi Algoritma : kumpulan metode atau teknik untuk memecahkan masalah guna
mencapai tujuan yang ditentukan, yang dalam hal ini deskripsi metode atau teknik tersebut
dinyatakan dalam suatu urutan langkah-langkah penyelesaian
Jenis Strategi Algoritma
Strategi solusi langsung (direct solution strategies)
Brute force
Greedy
Strategi berbasis pencarian pada ruang status (state-space base strategies)
Backtracking
Branch and Bound
Strategi solusi atas-bawah (top-down solution strategies)
Divide and Conquer
Transform and Conquer
Increase and Conquer
Strategi solusi bawah-atas (bottom-up solution strategies)
Dynamic Programming.
Program Dinamis (Dynamic Programming)
Program Dinamis
• Program Dinamis (dynamic programming): metode pemecahan masalah dengan cara
menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage)
sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian
keputusan yang saling berkaitan. Pada penyelesaian persoalan dengan metode ini:
1. terdapat sejumlah berhingga pilihan yang mungkin,
2. solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya,
3. kita menggunakan persyaratan optimasi dan kendala untuk membatasi
sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.
Karakteristik Persoalan Program Dinamis
1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya
diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan
tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan
yang ada pada tahap tersebut.
Graf multitahap (multistage graph). Tiap simpul di dalam graf tersebut menyatakan
status, sedangkan V1, V2, … menyatakan tahap.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status
yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan
bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan
dan ongkos pada tahap tersebut.
6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang
dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap
status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k +1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
Contoh Kasus Dynamic Programming
Terdapat empat bentuk bangun persegi yang berbeda seperti dibawah ini ( A,B,C,D) . Dengan
dynamic programming susun keempat balok agar dapat masuk ke dalam kotak berbentuk
persegi panjang yang luasnya 35x15 meter dengan menyisakan luas yang sangat kecil.
Penyelesaian : dynamic programming membagi persoalan ini menjadi beberapa tahap, yang pada setiap tahap hanya diambil satu keputusan..
Idenya :
1. Membuat Kotak dari bangun B, diperoleh bangun F yang baru dengan luas 7 x 4 = 28
m2
2. Kotak persegi panjang dibagi menjadi dua seperti ini . Tahap 1 (8 x 35)m .Tahap 2 (7x35)m
3. Ditahap 1 (8 x 35 )m diambil satu keputusan : isi bagian atas seperti ini
4. Ditahap 2 (7 x 35 )m diambil satu keputusan : isi bagian bawah seperti ini
Daerah yang berwarna merah : Luas Sisa
Luas Sisa = Luas Keseluruhan – Luas yang Terisi
= (35x15) – (18F+C)
= 525 – (18.28 + 8)
= 525 – (512 )
= 13 m2
Dengan dynamic programming diperoleh Luas Sisa 13 m2..
Optimasi
Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian
solusi optimum. Persoalan optimasi ada dua macam:
1. Maksimasi (maximization)
2. Minimasi (minimization)
Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari
sekumpulan alternatif solusi yang mungkin. Elemen persoalan optimasi:
1. kendala (constraints)
2. fungsi objektif(atau fungsi optiamsi)
Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi
layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.
Metode Greedy
Algoritma greedy merupakan metode yang paling populer untuk memecahkan
persoalan optimasi. Greedy = rakus, tamak, loba, ….Prinsip greedy adalah: “take what you
can get now!”. Contoh masalah sehari-hari yang menggunakan prinsip greedy:
o Memilih beberapa jenis investasi (penanaman modal)
o Mencari jalur tersingkat dari Bandung ke Surabaya
o Memilih jurusan di Perguruan Tinggi
o Bermain kartu remi
Karakteristik Metode Greedy
Algoritma greedy membentuk solusi langkah per langkah (step by step).
Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh
karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam
menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat
diubah lagi pada langkah selanjutnya.
Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang
“tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum
lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah
ke solusi optimum global (global optimum).
Jika jawaban terbaik mutlak (benar-benar optimum) tidak diperlukan, maka algoritma
greedy sering berguna untuk menghasilkan solusi yang menghampiri (approximation)
optimum, daripada menggunakan algoritma yang lebih rumit untuk menghasilkan
solusi yang eksak.
Bila algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara
matematis
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.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap
optimum lokal menjadi optimum global.
Contoh 1 (Masalah Penukaran uang):
Persoalan: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa
jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh: tersedia koin-koin 1, 5, 10, dan 25
Uang senilai 32 dapat ditukar dengan cara berikut:
32 = 1 + 1 + … + 1 (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)
32 = 10 + 10 + 10 + 1 + 1 (5 koin)
… dan seterusnya
Minimum: 32 = 25 + 5 + 1 + 1 ) hanya 4
Strategi greedy yang digunakan adalah:
Pada setiap langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan
koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.
Tinjau masalah menukarkan uang 32 dengan koin 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 setiap langkah di atas kita memperoleh optimum lokal, dan pada akhir algoritma kita
memperoleh optimum global (yang pada contoh ini merupakan solusi optimum).
Skema Umum Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen berikut:
1. Himpunan kandidat.
Berisi elemen-elemen pembentuk solusi.
2. Himpunan solusi
Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
3. Fungsi seleksi (selection function)
Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang
sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah
selanjutnya.
4. Fungsi kelayakan (feasible)
Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang
layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah
terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak
dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang
dan tidak pernah dipertimbangkan lagi.
4. Fungsi obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi
(misalnya panjang lintasan, keuntungan, dan lain-lain).
Contoh pada masalah penukaran uang, elemen-elemen algoritma greedy-nya adalah:
1. Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling
sedikit mengandung satu koin untuk setiap nilai.
2. Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang
yang ditukarkan.
3. Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
4. Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak
melebihi jumlah uang yang harus dibayar.
5. Fungsi obyektif: jumlah koin yang digunakan minimum.
Contoh Kasus dengan Metode Greedy
Terdapat empat bentuk bangun persegi yang berbeda seperti dibawah ini ( A,B,C,D) . Dengan
metode greedy susun keempat balok agar dapat masuk ke dalam kotak berbentuk persegi
panjang yang luasnya 35x15 meter dengan menyisakan luas yang sangat kecil.
Penyelesaian :
Metode greedy adalah metode yang memecahkan langkah per langkah, dimana pada setiap
langkah diambil pilihan yang terbaik (“take what you can get now”). Luas bangun A,B,C,D
berturut-turut (12m2,14m2,8m2,16m2). Pada kasus ini, untuk menyisakan luasan yang sangat
kecil,ide terbaik yang kita ambil adalah
1. Menyusun bangun yang mempunyai luas terbesar yakni bangun D menjadi berbentuk
kotak seperti dibawah ini, kita peroleh
bangun baru E (8x8 = 64m2 ).
2. Memasukkan E kedalam kotak persegi panjang hingga tidak bisa dimasukkan lagi.
Terlihat hanya 4 buah bangun E yang bisa dimasukkan, panjang kotak bersisa
35-(8x4) = 3m dan lebar kotak bersisa 15-8 = 7m
3. Tetap pada prinsip “take what you can get now” ,, kita masukkan lagi bangun yang
terluas dan cukup menempati lebar 7m yakni bangun D yang disusun sedemikian rupa
seperti ini
4. Tutup bagian yang terbuka dengan bangun C seperti ini
5. Panjang 7m tadi telah bersisa 7-6 = 1 m dan karena tidak ada bangun yang bersisi 1m
maka sisanya sudah tidak bisa diisi bangun lagi. Tapi panjang sisa 3m masih bisa diisi
oleh bangun C seperti ini
l
Daerah yang berwarna abu-abu : Luas Sisa
Luas Sisa = Luas Keseluruhan – Luas yang Terisi
= (35x15) – (4E+11C+8D)
= 525 – (4.64 + 11.8 + 8.16)
= 525 – (256 + 88 + 128 )
= 525 – 472
= 53 m2
Dengan metode greedy diperoleh Luas Sisa 53 m2 4x luas sisa dengan metode greedy. Terlihat , dengan dynamic programming luas sisa yang diperoleh lebih kecil
top related