Mengenal algoritma Greedy

Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.

Algoritma Greedy membentuk solusi langkah per langkah, terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. keputusan yang telah di ambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Contoh penempatan komponen diatas papan sirkuit, sekali komponen telah di letakan dan di pasang maka tidak bisa di pindahkan lagi
contoh aplikasi menggunakan Algoritma Greedy (game TD "tower defanse ")
Permainan Tower Defense (TD) merupakan permainan strategi pengaturan tower (bangunan,senjata, naga, tanaman, dll) yang bertujuan menghentikan musuh yang akan melintas. Tower iniakan menembaki musuh dalam radiusnya. Tower memiliki beberapa tipe dan level dengan kemampuan, biaya pembelian, biaya penggunaan, dan biaya upgrade yang berbeda. Untuk setiap musuh yang berhasil dikalahkan, pemain akan mendapatkan uang untuk meng-upgrade towers. Strategi dalam permainan ini mencakup pemilihan tower yang akan di-upgrade. Permainan ini biasanya memiliki misi untuk meminimalkan jumlah musuh yang lolos atau menjaga sejumlah barang. Pemain dianggap menang jika jumlah musuh yang lolos kurang dari batas yang ditentukan atau barang yang dijaga masih ada.

Di dalam tugas ini, Anda diminta mengaplikasikan algoritma greedy untuk memenangkan permainan TD. Komputer bermain menggunakan algoritma greedy, sedangkan manusia bermain menggunakan akal dan intuisinya. Program yang dibuat harus memungkinkan melakukan permainan TD dengan pemainnya adalah:

1. User (manusia) lawan komputer

2. Komputer dengan dirinya sendiri.

Jika pemainnya adalah user (manusia) versus komputer, maka manusia akan mengatur kemampuan sejumlah tower yang ada, dan komputer akan mengaplikasikan algoritma greedy untuk melakukan penyusunan rombongan musuh (wave) agar semakin banyak musuh yang dapat lolos. Penyusunan rombongan musuh dibatasi oleh jumlah uang yang tersedia. Penyusunan wave ini akan dilakukan setelah tower selesai diatur.

Jika pemain adalah komputer versus dirinya sendiri, maka pihak komputer pertama mengaplikasikan algoritma greedy untuk penyusunan wave, dan pihak komputer kedua mengaplikasikan algoritma greedy untuk pengaturan kemampuan tower. Pengaturan tower akan dilakukan setelah hasil penyusunan wave diberikan. Anda harus merancang minimal masing-masing dua buah strategi greedy yang berbeda (greedy by

X dan greedy by Y) untuk penyusunan rombongan musuh (wave) dan strategi pengaturan kemampuan tower. Deskripsi algoritma greedy tersebut harus dapat memperlihatkan properti algoritmanya, yaitu himpunan kandidiat, himpunan solusi, fungsi seleksi, fungsi kelayakan, dan fungis obyektif.