2. Berikan contoh soal dan penjelasan dengan metode Divide and Conquer dan Jelaskan !
JAWABAN !!!!
1. Algoritma Sekuensial Knapsack Metode Greedy
Salah satu cara untuk menyelesaikan masalah knapsack secara sekuensial adalah
dengan pemakaian metode
Greedy. Procedure tersebut disebut
procedure GREEDY_KNAPSACK. Sebelum procedure tersebut digunakan, benda-benda harus diurutkan rasio
pi/wi -nya tidak menaik. Dengan kata lain :
p0/ w0 ≥ p1 / w1 ≥ ... ≥ pn-1 / wn-1
Adapun procedure
GREEDY_KNAPSACK adalah sebagai berikut
:
procedure
GREEDY_KNAPSACK(P,W,M,Z,n)
real P(0:n-1),W(0:n-1),Z(0:n-1),cu; {n = banyak benda}
integer i,n;
Z ← 0 { Z(0), Z(1), . . . , Z(n-1) = 0}
cu ← M
for i ← 0
to n-1 do
if W(i) 〉 cu then
exit endif
Z(i) ← 1
cu ← cu - W(i)
repeat
if i ≤ n-1 then
Z(i) ← cu/W(i) endif end GREEDY_KNAPSACK
Jika algoritma
ini digunakan untuk menyelesaikan masalah seperti pada contoh yang lalu, dimana
n = 4; M = 15; W = { 5,9,2,4 }; P = { 100,135,26,20 }, maka akan terlihat hasil tracenya sebagai berikut :
Z ← 0
cu ← 15 i = 0
karena W(0) 〈 cu
yaitu
: 5 〈 15 berarti : Z(0) ← 1
i = 1
i = 2
cu ← 15 - 5 = 10
karena W(1) 〈 cu
yaitu
: 9 〈 10 berarti : Z(1) ← 1
cu ← 10 - 9 = 1
karena W(2) 〉 cu yaitu
: 2 〉 1 berarti : keluar dari loop (exit)
Karena 2 ≤ 3 maka Z(2) ← cu/W(2) = 1/2 = 0,5
Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }
Sehingga Q = 1 x
100 + 1 x 135 +
0,5
x 26 + 0 x 20
= 100 + 135 + 13 +
0
= 248
Analisis.
Kompleksitas
waktu dari algoritma Greedy_Knapsack
ini adalah O(n). Tetapi jika data yang digunakan belum terurut rasio pi/wi -nya tidak menaik, maka diperlukan kompleksitas waktu sebesar O(n log n) untuk mengurutkan
sebelumnya. Sehingga untuk masalah optimisasi
knapsack, kompleksitas waktu dari algoritma ini akan lebih besar pada waktu proses
pengurutannya.
2. 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.
