Permainan
Minesweeper dengan Algoritma BFS
dan
Optimasi Algoritma Greedy
Nama
: Ady Mulyono
NIM
: 0110214018
Tugas
: Kecerdasan Buatan
Minesweeper merupakan salah satu permainan yang sudah terinstall pada
sistem operasi Windows. Permasalah pada permainan ini adalah menemukan seluruh
ranjau bom pada kumpulan petak yang ada tanpa meledakannya. Cara menemukan
ranjau adalah menggunakan petunjuk yang ada pada petak yang terbuka (non
ranjau), petak tersebut berisikan angka yang menyatakan banyaknya ranjau yang
ada disekitar petak yang berisikan angka tersebut.
1.
Pendahuluan
Minesweeper
adalah sebuah permainan single-player. Tujuan dari permainan ini adalah untuk
menghapus papan persegi panjang yang tersembunyi, "ranjau adalah jebakan
bom yang dipasang" tanpa meledakkan salah satu dari ranjau, dengan bantuan
dari petunjuk tentang jumlah tambang tetangga di masing-masing bidang.
Permainan berasal dari tahun 1960-an, dan telah ditulis untuk banyak platform
komputasi yang digunakan saat ini. Ini memiliki banyak variasi dan cabang. Game
Komputer ini menggunakan strategi dan kesempatan.
Breadth-first
search (BFS) adalah sebuah algoritma untuk melintasi atau mencari pohon atau
grafik struktur data. Dimulai pada akar pohon (atau beberapa simpul
sewenang-wenang dari grafik, kadang-kadang disebut sebagai 'kunci pencarian)
dan mengeksplorasi tetangga node pertama, sebelum pindah ke tetangga tingkat
berikutnya.
BFS
diciptakan pada akhir 1950-an oleh E. F. Moore, yang digunakan untuk menemukan
jalur terpendek dari labirin, dan
ditemukan secara independen oleh C. Y. Lee sebagai algoritma kawat routing.
2.
Algoritma
Greedy dan Implementasinya Pada Program Java
Algoritma
greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai
dalam implementasi sebuah system atau program yang menyangkut mengenai
pencarian “optimasi”.
Di dalam mencari sebuah solusi (optimasi) algoritma
greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:
1. Maksimasi (maxizimation)
2. Minimasi (minimization)
Solusi optimum
(terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif
solusi yang mungkin.
Elemen persoalan optimasi:
1. Kendala (constraints)
2. Fungsi objektif (fungsi optiamsi)
Solusi yang
memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak
yang mengoptimumkan fungsi optimasi disebut solusi optimum.
Algoritma
greedy merupakan metode yang paling populer untuk memecahkan persoalan
optimasi.
Greedy = rakus, tamak, loba, ….
Prinsip greedy adalah: “take what you can get now!”.
Contoh masalah sehari-hari yang menggunakan prinsip
greedy:
Permainan
Minesweeper
Memilih beberapa jenis investasi (penanaman modal)
Mencari jalur tersingkat dari Bandung ke Surabaya
Memilih jurusan di Perguruan Tinggi
Pendekatan
yang digunakan di dalam algoritma greedy adalah membuat pilihan yang
“tampaknya” memberikan perolehan terbaik yaitu dengan membuat pilihan optimum
lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global
optimm).
Algoritma
greedy adalah algoritma yang memecahkan masalah langkah per langkah pada setiap
langkah:
Mengambil pilihan yang terbaik yang dapat diperoleh
pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you
can get now!”)
Berharap bahwa dengan memilih optimum lokal pada
setiap langkah akan berakhir dengan optimum global.
Pada setiap
langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum
lokal menjadi optimum global.
3.
Skema Umum
Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen berikut:
1. Himpunan kandidat berisi elemen-elemen pembentuk
solusi.
2. Himpunan solusi berisi kandidat-kandidat yang
terpilih sebagai solusi persoalan.
3. Fungsi seleksi (selection function) memilih kandidat
yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih
pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
4. Fungsi kelayakan (feasible) memeriksa apakah suatu
kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat
tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak
melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke
dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak
pernah dipertimbangkan lagi.
5. Fungsi obyektif yaitu fungsi yang memaksimumkan
atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan
lain-lain).
4.
Flow Chart
5.
Implementasi
6.
Screan
Shout
7.
Kesimpulan
Tidak ada komentar:
Posting Komentar