LAPORAN PRAKTIKUM VIII DESAIN DAN ANALISIS ALGORITMA Backtracking Buatlah Program Python untuk penyelesaian Maze Problem dan N-Queen Problem PDF

Preview

Summary

LAPORAN PRAKTIKUM VIII DESAIN DAN ANALISIS ALGORITMA Backtracking Buatlah Program Python untuk penyelesaian Maze Problem dan N-Queen Problem Disusun Oleh : MARIQUITO ALVES SIMÕES 17330004 FAKULTAS TEKNIK JURUSAN INFORMATIKA UNIVERSITAS JANABADRA YOGYAKARTA 2018 DAFTAR ISI HALAMAN JUDUL ........ DAFT...

Description

LAPORAN PRAKTIKUM VIII DESAIN DAN ANALISIS ALGORITMA Backtracking Buatlah Program Python untuk penyelesaian Maze Problem dan N-Queen Problem

Disusun Oleh : MARIQUITO ALVES SIMÕES 17330004 FAKULTAS TEKNIK JURUSAN INFORMATIKA UNIVERSITAS JANABADRA YOGYAKARTA 2018

DAFTAR ISI

HALAMAN JUDUL………………………………………………………………………........ DAFTAR ISI………………………………………………………………………………........ BAB I PENDAHULUAN 1. Latar Belakang……………………………………………………………………...... 2. Tujuan……………………………………………………………………………....... BAB II DASAR TEORI 1. Pengertian Python untuk penyelesaian Maze Problem dan N-Queen Problem........... BAB III TUGAS 1. Buatlah Program Python untuk penyelesaian Maze Problem dan N-Queen Problem. BAB IV PENUTUP 1. Kesimpulan………………………………………………………………………....... 2. Daftar Pustaka.............................................................................................................

BAB I PENDAHULUAN 1 . Latar Belakang Chess atau akrab dikenal dengan catur adalah satu dari permainan board game yang sudah sangat terkenal, bahkan permainan ini sudah ada dari ratusan tahun yang lalu. Permainan ini

menuntut

kita

untuk berpikir sedemikian rupa sehingga kita dapat mengalahkan

pertahanan lawan. Tentunya diperlukan suatu kepintaran lebih untuk melakukan hal ini, salah satu pengembangan dari board game catur adalah permainan knight logic problem’sdan 8-queen problem’s. Knight logic problem’s dan 8-queen problem’smerupakan salah satu jenis permainan yang menggunakan dasar permainan catur, tapi dalam knight logic problem’s dan 8-queen problem’s hanya menggunakan satu buah bidak kuda dan delapan (8) buah bidak ratu. Selain itu, knight logic problem’s dan 8-queen problem’s ini sangat rumit dan sukar untuk diselesaikan secara manual. Karena total dari 98% responden berpendapat bahwa permainan dari knight logic problem’s dan 8-queen problem’s membutuhkan waktu dalam penyelesaiannya. Hal ini disebabkan karena pada knight logic problem’s dan 8-queen problem’s tidak ada informasi tambahan yang dimiliki

untuk membantu melakukan

pencarian solusi dari permainan tersebut. Dan total dari 76%

responden berpendapat

dengan adanya permainan tersebut dapat

menambah ragam permainan board game yang telah ada sehingga dapat digunakan sebagai salah satu media alternatif untuk mengisi waktu senggang dan juga termasuk salah satu jenis permainan edukasi sehingga dapat digunakan untuk melatih kemampuan nalar dan logika seseorang. Algoritma pencarian yang efektif dapat diterapkan untuk menyelesaikan persoalan tersebut. Salah satunya adalah dengan menggunakan algoritma Breadth-First Search. Dengan metode ini, semua node akan ditelusuri dan node-node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Penggunaan metode ini mampu menemukan suatu solusi terpendek dalam waktu dan tingkat tertentu.

2 . Tujuan Tujuan dari pembuatan aplikasi yang akan dibangun, yaitu : 1. Aplikasi ini breadth first search problem’s.

dibuat bertujuan untuk mengimplementasikan penerapan algoritma dalam penyelesaikan permainan knight logic problem’s dan 8-queen

