BAB II. KAJIAN PUSTAKA
A.
Algoritma Backtracking Graf merupakan cikal bakal dari Depth First Search, Depth First Search merupakan graf khusus atau sering disebut dengan pohon pencarian. 1. Pengertian depth first search Depth First Search pertama kali diperkenalkan oleh Tarjan dan Hopcrof 22 tahun yang lalu, depth first search dapat digunakan untuk membangun sejumlah algoritma graf yang efisien. Pencarian mendalam pertama (Depth First Search) adalah Pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri (Suyanto, 2007).
Gambar 1. Depth First Search.
2. Algoritma depth first seacrh (Kusumadewi, 2003) : a. Jika keadaan awal merupakan tujuan, keluar (sukses). b. Jika tidak demikian, kerjakan langkah-langkah berikut ini sampai tercapai keadaan sukses atau gagal. -
Bangkitkan succesor E dari kedaan awal. Jika tidak ada succesor, maka akan terjadi kegagalan.
-
Panggil depth first search dengan E sebagai kedaan awal.
-
Jika sukses berikan tanda sukses. Namun jika tidak, ulangi langkah-2.
4 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Algoritma backtracking diperkenalkan pertama kali oleh D.H Lehmer pada tahun 1950. 1. Pengertian algoritma backtraking Mencari solusi dari persoalaan di antara semua kemungkinan yang ada merupakan penjelasan sistematis dari algoritma brute force, algoritma backtracking dikenal sebagai perbaikkan dari algoritma brute force. Algoritma backtracking adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus (Munir, 2006). 2. Perbedaan algoritma brute force dan backtracking Perbedaan mendasar algoritma burte force dan algoritma backtracking adalah waktu pencariannya. Algoritma algoritma
backtracking dalam
pencarian solusinya menghemat waktu dikarenakan tidak perlu membentuk kemungkinan solusi untuk dicari solusi, sedangkan brute force menentukan kemungkinan solusinya terlebih dahulu, lalu mencari solusi dari kemungkinan solusi tersebut. 3. Langkah-langkah pencarian solusi : a. Solusi dicari membentuk lintasan dari akar kedaun. Simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup diperluas dinamakan simpul-E (Expand-node). b. Jika lintasan yang diperoleh dari perluasan simpul-E tidak mengarah ke solusi maka, simpul itu akan menjadi simpul mati dimana simpul itu tidak akan diperluas lagi. c. Jika posisi terakhir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak yang lainnya dan jika tidak ada simpul anak maka dilakukan runut balik (backtrackking) kesimpul induk. d. Pencarian dihentikan jika telah menemukan solusi atau tidak ada simpul hidup yang dapat di perlukan.
5 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Gambar 2. Algoritma Backtracking. B.
Jenis-Jenis Puzzle Ada beberapa jenis puzzle, antara lain: 1. Logika puzzle Logika puzzle adalah permainan puzzle yang mengutamakan logika dalam hal penyelesaiannya. Puzzle jenis ini pertama kali diproduksi oleh Charles Lutwidge, salah satu contoh logika puzzle yaitu sudoku, seperti yang tersaji pada Gambar 3 berikut.
Gambar 3. Puzzle Sudoku
6 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Permainan sudoku dimulai dengan beberapa sel yang sudah berisi sel sel kosong dengan angka antara 1 angka, kemudian pemain mengisi sel-sel sampai dengan 9, 9 sesuai dengan petunjuk berikut: a. Angka hanya dapat muncul satu kali dalam setiap baris. b. Angka hanya dapat muncul satu kali dalam setiap kolom. c. Angka hanya dapat muncul satu kali dalam setiap region. 2. Kombinasi puzzle Kombinasi binasi puzzle adalah puzzle yang dapat diselesaikan melalui beberapa kombinasi yang berbeda. Salah satu contoh kombinasi puzzle yaitu rubic cube, cube seperti yang tersaji pada Gambar 4 berikut.
Gambar 4. Rubic Cube Pada Gambar 4 merupakan rubic cube berukuran tiga kali tiga yang mempunyai mpunyai enam sisi dan mempunayi enam warna, pemain dikatakan berhasil menyelesaikan permainan rubic cube jika setiap sisi pada rubic cube hanya berisi satu jenis warna, seperti yang tersaji pada Gambar 5 berikut.
7 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Gambar 5. Hasil Penyelesaian Rubic Cube 3. Jigsaw puzzle Jigsaw puzzle adalah puzzle yang dapat diselesaikan dengan cara menyatukan kepingan-kepingan. Jigsaw puzzle pertama kali diproduksi pada tahun 1766 oleh John Spilsbury, nama jigsaw diambil dari alat untuk memotong menjadi kepingan-kepingan puzzle tersebut. Salah satu contoh jigsaw puzzle yaitu puzzle peta buatan John Spilsbury, seperti yang tersaji pada Gambar 6 berikut.
Gambar 6. Puzzle Peta Buatan John Spilsbury Untuk menyelesaikan puzzle peta buatan pada Gambar 6, pemain harus menyusun
kepingan-kepengian puzzle peta tersebut sehingga
menjadi sebuah bentuk peta secara utuh, seperti yang tersaji pada Gambar 7 berikut.
8 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Gambar 7. Bentuk Utuh Peta Buatan John Spilsbury C.
Bahasa Pemrograman Java Sun Microsystem Inc merupakan perusahan yang membuat bahasa pemrograman java ini, java dalam level beta dirilis secara resmi pada November 1995. Asal mulanya bahasa pemrograman java ditunjukkan untuk pemrograman applet di web browser, tapi bahasa pemrograman java berkembang begitu pesat, hingga sekarang aplikasi untuk smartphone bisa dibuat menggunakan bahasa pemrograman java. Pemrograman Berorientasi Objek adalah suatu cara baru dalam berfikir dan berlogika dalam menghadapi masalah-masalah dengan bantuan komputer, sehingga kita dapat membuat program yang mencerminkan fakta yang sesungguhnya yang memang kita jumpai dalam kehidupan sehari-hari melalui bahasa pemrograman java (Nugroho,2008).
D.
Bendera Negara Bendera Negara berperan sebagai pembawa identias negara di mata dunia, bendera negara didesain secara teliti dan hati-hati. Warna dan pola bendera dipikirkan secara mendalam agar mampu menggambarkan karakter dan ciri khas suatu negara. Berikut gambar bendera negara pada sembilan bagian benua :
9 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
1. Asia Tenggara Nama Negara dan Bendera Negara bagian Benua Asia Tenggara yang akan digunakan dalam permainan, tersaji pada Tabel 1. Tabel 1. Bendera Negara di Asia Tenggara Nama Negara
Bendera Negara
Indonesia
Brunei
Filipina
Kamboja
Laos
Malaysia
Myanmar
Singapura
Thailand
Timor Leste
10 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
2. Asia Barat Nama Negara Asia gara dan Bendera Negara bagian Benua A Barat yang akan digunakan dalam permainan, tersaji pada Tabel 2. Tabel 2. Bendera Negara di Asia Barat Nama Negara
Bendera Negara
Arab Saudi
Bahrain
Irak
Israel
Kuwait
Lebanon
Palestina
Turki
Oman
Siprus
3.
Amerika Utara Nama Negara dan Bendera Negara bagian Benua Amerika Utara yang akan digunakan dalam permainan, tersaji pada Tabel 3.
11 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Tabel 3. Bendera Negara di Amerika Utara Nama Negara
Bendera Negara
Amerika Serikat
Kanada
Bermuda
Greenland
4.
Amerika Selatan atau Amerika Latin Nama Negara gara dan Bendera Negara bagian Benua Amerika Latin yang akan digunakan dalam permainan, tersaji pada Tabel 4. Tabel 4. Bendera Negara di Amerika Latin Nama Negara
Bendera Negara
Suriname
Argentina
Brazil
Chili
Ekuador
Kolombia
Paraguay
12 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Peru
Uruguay
Guyana
Venezuela
5.
Eropa Barat Nama Negara dan Bendera Negara bagian B Benua Eropa Barat yang akan digunakan dalam permainan permainan, tersaji pada Tabel 5. Tabel 5. Bendera Negara di Eropa Barat Nama Negara
Bendera Negara
Austria
Belanda
Belgia
Jerman
Liechtenstein
Perancis
Swiss
13 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
6. Eropa Selatan Benua Eropa Nama Negara gara dan Bendera Negara bagian B Selatan yang akan digunakan dalam permainan permainan, tersaji pada Tabel 6. Tabel 6. Bendera Negara di Eropa Selatan Nama Negara
Bendera Negara
Yunani
Spanyol
Portugal
Kroasia
Italia
Bosnia
San Morino
Malta
Andorra
14 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
7. Afrika Utara Nama Negara gara dan Bendera Negara bagian Benua Afrika Utara yang akan digunakan dalam permainan permainan, tersaji pada Tabel 7. Tabel 7. Bendera Negara di Afrika Utara Nama Negara
Bendera Negara
Aljazair
Libya
Maroko
Mesir
Sahara Barat
Sudan
Tunisia
8.
Afrika Tengah gara dan Bendera Negara bagian Benua Afrika Nama Negara Tengah yang akan digunakan dalam permainan permainan, tersaji pada Tabel 8. Tabel 8. Bendera Negara di Afrika Tengah Nama Negara
Bendera Negara
Angola
Chad
15 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Gabon
Kamerun
Kongo
Republik Afrika Tengah
Republik Demokratik Kongo
9. Oseania ggap dengan luas benua terkecil terkecil. Oseania sering dianggap Nama Negara dan Bendera Negara bagian Benua enua Oseania yang akan digunakan dalam permainan,, tersaji pada Tabel 9. Tabel 9. Bendera Negara di Oseania Nama Negara
Bendera Negara
Australia
Selandia Baru
Papua Nugini
Pulau Norflok
Kepulauan Solomon
16 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
E.
Penelitian Terdahulu 1. Sirait (2013) telah mengembangkan aplikasi permainan labirin dengan menggunakan algoritma backtracking. Labirin adalah sebuah permainan mencari yang jalan keluar, dimana dalam perjalanan labirin ini banyak mendapat rintangan atau halangan untuk sampai pada tujuan. Algoritma backtracking pada aplikasi permainan ini digunakan untuk mencari solusi, agar bisa mencapai tujuan. 2. Handayani, dkk. (2012) telah mengembangkan aplikasi permainan othello berbasis android menggunakan algoritma Depth First Search. Pengembangan aplikasi othello difokuskan kepada bagaimana membuat agen cerdasnya. Agen adalah suatu yang dapat menerima kesan dari lingkungannya dan melakukan tindakan terhadap lingkungannya. Hasil dari pengembangan aplikasi ini menentukan pilihan langkah yang cerdas sehingga membuat para pemain terlibat mengasah dan mengatur strategi untuk mengalahkan agen cerdas tersebut. Agen cerdas dirangcang menggunakan algoritma Depth First Search. 3. Pribadi, dkk. (2010) telah mengembangkan sistem pencarian rute terpendek dengan menggunakan algoritma Depth First, Breath First dan Hill Climbing (Study Comparetive). Pada penelitian ini memfokuskan pada penerapan 3 algoritma pencarian dalam penentuan rute terpendek yang paling optimum untuk dicapai. Tujuan dari penelitian ini untuk menemukan rute yang efektif dan efisien dengan penerapan algoritma pencarian yang tepat sehingga rute yang disarankan akan benar-benar menjadi rute yang terbaik.
17 Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015