APLIKASI ALGORITMA GREEDY DAN PROGRAM DINAMIS (DYNAMIC PROGRAMMING) PADA PERMAINAN GREDDY SPIDERS - Zulhidayati, Ika (2013)
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. Kata Kunci: Algoritma Greedy, Program Dinamis (Dynamic Programming), serangga, jaring laba-laba, laba-laba. As the technology rapidly develops, the development of games follows. Greedy Spiders is a game for smartphone with such system as Android developed by Blyts, a software house. There is spider in this game wishing to eat insects that are trapped on a spider web. The spider is an Artificial Intelligence (AI) in this game, which will be the opponent of player in completing this game. Player's duty is to save the trapped insects, so that the spider will not get any chance to eat those insects. The step is to cut the spider web by tapping it. Greedy algorithm is one most popular method in solving optimization problems. It provides step by step solution. Dynamic programming is a problem shooting method which disentangles solutions into a set of steps in such a way, so that the solution of the problem is known as a combination of interrelated conclusions. On dynamic programming, an optimum combination of conclusions is made by applying principle of optimally, this principle guarantees that a conclusion taken on one step will be the correct conclusion on the following steps. Greedy algorithm is used in noticing the spider's movement, while, dynamic programming on Greedy Spiders game is used to find the optimal solution of it, which is to find the shortest path between spider and insects so the player can decide which nets to cut in which it aims at getting the best result, or, in this case to get the highest score. Keywords: Greedy Algorithm, Dynamic Programming, insects, spider web, spider.