bab ii. kajian pustaka - repository.ump.ac.idrepository.ump.ac.id/637/3/abdul kadir hasan bab...
TRANSCRIPT
4
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.
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
5
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.
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
6
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
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
Permainan
angka, kemudian pemain mengisi sel
sampai dengan 9
a.
b.
c.
2. Kombinasi
Kombinasi
beberapa kombinasi yang berbeda.
yaitu rubic cube
Pada Gambar 4 merupakan
mempunyai enam sisi dan mempunayi enam warna, pemain dikatakan
berhasil menyelesaikan permainan
cube hanya berisi satu jenis warna, seperti yang tersaji pada Gambar 5
berikut.
Permainan sudoku dimulai dengan beberapa sel yang sudah berisi
kemudian pemain mengisi sel-sel kosong dengan angka antara 1
sampai dengan 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.
Kombinasi puzzle
binasi puzzle adalah puzzle yang dapat diselesaikan melalui
beberapa kombinasi yang berbeda. Salah satu contoh kombinasi
rubic cube, seperti yang tersaji pada Gambar 4 berikut.
Gambar 4. Rubic Cube
Pada Gambar 4 merupakan rubic cube berukuran tiga kali tiga yang
mpunyai enam sisi dan mempunayi enam warna, pemain dikatakan
berhasil menyelesaikan permainan rubic cube jika setiap sisi pada
hanya berisi satu jenis warna, seperti yang tersaji pada Gambar 5
7
dimulai dengan beberapa sel yang sudah berisi
sel kosong dengan angka antara 1
Angka hanya dapat muncul satu kali dalam setiap baris.
Angka hanya dapat muncul satu kali dalam setiap kolom.
Angka hanya dapat muncul satu kali dalam setiap region.
dapat diselesaikan melalui
Salah satu contoh kombinasi puzzle
seperti yang tersaji pada Gambar 4 berikut.
berukuran tiga kali tiga yang
mpunyai enam sisi dan mempunayi enam warna, pemain dikatakan
jika setiap sisi pada rubic
hanya berisi satu jenis warna, seperti yang tersaji pada Gambar 5
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
8
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.
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
9
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 :
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
bagian Benua Asia
permainan, tersaji pada
Asia Tenggara
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
2.
3.
Asia Barat
Nama Negara 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
Amerika Utara
Nama Negara dan Bendera Negara bagian Benua
Amerika Utara yang akan digunakan dalam permainan, tersaji
pada Tabel 3.
11
gara dan Bendera Negara bagian Benua Asia
permainan, tersaji pada
Asia Barat
Bendera Negara
Nama Negara dan Bendera Negara bagian Benua
permainan, tersaji
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
4.
Tabel 3. Bendera Negara di Amerika Utara
Nama Negara Bendera Negara
Amerika Serikat
Kanada
Bermuda
Greenland
Amerika Selatan atau Amerika Latin
Nama Negara 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
Amerika Utara
Bendera Negara
gara dan Bendera Negara bagian Benua
permainan, tersaji
Amerika Latin
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
5.
Peru
Uruguay
Guyana
Venezuela
Eropa Barat
Nama Negara dan Bendera Negara bagian B
Barat yang akan digunakan dalam permainan
Tabel 5.
Tabel 5. Bendera Negara di Eropa Barat
Nama Negara Bendera Negara
Austria
Belanda
Belgia
Jerman
Liechtenstein
Perancis
Swiss
13
Bendera Negara bagian Benua Eropa
permainan, tersaji pada
Eropa Barat
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
6.
Eropa Selatan
Nama Negara dan Bendera Negara bagian B
Selatan yang akan digunakan dalam permainan
Tabel 6.
Tabel 6. Bendera Negara di Eropa Selatan
Nama Negara Bendera Negara
Yunani
Spanyol
Portugal
Kroasia
Italia
Bosnia
San Morino
Malta
Andorra
14
gara dan Bendera Negara bagian Benua Eropa
permainan, tersaji pada
Eropa Selatan
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
7.
8.
Afrika Utara
Nama Negara dan Bendera Negara bagian Benua Afrika
Utara yang akan digunakan dalam permainan
Tabel 7.
Tabel 7. Bendera Negara di Afrika Utara
Nama Negara Bendera Negara
Aljazair
Libya
Maroko
Mesir
Sahara Barat
Sudan
Tunisia
Afrika Tengah
Nama Negara dan Bendera Negara bagian Benua Afrika
Tengah yang akan digunakan dalam permainan
Tabel 8.
Tabel 8. Bendera Negara di Afrika Tengah
Nama Negara Bendera Negara
Angola
Chad
15
gara dan Bendera Negara bagian Benua Afrika
permainan, tersaji pada
Afrika Utara
Bendera Negara
gara dan Bendera Negara bagian Benua Afrika
permainan, tersaji pada
Afrika Tengah
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
9.
Gabon
Kamerun
Kongo
Republik Afrika Tengah
Republik Demokratik Kongo
Oseania
Oseania sering dianggap dengan luas benua terkecil
Nama Negara dan Bendera Negara bagian Benua
akan digunakan dalam permainan, tersaji pada
Tabel 9. Bendera Negara di Oseania
Nama Negara Bendera Negara
Australia
Selandia Baru
Papua Nugini
Pulau Norflok
Kepulauan Solomon
16
ggap dengan luas benua terkecil.
enua Oseania yang
, tersaji pada Tabel 9.
Oseania
Bendera Negara
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015
17
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.
Algoritma Backtracking Untuk..., Abdul Kadir Hasani, Fakultas Teknik UMP, 2015