Implementasi Algoritma Depth First Search dalam Permainan Minesweeper Siti Maghfiroh 201310370311218 Metode Penelitian E Sumber : TA-TIF-UMM / Hariska G/ 2015
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
ImplementasiAlgoritmaDepth First Search dalam Permainan Minesweeper
Siti Maghfiroh201310370311218
Metode Penelitian E
Sumber : TA-TIF-UMM / Hariska G/ 2015
Masalah Mencari ranjau yang tersebar secara acak pada
petak permainan MinesweeperMencari petak yang bebas ranjau tanpa meledakkan bom pada permainan Minesweeper
Sumber : TA-TIF-UMM / Hariska G/ 2015
Metode
Depth First Search“ Algoritma yang bekerja dengan melintasi atau mencari sebuah pohon, struktur pohon, atau grafik.- Menggunakan pohon pencarian- Menemukan kedalaman pertama pada awal
permainan- Mengembangkan untuk mencari kedalaman
sehingga menemukan letak ranjau
Sumber : TA-TIF-UMM / Hariska G/ 2015
MetodeCara Kerja DFS pada kasus ini :- Buat ilustrasi petak yang telah dikondisikan dengan memberi keterangan angka pada tiap-tiap petak. Sample diambil pada permainan minesweeper level 1.
ImplementasiAlgoritmaBFS dengan OptimalisasiAlgoritma Greedydalam Permainan Minesweeper
Sumber : Paper-TIF-ITB/ Erdiansyah F.N/ 2010
Sumber : Paper-TIF-ITB/ Erdiansyah F.N/ 2010
Metode
BFSalgoritma
pencarian pada graf yang
dimulai dari simpul akar dan
menelusuri seluruh simpul tetangganya.
Menelusuri petak pada papan secara rekursif sehingga petak-petak tidak dapat ditelusuri lagi.
Papan akan membuka petaknya jika petak tersebut aman untuk dibuka dan menandai dengan bendera jika peta tersebut adalah ranjau
Jika pada penelusurannya menemukan sebuah petak yang belum dapat dipastikan makan petak tersebut akan disimpan dalam sebuah queue yang nantinya akan diproses lebih lanjut.
Sumber : Paper-TIF-ITB/ Erdiansyah F.N/ 2010
GreedyPendekatan yang
digunakan di dalam algoritma greedy adalah membuat
pilihan yang “tampaknya”
memberikan perolehan yang terbaik, yaitu dengan membuat
pilihan optimum lokal pada setiap langkah
dengan harapan bahwa sisanya
mengarah ke solusi optimum global.
Untuk petak-petak yang ada dalam queue maka akan diproses dengan algoritma greedy untuk ditentukan apakah petak tersebut aman untuk dibuka atau tidak.
menghitung persentase kemungkinan petak itu ranjau berdasarkan analisis multi-squre
kemudian dipilihlah petak yang memiliki persentase ranjau yang paling kecil.
Prosesnya yaitu menelusuri queue mulai dari head. Jika petak tersebut memiliki presentase yang paling kecil maka petak tersebut akan dibuka dan petak tersebut dihapus dari queue, jika petak head bukan petak yang memiliki persentase paling kecil maka petak tersebut dipindah ke tail.
Related Documents
