LAPORAN TUGAS KELOMPOK

PENGGUNAAN ALGORITMA BACKTRACKING PADA MAZE

Disusun Oleh :

171110096 - Aldo

141110167 - Eric Sejahtera

171112259 - Manda Silvianti

 BAB I

1. Pendahuluan
Semenjak dahulu, permainan (game) merupakan hal yang sangat menarik bagi sebagian
besar masyarakat dunia. Dengan berkembangnya berbagai bentuk game, baik berupa game
yang masih sederhana maupun yang sudah menggunakan teknologi yang canggih, game
menjadi sangat populer di berbagai tempat. Salah satu bentuk game yang dewasa ini sudah
tidak asing adalah game yang dimainkan di komputer. Game merupakan aplikasi yang cukup
diminati karena bisa dimanfaatkan sebagai ajang refreshing dan olah otak. Bahkan tidak jarang
aplikasi pada computer menimbulkan kecanduan bagi user. Makalah ini dibuat untuk
memenuhi tugas mata kuliah Kecerdasan Buatan (artificial intelligence). Selain itu juga
bertujuan untuk menambah pengetahuan penulis dalam menganalisa penerapan algoritma
untuk menyelesaikan persoalan. Dalam hal ini persoalan yang penulis angkat adalah persoalan
dalam penyelesaian game Maze (Labirin). Game Maze (Labirin) merupakan game sederhana
yang bertujuan menentukan jalur yang tepat untuk mencapai tujuan yang telah ditetapkan.
Selama proses penentuan jalur tersebut, jika menemui jalan buntu maka akan dilakukan proses
backtrack sampai kembali menemukan jalur yang tepat untuk mencapai tujuan. Berbagai data
yang terdapat dalam makalah ini diperoleh dari berbagai sumber yang berkaitan. Selain itu
penulis juga mendapatkan referensi dari berbagai buku dan situs yang berkaitan dengan
penerapan algoritma backtracking.

2. Pembahasan
Maze (Labirin) merupakan game yang template-nya berbentuk persegi yang ukurannya
dapat diatur sesuai dengan keinginan user. Di dalamnya terdapat serangkaian jalur berupa
labirin yang bercabang. Namun, tidak setiap cabang mencapai tujuan yang diinginkan.
Pada makalah ini, penulis menggunakan algoritma backtracking. Algoritma backtracking
pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Dalam perkembangannya
beberapa ahli seperti RJ Walker, Golomb, dan Baumert menyajikan uraian umum tentang
backtracking dan penerapannya dalam berbagai persoalan dan aplikasi. Algoritma
backtracking (runut balik) merupakan salah satu metode pemecahan masalah yang termasuk
dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtrack bekerja secara
rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan
solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS),
maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar
secara preorder. Proses ini dicirikan dengan ekspansi simpul terdalam lebih dahulu sampai
tidak ditemukan lagi suksesor dari suatu simpul. Algoritma runut-balik secara garis besar
adalah:

Penggunaan algoritma backtrack ini terlihat pada proses penelusuran tiap jalur untuk
mencapai tujuan yang diinginkan. Sejak komputer memulai permainan, computer akan
menentukan jalur menelusuri sembarang jalur. Ketika komputer menemukan jalan buntu, maka
ia akan melakukan proses backtrack dengan cara kembali pada jalur sebelumnya sampai
menemukan jalur baru yang belum pernah dilewati. Ada dua solusi untuk masalah ini, yaitu
secara iteratif dan rekursif. Dalam hal ini, penulis menggunakan metode iteratif. Algoritma
runut-balik persoalan labirin adalah sebagai berikut.
 Gambar 1. Sebuah labirin
Algoritma yang tepat untuk menemukan jalan keluar dari dalam labirin adalah
algoritma runut-balik. Dengan algoritma ini, kita mencoba sebuah lintasan hingga menemui
jalan buntu, lalu jejaki, (retrace) langkah sebelumnya sampai kita menemukan lintasan yang
lain, lalu ulangi lagi lintasan tersebut. Pada akhirnya kita akan menemukan lintasan yang
mengarah ke pintu keluar, atau mencoba semua lintasan dan memutuskan tidak terdapat
solusinya. Untuk menggambarkan algoritma runut-balik secara rinci, bagi lintasan menjadi
sederetan langkah. Sebuah langkah terdiri dari pergerakan satu unit sel pada arah tertentu. Arah
yang mungkin: ke atas (up), ke bawah (down), ke kiri (left), ke kanan (right). Algoritma runut
baliknya secara garis besar adalah :

Gambar 2. Contoh runut balik pada sebuah labirin

 Gambar 3. Contoh runut balik pada gambar 1

Langkah-Langkah Penyelesaian Maze menggunakan Algoritma Backtracking

1. Dari titik start pilih titik terdekat yang bisa dikunjungi atau tidak terhalang oleh tembok
pada hal ini kita hanya bisa bergerak ke atas, belok kanan, belok kiri, dan turun
kebawah.
2. Apabila titik yang kita kunjungi merupakan titik yang belum pernah dikunjungi
sebelumnya, push titik tersebut kedalam stack solusi stack penanda untuk menandakan
bahwa posisi tersebut sudah pernah dilewati , kemudian pilih lagi titik didekatnya.
3. Apabila titik yang kita kunjungi merupakan jalan buntu atau bertemu dengan tembok,
pop sekali dari stack solusi untuk kembali ke posisi sebelumnya.
4. Ulangi langkah 2–3 sampai menemukan titik keluar dari labirin.
 BAB II

