Aplikasi Algoritma Greedy dan Program Dinamis (Dynamic Programming) pada Permainan Greedy Spiders

Abstract

Semakin pesatnya perkembangan teknologi, perkembangan games pun semakin maju. Greedy Spiders merupakan salah satu game untuk smartphone yang berbasis seperti Android yang dikembangkan oleh Blyts sebuah software house. Pada game ini terdapat laba-laba yang ingin memakan serangga yang terjebak di jaring laba-laba tersebut. Laba-laba tersebut merupakan Artificial Intelligence (AI) pada permainan ini, yang akan menjadi lawan bagi pemain dalam menyelesaikan permainan ini. Tugas pemain adalah menyelamatkan serangga yang terjebak sehingga laba-laba tidak dapat memakan serangga tersebut dengan cara memutuskan beberapa sisi pada jaring laba-laba. Algoritma Greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Algoritma Greedy membentuk solusi langkah per langkah. Program Dinamis (Dynamic Programming) adalah suatu metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas, dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya. Algoritma Greedy digunakan untuk mengetahui pergerakan laba-laba, kemudian program dinamis (dynamic programming) pada permainan Greedy Spiders digunakan untuk mencari solusi optimal dari pergerakan laba-laba ke serangga, yaitu mencari jalur terpendek dari pergerakan laba-laba ke serangga sehingga pemain dapat memutuskan jaring mana yang akan dipotong untuk memperoleh hasil yang maksimal atau dalam hal ini pemain dapat memperoleh skor tertinggi.