IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PERMAINAN N-PUZZLE

22074281, Arnanda Danur Wicaksono (2012) IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PERMAINAN N-PUZZLE. Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22074281_bab1_bab5_daftarpustaka.pdf Download (2MB)
	Text (Skripsi Informatika) 22074281_bab2-sd-bab4_lampiran.pdf Restricted to Registered users only Download (2MB) | Request a copy

Abstract

Permainan N-Puzzle merupakan permainan yang menggunakan logika untuk dapat menyelesaikannya, sehingga permainan ini akan mengasah logika pemainnya. Permainan ini diselesaikan dengan cara menggeser angka-angka acak yang terdapat didalamnya sehingga dapat menjadi angka yang urut. User dalam memainkan N-Puzzle terkadang mengalami kesulitan dalam menentukan langkah yang harus diambil, sehingga sistem memberikan bantuan berupa hint yang akan memberikan solusi bagi user. Algoritma yang diterapkan pada hint dalam permainan N-Puzzle ini adalah algoritma branch and bound. Penerapan algoritma branch and bound pada permainan N-Puzzle di papan dengan ukuran 3x3, 4x4 dan 5x5 mampu menemukan solusi yang diinginkan, yaitu kondisi dimana angka tersusun secara urut. Namun dalam penerapan algoritma branch and bound pada permainan N-Puzzle terdapat masalah yaitu dalam perhitugan nilai cost terdapat nilai yang mempunyai besar nilai cost yang sama dan hal ini mengalami perulangan, sehingga menyebabkan permainan tidak dapat terselesaikan. Dalam kasus ini semakin besar ukuran papan, maka algoritma branch and bound kurang efektif dalam menyelesaikan permainan. Dari percobaan yang dilakukan presentase keberhasilan papan dengan ukuran 3x3 adalah 98% sedangkan ukuran 4x4 mempunyai presentase keberhasilan 72% dan ukuran 5x5 mempunyai presentase keberhasilan 53%.

Actions (login required)

View Item