2. Untuk merancang suatu perangkat lunak yang dapat mencari solusi dari permainan knight logic problem’s dan 8-queen problem’s. Manfaat dari pembuatan aplikasi yang akan dibangun, yaitu membantu mencari solusi dari permainan knight logic problem’s dan 8-queen problem’s.

BAB II DASAR TEORI Runut balik (backtracking) merupakan algoritma yang berbasis pada DFS (Depth First Search) untuk mencari solusi persoalan secara lebih optimal. Runut balik merupakan perbaikandari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semuakemungkinan solusi yang ada. Perbedaan utamanya adalah pada konsep dasarnya, yauti pada backtracking semua solusi dibuat dalam bentuk pohon solusi (tree), dan kemudian pohontersebut akan ditelusuri secara DFS sehingga ditemukan solusi terbaik yang diinginkan.Dengan metode runut-balik, kita tidak perlu memeriksa semua kemungkinan solusi yangada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimabangkan. Akibatnya,waktu pencarian dapat dihemat. Saat ini algoritma runut balik balik diterapkan untuk permainangames (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, danlainlain) dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence).

Misalkan pohon di atas menggambarkan solusi dari suatu persoalan. Jika kita inginmencari solusi dari A ke E, maka jalur yang harus ditempuh adalah (A-B-E). Demikian jugauntuk solusi-solusi yang lain. Algoritma Backtracking akan memeriksa jalur secara DFS, yaitudari solusi terdalam pertama yang ditemui yaitu solusi E. Jika ternyata E bukanlah solusiyang diharapkan, maka pencarian akan dilanjutkan ke F. Jalur yang harus dilalui untuk bisamencapai E adalah (A-B-E) dan untuk mencapai F adalah (A-B-F). Kedua solusi tersebutmemiliki jalur awal yang sama, yaitu (A-B). Jadi, daripada memeriksa ulang jalur dari Akemudian B, maka jalur (A-B) disimpan dulu dan langsung memeriksa solusi F. Untuk kasuspohon yang lebih rumit, cara ini dianggap lebih efisien daripada jika menggunakanalgoritma Brute-Force.

BAB III TUGAS 1. Buatlah Program Python untuk penyelesaian Maze Problem dan N-Queen Problem:

Hasil Run:

2.N-Queen Problem:

Hasil Run:

BAB IV PENUTUP

1 . Kesimpulan dalam algoritma BFS dapat digunakan untuk menemukan jarak terpendek dari suatu tempat ke tempat lainnya, selama kita dapat memodelkan pertanyaan sebagai graf tak-berbobot atau berbobot 1. Kita juga dapat mengaplikasikan algoritma BFS ke graf berbobot dengan memecah sisinya menjadi sisi-sisi yang berbobot satu. Kelemahan algoritma BFS adalah untuk graf yang besar dengan jarak dari simpul awal dengan simpul akhir yang jauh dibutuhkan waktu yang lama, karena BFS akan menelusuri seluruh simpul yang jaraknya kurang dari jarak simpul awal ke simpul akhir, namun selama ada jalan antara simpul awal dan akhir, BFS dijamin akan bisa menemukan jalan terpendek.

BAB V DAFTAR PUSTAKA [1]Munir, Rinaldi. 2009. “Diktat Kuliah IF 2251 Strategi Algoritmik”. Bandung: Program Studi Teknik Informatika STEI ITB. [2]Halim, Steven., Halim, Felix, 2013. “Competitive Programming, 3rd Edition”. [3]Cormen, Thomas H., et al. “Introduction to Algorithms, 3rd Edition”. MIT Press. [4]Joshi, R., Treiman, R., Carreker, S., & Moats, L.. (2008-2009, Winter). The real magic of spelling: Improving reading and writing. American Educator , 9.http://www.aft.org/sites/default/files/periodicals/joshi.pdf p. 10. [5]http://www.spellingcity.com/importance-of-spelling.html The Importance of Spelling by Susan Jones, M.Ed. 2/2009 Diakses pada Sabtu, 7 Mei 2016 jam 11.37 [6]http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf diakses pada Sabtu, 7 Mei 2016 13.26 WIB [7]https://xlinux.nist.gov/dads//HTML/Levenshtein.html diakses pada Sabtu, 7 Mei 2016 20.12 WIB...