Program untuk Memecahkan 15-Puzzle dengan Menggunakan Algoritma Branch and Bound
Telusuri Dokumen>>
Table of Contents
Program ini merupakan program pencarian solusi pada Permainan 15-Puzzle dengan pengaplikasian algoritma Branch and Bound. Aplikasi disediakan dalam bentuk Graphical User Interface dan Command Line Interface. GUI dibuat dengan menggunakan tools Qt Designer dan PyQt5
-
Sediakan list notVisited dan list visited.
-
Input suatu Puzzle dan dijadikan sebagai root Puzzle. Masukkan root Puzzle ke dalam list notVisited
-
Untuk setiap Puzzle pada list notVisited, hitung costnya dengan heuristik
c(x) = f(x) + g(x)
Keterangan :
- c(x) = cost untuk simpul x
- f(x) = cost untuk mencapai simpul x dari akar
- g(x) = taksiran panjang lintasan terpendek dari P ke simpul solusi
Pilih Puzzle dengan cost terendah sebagai currentPuzzle
-
Periksa apakah puzzle merupakan solusi atau tidak
- Jika ya, maka pencarian dihentikan
- Jika tidak, lanjutkan
-
Tentukan pergerakan selanjutnya yang memungkinkan. Syarat pergerakan yang memungkinkan :
- Slot kosong pada puzzle bergerak ke arah kiri, kanan, atas, atau bawah.
- Pergerakan tersebut tidak menghasilkan Puzzle yang sudah pernah dikunjungi (tidak terdapat pada list visited)
-
Hapus currentPuzzle dari list notVisited dan 7.masukkan ke dalam listVisited
-
Kembali ke langkah 2
-
Buka command line dan arahkan firectory ke folder src
-
Jalankan dengan command
python cliTest.py
- Buka folder bin dan run file main.exe
- Masukkan input (dapat dilakukan secara manual maupun dengan mengarahkan directory menggunakan tombol file di kanan bawah)
- Tekan tombol search yang ada di bawah input puzzle
- Tunggu sampai kolom solusi menampilkan hasil
- Kecepatan animasi puzzle dapat diubah dengan menggunakan horizontal slider
- 13520079 Ghebyon Tohada Nainggolan