BAB II. KAJIAN PUSTAKA

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.


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


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.


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.


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 :


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


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.


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


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


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


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


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


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.


BAB II. KAJIAN PUSTAKA

Recommend Documents