BAB II LANDASAN TEORI Perancangan program aplikasi yang akan dibuat menggabungkan algoritma Brute Force dan algoritma Greedy yang digunakan secara bergantian pada tahap-tahap tertentu. Karena itu, pada bagian ini akan dibahas juga algoritma Brute Force dan Greedy terlebih dahulu sebelum masuk ke dalam pembahasan algoritma kombinasi keduanya yaitu algoritma Brudy.
2.1. Algoritma Brute Force Brute Force (Rinaldi Munir, 2004, p. 2) adalah sebuah pendekatan langsung (straight forward) untuk memecahkan suatu masalah, yang biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Pada dasarnya algoritma Brute Force adalah alur penyelesaian suatu permasalahan dengan cara berpikir yang sederhana dan tidak membutuhkan suatu permikiran yang lama. Sebenarnya, algoritma Brute Force merupakan algoritma yang muncul karena pada dasarnya alur pikir manusia adalah Brute Force (langsung/to the point). Beberapa karakteristik dari algoritma Brute Force dapat dijelaskan sebagai berikut. a. Membutuhkan jumlah langkah yang banyak dalam menyelesaikan suatu permasalahan sehingga jika diterapkan menjadi suatu algoritma program aplikasi akan membutuhkan banyak memori. b. Digunakan sebagai dasar dalam menemukan suatu solusi yang lebih efektif. c. Banyak dipilih dalam penyelesaian sebuah permasalahan yang sederhana karena kemudahan cara berpikirnya.
8 d. Pada banyak kasus, algoritma ini banyak dipilih karena hampir dapat dipastikan dapat menyelesaikan banyak persoalan yang ada. e. Digunakan sebagai dasar bagi perbandingan keefektifan sebuah algoritma. Dalam beberapa kasus tertentu algoritma Brute Force hampir sama dengan Exhaustive Search. Exhausitve Search yang merupakan teknik pencarian solusi secara Brute Force pada masalah yang melibatkan pencarian elemen dengan sifat khusus. Biasanya elemen tersebut berada di antara objek-objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan. Berdasarkan definisi ini, maka dapat ditarik kesimpulan bahwa Exhaustive Search adalah Brute Force juga. Oleh karena itu Exhaustive Search adalah salah satu implementasi dari Brute Force dalam kasus pencarian. Masalah–masalah dalam Exhaustive Search dengan penerapan algoritma Brute Force dapat dijelaskan sebagai berikut. a. Enumerasi setiap solusi yang mungkin dengan cara yang sistematis. b. Evaluasi setiap kemungkinan solusi yang ditemukan satu per satu, meskipun terdapat beberapa kemungkinan ditemukannya solusi yang tidak layak atau bahkan terdapat kemungkinan–kemungkinan solusi terbaik yang telah ditemukan dan dievaluasi. c. Bila pencarian sudah sampai pada tujuan, maka pilih solusi yang terbaik. Berikut ini adalah contoh-contoh penerapan algoritma Brute Force pada perhitungan matematika biasa. 1.
Menghitung an (a > 0, n adalah bilangan bulat tak-negatif) an = a x a x … x a (n kali) , jika n > 0 =1
, jika n = 0
Algoritma: kalikan 1 dengan a sebanyak n kali.
9 2.
Menghitung n! (n bilangan bulat tak-negatif) n! = 1 × 2 × 3 × … × n =1
, jika n > 0 , jika n = 0
Algoritma: kalikan n buah bilangan, yaitu 1, 2, 3, …, n, sekaligus. 3.
Mengalikan dua buah matrik yang berukuran n × n. Misalkan C = A × B dan elemen-elemen matrik dinyatakan sebagai cij, aij, dan bij. Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua vektor baris dan kolom yang panjangnya n.
4.
Menemukan semua faktor dari bilangan bulat n selain dari 1 dan n itu sendiri. Definisi: Bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b.
5.
Mencari elemen terbesar (atau terkecil) Diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan tersebut.
6.
Sequential Search Diberikan n buah bilangan bulat yang dinyatakan sebagai a1, a2, …, an. Carilah apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0.
10 7.
Bubble Sort Algoritma Bubble Sort mengimplementasikan teknik Brute Force dengan jelas sekali.
8.
Menghitung nilai polinom secara Brute Force
Kelebihan dari algoritma Brute Force adalah sebagai berikut. 1.
Metode Brute Force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability).
2.
Metode Brute Force sederhana dan mudah dimengerti.
3.
Metode Brute Force menghasilkan algoritma yang layak untuk beberapa masalah penting, seperti pencarian, pengurutan, pencocokan string, perkalian matriks.
4.
Metode Brute Force menghasilkan algoritma baku (standard) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).
Selain itu, terdapat beberapa kelemahan dari algoritma Brute Force: 1.
Metode Brute Force jarang menghasilkan algoritma yang efektif.
2.
Beberapa algoritma Brute Force lambat sehingga tidak dapat diterima.
3.
Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya.
Algoritma Brute Force pada penyelesaian masalah Knapsack dilakukan dengan menghitung satu per satu keuntungan yang diperoleh dari semua kemungkinan pemilihan barang yang ada. Banyaknya kemungkinan pemilihan barang tersebut dapat dirumuskan sebagai: 2n.
11 Adapun n adalah jumlah dari barang yang akan dikirim. Jadi, seandainya banyak barang yang akan dikirm 5 buah, maka untuk mencari solusi optimal diperlukan 25 = 32 kemungkinan. Memang, akan didapatkan hasil yang sangat optimal mengingat akan ditelusuri satu per satu kemungkinan yang ada, tetapi akan sangat membutuhkan waktu yang sangat lama (perhitungan manual) dan memori yang besar (jika menggunakan program komputer) untuk jumlah barang yang ada sangat banyak.
2.2
Algoritma Greedy Algoritma Greedy merupakan algoritma yang lazim untuk memecahkan persoalan
optimasi meskipun hasilnya tidak selalu merupakan solusi yang optimum. Sesuai arti harafiah, Greedy berarti tamak. Prinsip utama dari algoritma ini adalah mengambil sebanyak mungkin apa yang dapat diperoleh sekarang. Untuk memecahkan persoalan dengan algoritma Greedy, kita memerlukan elemen-elemen sebagai berikut. a. Himpunan Kandidat (C) Himpunan ini berisi elemen-elemen pembentuk solusi. b. Himpunan Solusi, (S) Himpunan ini berisi kandidat yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari himpunan kandidat. c. Fungsi Seleksi Fungsi seleksi merupakan fungsi yang ada pada setiap langkah memilih kandidat yang paling memungkinkan guna mencapai solusi optimal.
12 d. Fungsi Kelayakan (Feasible) Fungsi kelayakan adalah fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak dan tidak melanggar batasan atau constraints yang ada. e. Fungsi Objektif Fungsi
objektif
adalah
fungsi
yang
memaksimumkan
atau
meminimumkan nilai solusi. Skema umum algoritma Greedy adalah sebagai berikut. a. Inisialisasi S dengan kosong. b. Pilih sebuah kandidat C dengan fungsi seleksi. c. Kurangi C dengan kandidat yang sudah dipilih dari langkah (b) di atas. d. Periksa apakah kandidat yang dipilih tersebut bersama-sama dengan himpunan solusi membentuk solusi yang layak atau feasible (dengan fungsi kelayakan). e.
Periksa apakah himpunan solusi sudah memberikan solusi yang lengkap serta optimal (dengan fungsi objektif).
Contoh permasalahan yang dapat diselesaikan dengan algoritma Greedy adalah masalah penukaran uang koin. Strategi Greedy adalah pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa. •
Misal: A = 32, koin yang tersedia: 1, 5, 10, dan 25.
•
Himpunan Kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
13 •
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 Objektif: jumlah koin yang digunakan minimum.
•
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!)
Optimum global dengan menggunakan algoritma Greedy belum tentu merupakan solusi optimum (terbaik), tetapi sub-optimum atau pseudo-optimum. Alasannya adalah sebagai berikut. 1. Algoritma Greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode Exhaustive Search). 2. Terdapat beberapa fungsi seleksi yang berbeda, sehingga harus dipilih fungsi yang tepat agar algoritma yang digunakan menghasilkan solusi optimal. Secara umum rumus dari algoritma Greedy adalah: Berat barang total = ∑ WjXj ≤ K di mana Xj € {0,1} j∈N
Volume barang total = ∑ VjXj ≤ K di mana Xj € {0,1} j∈N
14 Keuntungan total =
∑PX j
j
di mana Xj € {0,1}
j∈N
Wj adalah berat barang, Vj adalah volume barang, Pj adalah keuntungan barang, Xj adalah bernilai 0 jika barang tersebut tidak dipilih untuk dimasukkan ke dalam kapasitas Knapsack dan 1 jika barang tersebut terpilih untuk dimasukkan ke dalam kapasitas Knapsack, dan K adalah kapasitas media pengiriman. Pada penyelesaian masalah Knapsack dengan menggunakan algoritma Greedy dapat dipilih 3 cara sebagai berikut. 1. Greedy by Profit, pilih benda-benda dengan keuntungan maksimum dan bendabenda tersebut memiliki berat yang masih dapat ditampung oleh sisa kapasitas Knapsack. 2. Greedy by Weight, pilih benda-benda dengan berat minimum dan benda-benda tersebut memiliki volume yang masih dapat ditampung oleh sisa kapasitas Knapsack. 3. Greedy by Volume, pilih benda-benda dengan volume minimum dan benda-benda tersebut memiliki berat yang masih dapat ditampung oleh sisa kapasitas Knapsack. 4. Greedy by Weight Density, pilih benda-benda dengan keuntungan per berat yang nilainya maksimum dan benda-benda tersebut memiliki berat dan volume yang masih dapat ditampung oleh sisa kapasitas Knapsack. Rumus untuk mendapatkan density adalah: Dj =
Pj Wj
5. Greedy by Volume Density, pilih benda-benda dengan keuntungan per volume yang nilainya maksimum dan benda-benda tersebut memiliki berat dan volume yang
15 masih dapat ditampung oleh sisa kapasitas Knapsack. Rumus untuk mendapatkan density adalah: Dj =
Pj Vj
Pada sebagian masalah, algoritma Greedy tidak selalu berhasil memberikan solusi yang optimal. Jika jawaban terbaik mutlak tidak diperlukan, maka algoritma Greedy sering berguna untuk menghasilkan solusi hampiran (approximation), dibandingkan dengan menggunakan algoritma yang lebih rumit untuk menghasilkan solusi yang eksak. Bila algoritma Greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.
2.3
Algoritma Brudy (Brute Force-Greedy) Ide awal dari penggabungan kedua algoritma tersebut adalah membentuk sebuah
algoritma baru yang di tengah-tengah. Misalkan diperlukan algoritma dengan kecepatan yang cukup tinggi (lebih tinggi dari kecepatan Brute Force), algoritma yang cukup sederhana, serta ketepatan penemuan solusi yang cukup baik (lebih baik dari Greedy). Algoritma ini (untuk selanjutnya, dinamakan sebagai algoritma Brudy (Brute ForceGreedy)) lebih mengacu pada algoritma Greedy. Bedanya, algoritma Greedy mencari optimum lokal pada tiap langkahnya, sedangkan algoritma Brudy mencari optimum lokal pada tiap b-langkah (untuk selanjutnya b dinamakan sebagai nilai batas, dengan catatan b > 1 dan b < jumlah_tahap), sehingga dapat dikatakan algoritma Brudy ini sama dengan algoritma B-Greedy. Jadi, pada suatu keadaan, misalkan pada suatu permasalahan yang pengerjaannya bertahap (anggap saja 14 tahap dengan tahap ke-0 adalah kondisi awal), algoritma Brute Force akan mencari semua cara mencapai tahap
16 ke-13 tersebut. Algoritma Greedy akan mencari optimum dari tahap ke-i menuju tahap ke-(i+1), sedangkan algoritma Brudy akan mencari optimum dari tahap ke-i menuju tahap ke-(i+b) dan b bebas ditentukan oleh pengguna. Misalkan dipilih b adalah 3, berarti akan dicari optimum tahap ke-1 menuju tahap ke-4, setelah itu dicari optimum tahap ke-4 menuju tahap ke-7, dan seterusnya. Begitu diperoleh optimum dari tahap ke-1 menuju ke tahap ke-4, status di tahap ke-4 tersebut itulah yang akan diperluas untuk dicari optimumnya menuju tahap ke-7 dan seterusnya. Hal inilah yang merupakan letak kemiripan algoritma Brudy dengan algoritma Greedy. Sedangkan untuk mencari optimum dari tahap ke-1 sampai tahap ke-4, akan dicoba semua cara yang mungkin dari tahap ke-1 sampai tahap ke-4, begitu seterusnya. Inilah kemiripan algoritma Brudy dengan algoritma Brute Force. Sedikit perbedaan dengan algoritma Greedy, yang sekaligus berguna menutupi kelemahan algoritma ini, adalah apabila tahap ke-(i+b) melebihi solusi akhir, kurangilah b dengan 1 dan lakukan lagi untuk langkah selanjutnya. Berikut ini contoh perbandingan hasil penyelesaian permasalahan Knapsack menggunakan metode Brute Force, Greedy, dan Brudy. Persoalan: Misalkan diberikan beberapa buah barang dengan keuntungan serta beratnya masing-masing, akan tetapi container yang dimiliki hanya dapat memuat sejumlah berat tertentu. Pilih barang-barang yang akan dibawa agar keuntungan yang diperoleh maksimum. Contoh: Terdapat 6 benda (label 1 sampai 6), dengan wi adalah berat benda ke-i dan pi adalah keuntungan benda ke-i. w1 = 100
p1 = 40
v1= 50
w2 = 50
p2 = 35
v2 = 70
17 w3 = 45
p3 = 18
v3 = 30
w4 = 20
p4 = 4
v4 = 25
w5 = 10
p5 = 10
v5 = 10
w6 = 5
p6 = 2
v6 = 18
Kapasitas Knapsack K = 100, volume = 200 Tuliskan solusi sebagai X = (x1, x2, …, x6) dengan xi = 0 jika benda ke-i dibawa atau xi = 1 jika benda ke-i tidak dibawa.
Penyelesaian dengan Brute Force. Dicoba semua kemungkinan X, mulai X = (0, 0, 0, 0, 0,0), sampai dengan X = (1, 1, 1, 1, 1, 1). Jumlah kemungkinan yang harus dicoba ada 26 = 64 kemungkinan. Tiap kemungkinan harus dihitung berat totalnya, dan dari semua kemungkinan yang berat totalnya tidak melebihi kapasitas Knapsack, pilih satu yang keuntungannya paling besar. Pada akhirnya akan diperoleh solusi optimum X = (0, 1, 1, 0, 0, 1), dengan berat total 100, volume total 118, dan keuntungan total 55. Hal ini memang sangat optimal tetapi untuk memperoleh hasil tersebut membutuhkan proses yang sangat panjang dan lama (perhitungan manual). Apabila metode ini diterapkan menjadi algoritma pembuatan program aplikasi akan menggunakan memori yang sangat besar.
Penyelesaian dengan Greedy. Dengan Greedy, bisa dipilih 3 cara sebagai berikut. 1. Greedy by Profit, pilih benda-benda dengan keuntungan maksimum dan bendabenda tersebut memiliki berat yang masih dapat ditampung oleh sisa kapasitas Knapsack.
18 2. Greedy by Weight, pilih benda-benda dengan berat minimum dan benda-benda tersebut memiliki volume yang masih dapat ditampung oleh sisa kapasitas Knapsack. 3. Greedy by Volume, pilih benda-benda dengan volume minimum dan benda-benda tersebut memiliki berat yang masih dapat ditampung oleh sisa kapasitas Knapsack. 4. Greedy by Weight Density, pilih benda-benda dengan keuntungan per berat yang nilainya maksimum dan benda-benda tersebut memiliki berat dan volume yang masih dapat ditampung oleh sisa kapasitas Knapsack. Rumus untuk mendapatkan density adalah: Dj = 4.
Pj Wj
Greedy by Volume Density, pilih benda-benda dengan keuntungan per volume yang nilainya maksimum dan benda-benda tersebut memiliki berat dan volume yang masih dapat ditampung oleh sisa kapasitas Knapsack. Rumus untuk mendapatkan density adalah: Dj =
Pj Vj
19 Sehingga bisa dibuat tabelnya sebagai berikut. Tabel 2.1 Data Permasalahan Knapsack dengan solusi Greedy Sumber : (Rinaldi Munir, 2004, p31) Greedy by weight volume weight volume density density 0 0 0 0
i
Wi
1
100
Sifat objek Vi Pi Di Di volume weight 50 40 0,8 0,4
2
50
70
35
0,5
0,7
0
0
0
1
0
3
45
30
18
0,6
0,4
0
1
1
0
1
4
20
25
4
0,16
0.2
0
1
1
1
1
5
10
10
10
1,0
1,0
0
1
1
1
1
6
5
18
2
0,11
0,4
0
1
1
1
1
100 50 40
80 83 34
80 83 34
85 123 51
80 83 34
Total bobot Total volume Total keuntungan
profit 1
Sehingga diperolehlah solusi sebagai berikut. • Greedy by Profit: X = (1, 0, 0, 0, 0, 0), dengan keuntungan total = 40. • Greedy by Weight: X = (0, 0, 1, 1, 1, 1), dengan keuntungan total = 34. • Greedy by Volume: X = (0, 0, 1, 1, 1, 1), dengan keuntungan total = 34. • Greedy by Weight Density: X = (0, 1, 0, 1, 1, 1), dengan keuntungan total = 51. • Greedy by Weight Density: X = (0, 0, 1, 1, 1, 1), dengan keuntungan total = 34. Dari hal-hal di atas diperoleh kenyataan, bahwa langkah Greedy mengutamakan kecepatan dan hanya optimum pada setiap langkah, dan tidak ada yang menghasilkan keuntungan optimum pada langkah akhir. Secara umum, jika banyak barang adalah n, kompleksitas algoritma untuk Brute Force adalah: O(2n).
20 Sedangkan untuk algoritma greedy, kompleksitas pada greedy by profit dan greedy by weight adalah sama, yaitu: O(n2), yang artinya pemilihan k barang yang diambil, dengan maksimal n buah iterasi, karena jumlah barang yang diambil tidak mungkin lebih dari n. Pada greedy by density, kompleksitasnya berbeda sedikit karena harus ada perhitungan pi/wi untuk setiap i barang-barang yang ada, yaitu: T(n) = n2 + n, sehingga kompleksitasnya adalah: O(n2). Dengan menggunakan algoritma Brudy maka akan memperoleh hasil sebagai berikut. Pertama, pilih nilai batas secara bebas (penjelasan mengenai nilai batas). Misalkan saja nilai batasnya dipilih yaitu b = 2. Langkah-langkah penyelesaian algoritma adalah sebagai berikut. 1. Karena dipilih b = 2, berikutnya tentukan semua himpunan bagian dari 6 benda tersebut ({1, 2, 3, 4, 5, 6}) yang banyak anggotanya adalah 2. Banyaknya himpunan bagian tersebut didapat dengan menggunakan rumus kombinasi yaitu: C(n,r) =
n! (n − r )! r!
2. Cari profit, berat, dan profit/berat untuk tiap 2 benda tersebut. Untuk memudahkan, dapat dibuat tabel.
21 Tabel 2.2 Data Permasalahan Knapsack dengan solusi Brudy Sumber : (Anggriawan Sugianto, 2005, p4)
Properti objek i
wi
vi
pi
pi/wi
pi/vi
{1,2}
150
120
75
0,5
0,63
{1,3}
145
80
58
0,4
0,73
{1,4}
140
75
44
0,37
0,59
{1,5}
110
60
50
0,45
0,83
{1,6}
105
68
42
0,4
0,62
{2,3}
95
100
53
0,56
0,53
{2,4}
70
95
39
0,56
0,41
{2,5}
60
80
45
0,75
0,56
{2,6}
55
88
37
0,67
0,42
{3,4}
65
55
22
0,34
0,4
{3,5}
55
40
28
0,51
0,7
{3,6}
50
48
20
0,4
0,42
{4,5}
30
35
14
0,47
0,4
{4,6}
25
43
6
0,24
0,14
{5,6}
15
28
12
0,8
0,43
Untuk memperoleh solusi optimal masalah Knapsack di atas dengan menggunakan algoritma Brudy adalah dengan cara menganalisis data-data di atas ke dalam 5 cara yang berbeda, yaitu Brudy by Weight (dengan memprioritaskan berat yang paling kecil),
22 Brudy by Weight (dengan memprioritaskan volume yang paling kecil), Brudy by Profit (dengan memprioritaskan keuntungan yang paling besar terlebih dahulu), Brudy by Weight Density (dengan memprioritaskan keuntungan per berat yang paling besar terlebih dahulu), dan Brudy by Volume Density (dengan memprioritaskan keuntungan per volume yang paling besar terlebih dahulu). Kemudian setelah mendapatkan solusisolusi dari ketiga cara tersebut digunakan suatu rumusan untuk memperoleh solusi optimal yaitu: Popt = maks (Pp, Pw, Pv, Pdw,Pdv ), Wopt = W( Popt), dan Vopt = V(Popt) Popt adalah keuntungan optimal yang dicari, Wopt adalah berat total dari barang-barang yang diprioritaskan sehingga memperoleh keuntungan yang maksimal, Vopt adalah volume total dari barang-barang yang diprioritaskan sehingga memperoleh keuntungan yang maksimal, Pp adalah keuntungan yang diperoleh dalam perhitungan dengan menggunakan cara Brudy by Profit, Pw adalah keuntungan yang diperoleh dalam perhitungan dengan menggunakan cara Brudy by Weight, Pv adalah keuntungan yang diperoleh dalam perhitungan dengan menggunakan cara Brudy by Volume, Pdw adalah keuntungan yang diperoleh dalam perhitungan dengan menggunakan cara Brudy by Weight Density, sedangkan Pdv adalah keuntungan yang diperoleh dalam perhitungan dengan menggunakan cara Brudy by Volume Density.
Brudy by Weight: 1. Pilih i dengan berat terkecil dan tidak lebih dari 100, volume tidak lebih dari 200, dipilih {5,6}, berat sisa = 85, volume sisa = 172. 2. Pilih i berikutnya dengan berat terkecil, tidak lebih dari 85, volume tidak lebih dari 172, dan i ∩ {5,6} = {}, dipilih {3,4}, berat sisa = 20, volume sisa = 117.
23 3. Pilih i berikutnya dengan berat terkecil, tidak lebih dari 20, volume tidak lebih dari 117 dan i ∩ {3,4,5,6} = {}. Tidak ada yang dipilih. 4. Decrement b, b = 1, gunakan tabel 2.1 pada pembahasan dengan metode Greedy, pilih i berikutnya dengan berat terkecil, tidak lebih dari 20, volume tidak lebih dari 117, dan i ∩ {3,4,5,6} = {}. Tidak ada yang dipilih. 5. Decrement b, b = 0. Ketika b = 0 proses berhenti. Solusi = (0, 0, 1, 1, 1, 1). Berat = 80, volume = 83, keuntungan = 34.
Brudy by Volume: 1. Pilih i dengan volume terkecil dan tidak lebih dari 200, berat tidak lebih dari 100, dipilih {5, 6), berat sisa = 85, volume sisa = 172. 2. Pilih i berikutnya dengan volume terkecil, tidak lebih dari 172, berat tidak lebih dari 85, dan i ∩ {5, 6} = {}, dipilih {3,4}, berat sisa = 20, volume sisa = 117. 3. Pilih i berikutnya dengan volume terkecil, tidak lebih dari 117, berat tidak lebih dari 20 dan i ∩ {3, 4, 5, 6} = {}. Tidak ada yang dipilih. 4. Decrement b, b = 1, gunakan tabel 2.1 pada pembahasan dengan metode Greedy, pilih i berikutnya dengan volume terkecil, tidak lebih dari 117, berat tidak lebih dari 20, dan i ∩ {3, 4, 5, 6} = {}. Tidak ada yang dipilih. 5. Decrement b, b = 0. Ketika b = 0 proses berhenti. Solusi = (0, 0, 1, 1, 1, 1). Berat = 80, volume = 83, keuntungan = 34.
24 Brudy by Profit: 1. Pilih i dengan keuntungan terbesar dengan berat tidak lebih dari 100 dan volume tidak lebih dari 200, dipilih {2, 3), berat sisa = 5 dan volume sisa = 100. 2. Pilih i berikutnya dengan keuntungan terbesar, berat tidak lebih dari 5, volume tidak lebih dari 100, dan i ∩ {2, 3} = {}. 3.. Decrement b, b = 1, gunakan tabel 2.1 pada pembahasan dengan metode Greedy, pilih i berikutnya dengan keuntungan terbesar, berat tidak lebih dari 5, volume tidak lebih dari 100, dan i ∩ {2,3} = {6}, berat sisa = 0, sisa volume = 95. 4. Pilih i berikutnya dengan keuntungan terbesar, berat tidak lebih dari 0, volume tidak lebih dari 82 dan i ∩ {2, 3, 6} = {}. Tidak ada yang dipilih. 5. Decrement b, b = 0. Ketika b = 0 proses berhenti. Solusi = (0, 1, 1, 0, 0, 1). Berat = 100, volume = 118, keuntungan = 55.
Brudy by Weight Density: 1. Pilih i dengan keuntungan per berat terbesar dengan berat tidak lebih dari 100 dan volume tidak lebih dari 200, dipilih {5, 6}, berat sisa = 85, volume sisa = 172. 2. Pilih i berikutnya dengan keuntungan per berat terbesar, berat tidak lebih dari 85, volume tidak lebih dari 172, dan i ∩ {5, 6} = {2, 4}, berat sisa = 15, volume sisa = 77.
25 3. Pilih i berikutnya dengan keuntungan per berat terbesar dan berat tidak lebih dari 15, volume tidak lebih dari 77 dan i ∩ {2, 4, 5, 6} = {}. Tidak ada yang dipilih. 4. Decrement b, b = 1, gunakan tabel 2.1 pada pembahasan dengan metode Greedy, pilih i berikutnya dengan keuntungan per berat terbesar dan berat tidak lebih dari 15, volume tidak lebih dari 77 dan i ∩ {2, 4, 5, 6} = {}. Tidak ada yang dipilih. 5. Decrement b, b = 0. Ketika b = 0 proses berhenti. Solusi = (0, 1, 0, 1, 1, 1). Berat = 85, volume = 123, keuntungan = 51.
Brudy by Volume Density: 1. Pilih i dengan keuntungan per volume terbesar dengan berat tidak lebih dari 100 dan volume tidak lebih dari 200, dipilih {3, 5}, berat sisa = 45, volume sisa = 160. 2. Pilih i berikutnya dengan keuntungan per volume terbesar, berat tidak lebih dari 45, volume tidak lebih dari 160, dan i ∩ {3, 5} = {4, 6}, berat sisa = 20, volume sisa = 117. 3. Pilih i berikutnya dengan keuntungan per volume terbesar dan berat tidak lebih dari 20, volume tidak lebih dari 117,dan i ∩ {3, 4, 5, 6} = {}. Tidak ada yang dipilih. 4. Decrement b, b = 1, gunakan tabel 2.1 pada pembahasan dengan metode Greedy, pilih i berikutnya dengan keuntungan per berat terbesar dan berat tidak lebih dari 20, volume tidak lebih dari 117 dan i ∩ {3, 4, 5, 6} = {}. Tidak ada yang dipilih.
26 5. Decrement b, b = 0. Ketika b = 0 proses berhenti. Solusi = (0, 0, 1, 1, 1, 1). Berat = 80, volume = 83, keuntungan = 34.
Dari kelima solusi di atas selanjutnya dicari solusi yang memberi keuntungan paling besar yaitu solusi yang diperoleh dengan menggunakan cara Brudy by Profit yaitu keuntungan sebesar 55, volume sebesar 118, dan berat sebesar 100. Sedangkan solusi = (0, 1, 1, 0, 0, 1) artinya barang yang akan dipriopritaskan untuk dikirim adalah: •
barang dengan i = 2, yaitu berat = 50, volume = 70, dan keuntungan = 35.
•
barang dengan i = 3, yaitu berat = 45, volume = 30, dan keuntungan = 18.
•
barang dengan i = 6, yaitu berat = 5, volume = 18 dan keuntungan = 2.
Jika hasil yang diperoleh dengan menggunakan algoritma Brudy dibandingkan dengan hasil yang diperoleh dengan 2 algoritma lain, yaitu Brute Force dan Greedy, maka hasil yang diperoleh sama dengan yang diperoleh dengan menggunakan algoritma Brute Force namun dengan proses yang jauh lebih cepat. Pada hasil yang diperoleh dengan menggunakan algoritma Greedy hasil yang diperoleh tidak optimal yaitu keuntungan = 51 dan berat = 85 walaupun untuk memperoleh hasilnya jauh lebih cepat dibanding dengan menggunakan algoritma Brute Force. Dari contoh penyelesaian masalah Knapsack di atas dapat dilihat dengan jelas penggabungan dua buah algoritma yang sangat sederhana (Brute Force dan Greedy) yang saling memiliki kekurangan masing-masing ternyata menghasilkan suatu algoritma baru (Brudy) yang bukan hanya memberikan solusi yang optimal tetapi juga dengan proses yang cukup cepat. Untuk pencarian solusi dengan perhitungan manual saja lebih mudah dan singkat apalagi jika algoritma Brudy ini diterapkan dalam pembuatan
27 program aplikasi. Memori yang digunakan untuk menjalankan program aplikasi lebih hemat (walaupun tidak sehemat menggunakan algoritma Greedy) tapi tetap memberikan solusi yang optimal. Secara kasarnya, kompleksitas untuk algoritma ini adalah: O(2bn2/b2). Jadi, jika b = n, maka kompleksitasnya menjadi O(2n), yang sama dengan algoritma Brute Force. Sebaliknya, jika b = 1, maka kompleksitasnya pun akan sama pula dengan algoritma Greedy, yaitu: O(2n2) = O(n2).
2.4
Dasar Perancangan Piranti Lunak
Menurut IEEE (Institute of Electrical and Electonics Engineers), perancangan piranti lunak didefinisikan sebagai penggunaan pendekatan yang sistematik, disiplin, dan dapat dikualifikasi dalam pengembangan, pengoperasian, dan pemeliharaan piranti lunak; atau juga berarti studi mengenai hal-hal tersebut (Pressman, 2001, p20).
2.5
Daur Hidup Perangkat Lunak
Salah satu model perancangan piranti lunak adalah dengan menggunakan model air terjun (Waterfall model). Perancangan program aplikasi dengan model Waterfall dilakukan dalam 5 tahap. Tahap-tahap tersebut adalah sebagai berikut. a. Analisis Analisis adalah suatu kegiatan untuk memnentukan topik dari masalah yang sedang duhadapi dan bagaimana cara pemecahan masalah tersebut.
28 b. Desain Dalam tahap ini ditentukan konsep dasara rancangan dari program aplikasi yang akan dibuat sehingga diharapakan dengan desain yang baik, maka para pengguna (user) akan merasa nyaman dalam menggunakan program aplikasi yang dirancang tersebut. c. Pengkodean (coding) Pada tahap ini dilakukan penulisan kode program sebagai penterjemahan hasil perancangan menjadi suatu bentuk yang dapat dimengert oleh mesin. d. Pengujian (testing) Pengujian dilakukan untuk mencari kelemahan dan kesalahan (error) yang terjadi pada program aplikasi. Kelemahan dan kesalahan tersebut diperbaiki sehingga dihasilkan suatu program aplikasi sesuai dengan yang diharapkan. e. Pemeliharaan (maintenance) Perangkat lunak akan mengalamai perubahan setelah disampaikan kepada pelanggan. Pemeliharaan perangkat lunak mengaplikasikan lagi setiap fase program sebelumnya dan tidak membuat yang baru lagi.
2.6
Teori Interaksi Manusia dan Komputer
Selain memiliki tampilan yang menarik, suatu program aplikasi yang baik tenetu harus user friendly. Yang dimaksud dengan user friendly (Shneiderman, 1998, p15) adalah sebagai berikut. 1) Waktu untuk balajar tidak lama. 2) Kecepatan dan ketepatan dalam penyajian informasi. 3) Tingkat kesalahan user rendah.
29 4) Cara penggunaan oleh user tidak gampang dilupakan. 5) Kepuasan pribadi. Selain itu, terdapat 8 hal penting yang harus diperhatikan dalam merancang program aplikasi (Shneiderman, 1998, p74-75), yaitu: 1) Konsistensi. 2) User dapat menggunakan fasilitas shortcut. 3) Memberi umpan balik yang informatif. 4) Merancang dialog yang memberikan penutup. 5) Mempunyai pencegahan kesalahan. 6) Adanya pilihan redo dan undo. 7) User sebagai pemegang kendali. 8) Mengurangi beban ingatan jangka pendek.
2.7
Pseudocode
Pseudocode (Pressman, 1999, p411) adalah suatu bahasa umum yang menggunakan kosa kata dari suatu bahasa (seperti bahasa Inggris) dan perintah (syntax) dari bahahas lain (seperti bahasa pemrograman terstruktur). Pseudocode biasanya dijadikan alternatif pilihan dalam perancangan piranti lunak selain alat bantu berupa diagram. Tidak ada standarisasi dalam hal penulisan pseudocode.
2.8
State Transititon Diagram
State Transititon Diagram (STD) adalah suatu alat bantu yang digunakan untuk memodelkan suatu sistem yang memiliki ketergantungan terhadap waktu. STD memiliki suatu tingkah laku suatu sistem dengan menggambarkan state dan kejadian yang
30 menyebabkan suatu state berubah ke state lain. Komponen-komponen pada STD adalah sebagai berikut. 1) State,disimbolkan dengan State mempresentasikan reaksi yang muncul setelah suatu kejadian dilakukan. Ada 2 jenis state yaitu state awal dan state akhir. State akhir dapat terdiri dari beberapa state tapi state awal hanya boleh berupa satu state. 2) State Transititon, disimbolkan dengan Label tersebut menunjukan kejadian yang menyebabkan transisi tersebut terjadi. 3) Kondisi dan aksi, disimbolkan dengan
Kondisi berfungsi mengubah state dan aksi adalah tindakan yang dilakukan sistem ketika state berubah. Kondisi dan aksi digambarkan dengan anak panah yang menghubungkan 2 state yang berkaitan.
