1. Berikan
contoh soal & penyelesaian dengan metode greedy dan Jelaskan!
2. Berikan
contoh soal & penyelesaian dengan divide & conquer dan Jelaskan!
Jawab :
1. Metode Greedy
Penyelesaian :
Metode Greedy adalah metode untuk memperoleh solusi
yang optimal dari suatu masalah yang mempunyai 2 indikator yaitu : adanya
fungsi tujuan & pembatas (Constrain).Contohnya :
PROCEDURE GREEDY (A,n)
Solusi <- 0 (solusi awal)
FOR I <- 1 TO n DO
X <-
SELECT(A)
IF
FEASIBLE (Solusi, x)
THEN Solusi <- UNION (solusi, x)
ENDIF
REPEAT
RETURN (Solusi)
END GREEDY
Penjelasan :
Dalam program diatas menggunakan prosedur Greedy
dimana terdapat parameter (A,n) n adalah inputan data,variable Solusi bernilai
0 dan terdapat perulangan dari 1 sampai n yang kita input. Untuk variable X
terdapat fungsi SELECT yang merupakan fungsi untuk mengambil data input dari A.
Terdapat Percabangan If yang menggunakan fungsi FEASIBLE dimana fungsi yang
bernilai boolean (0 atau 1). Jadi apabila nilai yang disimpan variable Solusi bernilai
0 atau 1 maka akan menjalankan statemen dibawahnya yaitu Solusi <- UNION
(solusi, x).UNION adalah penggabungan dan pemeriksaan fungsi obyektifnya
(update). Jadi nilai yang disimpan variable Solusi digabungkan dengan nilai
dari variable x. Untuk mengakhiri perintah percabangan dapat kita tulis ENDIF
& untuk mengulangkan perulangannya kita tulis REPEAT. Lalu terdapat RETURN
(Solusi) yang artinya kembali ke variable Solusi. Untuk Mengakhiri program yang
bermetode Greedy dapat kita tulis END GREEDY.
2. Divide dan Conquer
Penyelesaian :
Strategi Divide dan Conquer memecah masalah menjadi
submasalah-submasalah independen yang lebih kecil sehingga solusi
submasalah-submasalah dapat diperoleh secara mudah, solusi
submasalah-submasalah digabung menjadi solusi seluruh masalah. Contohnya :
Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : =
DIVIDE (i,j)
COMBINE
(DNC(i,k),DNC(k+1,j))
End if
Penjelasan :
Dalam program diatas menggunakan prosedur DNC(Divide
& Conquer) yang terdapat formal parameter (I,j) bertipe datakan Integer.
Lalu terdapat variable K juga bertipe datakan integer. Dalam program diatas
menggunakan perintah percabangan if kemudian perintah SMALL merupakan fungsi
yang mengirim Boolean yang menentukan apakah ukuran parameter I & j telah
cukup kecil sehingga solusi dapat diperoleh. . Ukuran dinyatakan sebagai telah
berukuran kecil bergantung masalah. Apabila Benar maka akan menjalankan
perintah SOLVE tersebut dimana akan membenarkan/memperbaiki parameter-parameter
tersebut. Apabila kondisi salah maka akan menjalankan Else dengan statemen K :
= DIVIDE(I,j). Variabel K ini adalah hasil dari fungsi DIVIDE yang membagi
menjadi 2 bagian pada posisi K dari parameter” tersebut biasanya bagian
berukuran sama.Lalu terdapat perintah COMBINE yang merupakan fungsi untuk
menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil
prosedur rekursif DNC parameter (I,k) digabungkan dengan DNC (k+1,j).
