METODE GREEDY

APLIKASI ALGORITMA GREEDY DALAM PENENTUAN
SPESIFIKASI KOMPUTER RAKITAN
Hadyan Ghaziani Fadli – NIM : 13505005
Program Studi Teknik Informatika, Institut Teknologi Bandung
Jl. Ganesha 10, Bandung
E-mail : if15005@students.if.itb.ac.id
Abstrak
Makalah ini membahas tentang salah satu Aplikasi algoritmaGreedy dalam kehidupan masyarakat. Dalam
hal ini saya membahas penggunaan Algoritma Greedy dalam pemilihan spesifikasi kombinasi hardware
dalam perakitan komputer berdasarkan budget maksimum yang disediakan untuk mendapatkan performa
komputer yang terbaik. Saya memberikan batasan hardware yang akan dipilih hanya meliputi Processor,
Memory dan Graphic card.
Greedy yang berarti rakus, namun secara istilah algoritma greedy adalah salah satu algoritma yang
dipakai untuk mendapatkan hasil terbaik. Untuk mendapatkan hasil terbaik tersebut, dilakukan kombinasi
greedy terhadap kombinasi objek. Algoritma ini akan memilih hasil terbaik dari tiap sifat, kemudian akan
dilakukan kombinasi dari tiap sifat tersebut
Dalam Aplikasinya, saya akan melakukan greedy kepada tiap tipe objek pada hal ini adalah
Processor, Memory dan Graphic card, dengan sifat – sifat yang digunakan adalah benchmark, harga dan
besar pengaruh objek tersebut terhadap performa komputer.
Untuk pengembangan selanjutnya dapat dibuat Pilihan untuk kombinasi tersebut, yaitu apakah
komputer ini akan digunakan untuk pengetikan biasa yaitu komputer yang memiliki nilai tertinggi yang
overall, game atau desain grafis yang memiliki nilai tertinggi di graphic card,perhitungan scientific yaitu
yang memiliki nilai tertinggi di processor dan lain lain.
Inti Makalah
1. Pendahuluan
Manusia yang baik adalah manusia
yang dapat berguna untuk sesamanya. Jika kita
memiliki suatu ilmu, sangat baik jika kita dapat
mengamalkan ilmu tersebut untuk kebaikan.
Sebagai mahasiswa teknik informatika
ITB, hendaknya dengan ilmu yang didapat dapat
diimplementasikan dan diaplikasikan untuk
masyarakat.
Dengan dasar tersebut saya mencoba
mengimplementasikan dan mengaplikasikan
algoritma Greedy untuk sesuatu yang dapat
digunakan oleh banyak orang, dalam hal ini
adalah penggunaan algoritma Greedy untuk
membantu memilih spesifikasi komputer.
Namum Pada saat ini saya memberi
batasn hanya terhadap Processor, Memory dan
Graphic card.
2. Algoritma Greedy
Dalam kehidupan sehari hari , banyak terdapat
persoalan yang menuntut pencarian solusi
optimum. Persoalan tersebut dinamakan
persoalan optimasi(optimization Problems).
Persoalan Optimasi adalah persoalan
yang tidak hanya mencari sekedar solusi, tetapi
mencari solusi terbaik. Solusi terbaik adalah
solusi yang memiliki nilai minimum atau
meksimum dari sekumpulan alternatif solusi
yang mungkin
Algoritma Greedy adalah salah satu
algoritma yang dapat digunakan untuk
mendapatkan solusi terbaik dan merupakan
algoritma yang palin populer dalam hal ini.
Secara Harfiah Greedy artinya rakus
atau tamak, sifat yang berkonotasi negatif. Orang
yang memiliki sifat ini akan mengambil
sebanayak mungkin atau mengambil yang paling
bagus atau yang paling mahal. Sesuai dengan arti
tersebut, Prinsip Greedy adalah take what you
can get now.
Dalam kehidupan sehari hari Greedy
dapat digunakan dalam masalah seperti :
• Memilih beberapa jenis investasi
• Mencari jalur tersingkat
Ada juga yang dapat dilakukan algoritma ini
dalam sesuatu yang biasa dilakukan mesyarakat
modern, yaitu memilih spesifikasi komputer
yang terbaik dengan budget maksimum tertentu
seperti yang akan dibahas dalam makalah ini.
2.1 Definisi Algoritma Greedy
Algoritma Greedy membentuk solusi langkah
per langkah (step by step). Terdapat banyak
pilihan yang perlu di eksplorasi pada setiap
langkah solusi, karenanya pada setiap langkah
harus dibuat keputusann yang terbaikdalam
menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah
lagi pada langkah selanjutnya. Sebagai contoh,
jika kita manggunakan algoritma Greedy untuk
menempatkan komponen diatas papan sirkuit,
sekali komponen telah diletakkan dan dipasang
maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum
lokal. Bila algoritma berakhir, kita berharap
optimum lokal menjadi optimum global.
2.2 Skama 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 bersamasama
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.
5. Fungsi obyektif, yaitu fungsi yang
memaksimumkan atau meminimumkan nilai
solusi (misalnya panjang lintasan,
keuntungan, dan lain-lain).
Contoh pada masalah Pemilihan Processor,
berdasarkan benchmark elemen-elemen
algoritma greedy-nya adalah:
1. Himpunan kandidat: himpunan hardware
yang terdiri dari Processor, Memory dan
Graphic card
2. Himpunan solusi: Kombinasi Processor ,
Memory dan Graphic card dengan
Benchmark terbaik namun dengan total
harga yang tidak melebihi budget
maksimum
3. Fungsi seleksi: Seleksi Processor, Memory
dan Graphic card agar mendapat
performaoptimum dan tidak melebihi
budget maksimum yang tersedia
4. Fungsi obyektif: Budget maksimum yang
tersedia
2.3 Pseudo Code Algoritma Greedy
procedure greedy(input C:
himpunan_kandidat;
output S :
himpunan_solusi)
{ menentukan solusi optimum dari
persoalan optimasi dengan
algoritma greedy
Masukan: himpunan kandidat C
Keluaran: himpunan solusi S
}
Deklarasi
x : kandidat;
Algoritma:
S←{} {
inisialisasi S dengan kosong
}
while (belum SOLUSI(S)) and
(C ≠ {} ) do
x←SELEKSI(C); { pilih
sebuah kandidat dari C}
C← C - {x} { elemen
himpunan kandidat berkurang
satu }
if LAYAK(S ∪ {x}) then
S←S ∪ {x}
endif
endwhile
{SOLUSI(S) sudah diperoleh or
C = {} }
• Pada akhir setiap lelaran, solusi yang
terbentuk adalah optimum lokal. Pada
akhir kalang while-do diperoleh
optimum global.
• Namun adakalanya optimum global
merupakan solusi sub-optimum atau
pseudo-optimum. Alasan:
1. algoritma greedy tidak beroperasi
secara menyeluruh terhadap semua
alternatif solusi yang ada (sebagaimana
pada metode exhaustive search).
2. pemilihan fungsi SELEKSI: Mungkin
saja terdapat beberapa fungsi SELEKSI
yang berbeda, sehingga kita harus
memilih fungsi yang tepat jika kita
ingin algoritma bekerja dengan benar
dan menghasilkan solusi yang benarbenar
optimum
• Karena itu, pada sebagian masalah
algoritma greedy tidak selalu berhasil
memberikan solusi yang benar-benar
optimum.
• Jika jawaban terbaik mutlak (benarbenar
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
3. Pemilihan Hardware Komputer
3.1 Batasan dan Atribut uji
Pada Makalah ini yang akan dites hanyalah
Processor, Memory dan Graphic card. Atribut
yang akan dimasukkan sebagai data masukan
adalah harga dan benchmark dari tiap objek
tersebut
3.2 Cara Pengujian
Akan dibuat semua kombinasi yang mugkin
tetapi dibatasi oleh budget maksimum yang
disediakan, kemudian dilakukan pencarian solusi
optimum untuk memilih kombinasi terbaik
dengan cara kombinasi greedy dengan performa,
greedy dengan harga dan greedy dengan
performa / harga.
4 Aplikasi Algoritma Greedy
4.1 Metode Aplikasi Algoritma Greedy
Cara yang akan digunakan untuk
mengaplikasikan algoritma greedy adalah :
1. Untuk mempercepat waktu akan
dilakukan beberapa kali sort produk
2. Setiap Objek akan disortir tidak akan
melebihi budget maksimum.
3. Dibuat Kombinasi dari ketiga objek,
kemudian disortir kembali hingga yang
tersisia adalah kombinasi yang tidak
melebihi budget maksimum.
4. Greedy dilakukan terhadap dengan
performa / harga yang berada diantara
budget maksimum dan budget
minimum ataupun dengan performa
terhadap budget maksimum
Tabel 1. Daftar Harga dan Spesifikasi Hardware
4.2 Pengujian
Dengan tabel diatas , dengan budget $300 dan
pemilihan
1. Greedy by Performance maka didapatkan
hasil performa terbaik yaitu kombinasi :
• Processor : Intel core 2 Duo 6400
• Memory : 1GB 1000MHz
• Graphic Card : GeForce 7600 GS
Dengan nilai performance total 2150 dan
harga$290
2. Greedy By Performace / Price maka
didapatkan Hasil dengan kombinasi :
• Processor : Intel core 2 Duo 4300
• Memory : 2GB 800MHz
• Graphic Card : GeForce 7600 GS
Dengan nilai performance total 1940 dan
harga$280 serta nilai Performance / price =
20,00758
5. Pengembangan Aplikasi lebih lanjut
Untuk pengembangan lebih lanjut dapat
dimasukkan seluruh komponen komputer lainnya
dan jenis komputer dibuat sesuai Pilihan untuk
kombinasi tersebut,sesuai keperluan yaitu :
1. Overall : yaitu komputer yang
memiliki nilai tertinggi yang overall,
greedy dilakukan seperti pada makalah
ini.
2. game atau desain grafis : yaitu
Komputer yang memiliki nilai tertinggi
di performa graphic card,
3. Perhitungan scientific yaitu yang
memiliki nilai tertinggi di processor dan
lain lain.
4. Storage : yaitu komputer dengan nilai
performa hardisk tertinggi
5. Kegunaan lainnya yang dapat
disesuaikan
Memory Price Performance To Computer Performance / Price
Kingston 2 x 2 Gb 1000
Mhz 300 1000 3,333333333
Kingston 2 Gb 1000 Mhz 140 500 3,571428571
Kingston 2 Gb 800 Mhz 100 400 4
Kingston 2 GB 667 Mhz 80 340 4,25
Kingston 1 GB 1000 Mhz 50 250 5
Processor
Intel Core 2 Duo 6600 200 1500 7,5
Intel Core 2 Duo 6400 150 1300 8,666666667
Intel Core 2 Duo 4300 110 1000 9,090909091
Dual Core 2.8 90 800 8,888888889
Dual Core 2.0 70 600 8,571428571
Graphic Card
GeForce 8500 GT 150 1000 6,666666667
GeForce 7600 GT 180 950 5,277777778
GeForce 7600 GS 90 600 6,666666667
ATI X1600 150 800 5,333333333
ATI X1300 80 500 6,25
6. Kesimpulan
Kesimpulan yang dapat diambil adalah :
1. Penggunaan algoritma greedy dapat
diterapkan dalam berbagai hal dalam
kehidupan terutama yang berhubungan
dengan pemilihan kombinasi objek
dengan hasil optimum
2. Dalam permasalahan pemilihan
spesifikasi computer, variasi algoritma
greedy dapat dipakai untuk memilih
spesifikasi computer yang sesuai
dengan kebutuhan dan budget yang
disediakan
3. Kombinasi algoritma greedy dapat
memberikan pilihan terbaik untuk
berbagai permasalahan, karena banyak
hal yang akan menentukan nilai terbaik
suatu kombinasi produk dalam hal ini
DAFTAR PUSTAKA
[1] Munir, Rinaldi. (2004). Diktat Kuliah
Strategi Algoritmik. Departemen Teknik
Informatika, Institut Teknologi Bandung.