1. Pengertian Artifical Intelligence

Artifical Intelligence atau AI dalam bahasa Indonesia artinya Kecerdasan Buatan yaitu
kecerdasan yang ditunjukkan oleh suatu entitas ilmiah. Kecerdasan dibuat dan dimasukkan
ke dalam suatu mesin/ komputer supaya bisa melakukan pekerjaan seperti yang bisa
dikerjakan oleh manusia. Contohnya adalah kemampuan untuk menjawab diagnosa dan
pertanyaan pelanggan, perencanaan dan penjadwalan, pengendalian, serta pengenalan
tulisan tangan, suara dan wajah. Hal-hal seperti itu telah menjadi disiplin ilmu tersendiri,
yang memusatkan perhatian pada penyediaan solusi masalah di kehidupan yang nyata.
Terdapat macam-macam bidang yang menggunakan kecerdasan buatan diantaranya yaitu:
game komputer, sistem pakar, jaringan syaraf tiruan, logika fuzzy dan robotika.

2. Pengertian algoritma

Pengertian algoritma pada dasarnya adalah susunan logis dan sistematis yang
digunakan untuk memecahkan atau pun menyelesaikan suatu permasalahan tertentu. Jadi,
setiap susunan logis yang diurutkan berdasarkan sistematika tertentu yang dipakai untuk
menyelesaikan permasalahan dapat digolongkan sebagai sebuah algoritma. Susunan atau
pun langkah – langkah memasak mie intan misalnya, langkah – langkah sistematis yang
digunakan untuk memasak mie instan dapat digolongkan ke dalam logaritma, karena
menyelesaikan sebuah permasalahan yaitu permasalahan lapar yang dirasakan oleh
manusia.

Dalam dunia komputer sendiri, algoritma merupakan sistem kerja komputer yang
terdiri atas sekumpulan perintah terintegrasi pada brainware, software, dan hardware.
Tanpa salah satu dari tiga bagian sistem di atas, sebuah komputer tidak akan dapat
dioperasikan sama sekali.

Dalam dunia pemrograman, algoritma digunakan untuk membangun berbagai macam

software yang digunakan pada perangkat komputer. Penerapan sistem algoritma dalam
pembuatan software biasanya dilakukan melalui beberapa jenis bahasa pemrograman
seperti bahasa pemrograman C, bahasa pemrograman C#, dan bahasa pemrograman Visual
Basic.
 Tanpa algoritma yang tepat, susunan sintax atau pun baris – baris kode bahasa
pemrograman yang telah dibuat tidak akan ada artinya sama sekali. Hal ini dikarenakan
seluruh baris – baris kode yang dibuat dengan menggunakan tiga macam bahasa
pemrograman di atas diatur sepenuhnya oleh algoritma yang dibuat. Dari mulai aktivitas
pembukaan software aplikasi hingga ke berbagai macam aktivitas kerja yang digunakan
oleh penggunanya, semuanya diatur oleh algoritma pemrograman yang dibuat oleh
pengembang software tersebut.

3. Algoritma Bcaktracking

Algoritma Backtracking merupakan salah satu bentuk algoritma yang banyak

digunakan oleh para programmer ataupun pengguna komputer ahli untuk menyelesaikan
suatu permasalahan komputasional pada perangkat komputer yang mereka gunakan. Dalam
programming algoritma backtracking, rekursi adalah kunci dari programming
backtracking. Rekursi sendiri merupakan proses pengulangan suatu hal yang mencakup
kesamaan-diri. Penggunaan yang paling umum dari rekursi terdapat dalam kajian ilmu
matematika dan ilmu komputer.

Algoritma rekursi merupakan algoritma yang memanggil dirinya sendiri secara

berulang kali. Backtracking sebuah algoritma secara umum digunakan untuk menemukan
semua (atau beberapa) solusi terhadap sebuah permasalahan komputasional. Proses
backtracking dapat diaplikasikan hanya pada beberapa permasalahan yang mengikuti
konsep “solusi kandidat parsial” dan juga sebuah tes yang cukup relatif cepat untuk
menentukan kemungkinan apakah solusi tersebut valid atau tidak.

Backtracking tidaklah berguna untuk menyelesaikan permasalahaan seperti

menentukan sebuah nilai yang diberikan pada sebuah tabel yang tidak beraturan. Akan
tetapi ketika diaplikasikan, backtracking biasanya lebih cepat bila dibandingkan proses
pemecahan masalah brute force yang mana harus mencoba semua kandidat
kemungkinannya.

Sebagai salah satu algoritma yang banyak digunakan oleh para programmer.
Backtracking merupakan sebuah alat yang penting untuk dapat menyelesaikan
permasalahan pemenuhan terbatas, seperti teka – teki silang, aritmatika verbal, sudoku dan
berbagai macam puzzle sejenisnya. Algoritma ini juga dapat digunakan untuk
menyelesaikan permasalahan komputasional seperti memecahkan kata sandi atau password
pada suatu program, membuat sistem kerja atau mekanisme kerja dari suatu video game,
ataupun sistem dasar dari suatu simulasi komputer terhadap permasalahan di dunia nyata.

Referensi :

[Link]

[Link]
komputer/

[Link]

[Link]
2007/Makalah_2007/[Link]

[Link]

[Link]
[Link]
 BAB III

Flowchart