ALGORITMA RUNUT BALIK

MAKALAH

diajukan untuk memenuhi salah satu tugas Mata Kuliah Analisis dan Disain Algoritma

Disusun Oleh :

Cahya Widya 1100114Intan Asri Afifah 1103851Novi Setiawatri 1104950Risda Cahya Utami 1100198

PENDIDIKAN ILMU KOMPUTER

FAKULTAS PENDIDIKAN MATEMATIKA DAN IPA

UNIVERSITAS PENDIDIKAN INDONESIA

2013

KATA PENGANTAR

Rasa syukur yang dalam kami sampaikan ke hadirat Allah swt, karena berkat kemurahan-Nya makalah ini dapat kami selesaikan sesuai yang diharapkan. Dalam makalah ini kami membahas algoritma runut balik (backtracking) serta implementasinya.

Makalah ini dibuat dalam rangka memperdalam pemahaman terkait algoritma yang sangat diperlukan dalam membuat suatu program yang efektif dan efisien dalam memanfaatkan teknologi informasi terutama untuk para programmer.

Dalam proses pendalaman materi Backtracking ini, tentunya kami mendapatkan bimbingan, arahan, koreksi dan saran, untuk itu rasa terima kasih yang dalam-dalamnya kami sampaikan :

Jajang Kusnendar, MT. selaku dosen mata kuliah Analisis dan Disain Algoritma” Semua pihak yang terkait dalam penulisan makalah ini.

Demikian makalah ini kami buat semoga bermanfaat

Bandung, April 2013

Penyusun

DAFTAR ISI

KATA PENGANTAR......................................................................................................................i

DAFTAR ISI...................................................................................................................................ii

BAB I PENDAHULUAN...............................................................................................................1

A. Latar Belakang......................................................................................................................1

B. Rumusan Masalah.................................................................................................................1

C. Tujuan Penulisan Makalah...................................................................................................1

D. Manfaat Penulisan Makalah.................................................................................................1

BAB II PEMBAHASAN.................................................................................................................2

A. Algoritma Runut Balik.........................................................................................................2

B. Contoh-Contoh Algortima Runut Balik................................................................................2

C. Kekuatan dan Kelemahan Algoritma Runut Balik...............................................................5

D. Penggunaan Algoritma Runut Balik.....................................................................................6

BAB III PENUTUP.........................................................................................................................7

A. Kesimpulan...........................................................................................................................7

DAFTAR PUSTAKA......................................................................................................................8

BAB I PENDAHULUAN

A. Latar BelakangSebuah program adalah implementasi dari suatu algoritma.Arti algoritma itu sendiri adalah urutan langkah-langkah untuk memecahkan masalah, algoritma sendiri yaitu jantung ilmu komputer atau informatika.Bila rancangan pemecahan masalah sudah dibuat dengan skema yang benar maka rancangan tersebut siap dikodekan ke dalam bahasa pemrograman agar program dapat diesekusi dengan komputer. Selain berhasil tidaknya sebuah algoritma menjadi sebuah program, disini kita akan belajar mengenai analisis efektifitas algoritma tersebut. Dalam makalah ini penulis akan mengulas mengenai Algoritma Runut-Balik (Backtracking) adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus.

B. Rumusan Masalah1. Apa itu Algortima Runut Balik ?2. Bagaimana karakteristik Algortima Runut Balik ?3. Seperti apa contoh-contoh Algoritma Runut Balik ?4. Apa kekuatan dan kelemahan Algortima Runut Balik ?5. Pada saat bagaimana Algoritma Runut Balik ini digunakan ?

C. Tujuan Penulisan MakalahSejalan dengan rumusan masalah diatas, makalah ini disusun dengan tujuan untuk :

1. Memaparkan Pengertian Algoritma Runut Balik.2. Menjelaskan Karakter Algorimta Runut Balik.3. Menyajikan contoh-contoh Algoritma Runut Balik.4. Mengetahui Kekuatan dan Kelebihan Algoritma Runut Balik.5. Bagaimana Algoritma Runut Balik di harus digunakan.

D. Manfaat Penulisan MakalahMakalah ini disusun dengan harapan memberikan kegunaan baik secara teoritis maupun secara praktis. Secara teoritis makalah ini berguna sebagai bahan referensi untuk memahami Algoritma Runut Balik. Penulisan makalah ini di harapkan bermanfaat bagi :1. Penulis, sebagai wahana penambah pengetahuan dan ilmu mengenai analisis dan

disain algortima yang berfokus terhadap Algoritma Runut Balik.2. Pembaca, sebagai media informasi tentang analisis dan disain Algoritma Runut Balik

baik secara teoritis maupun secara praktis.

1

BAB IIPEMBAHASAN

A. Algoritma Runut BalikRunut Balik (Rinaldi Munir, 2004) adalah algoritma perkembangan dari Brute Force itu

sendiri.Pada dasarnya Algoritma Runut Balik adalah alur penyelesaian suatu permasalahan secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada.

Algoritma ini akan mencari solusi berdasarkan ruang solusi yang ada secara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang akan diproses.

Algoritma Runut Balik berbasis pada DFS (Depth First Search) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian kedalam. Simpul-simpul yang sudah dilahirkan (diperiksa) dinamakan simpul hidup (live node).Simpul hidup yang sedang diperluas dinamakan simpul-E atau Expand Node.Karakteristik Algoritma Runut Balik.

Berikut adalah beberapa karakteristik Algoritma Runut Balik :a. Algoritma ini tidak perlu memeriksa semua kemungkinan solusi yang ada.b. Di rancang untuk pencarian yang mengarah ke solusi saja yang selalu di pertimbangkanc. Waktu pencarian dapat di hemat.d. Saat ini Algoritma Runut Balik banyak di terapkan untuk program games seperti : Sudoku,

Logika Sirkuit Hamilton, Labirin, catur dll, dan masalah kecerdasan buatan lainnya.

B. Contoh-Contoh Algortima Runut BalikBerikut adalah contoh-contoh properti umum metode runut balik :a. Solusi persoalan

Solusi dinyatakan sebagai vektor dengan n-tuple:X = (x1, x2, …, xn), xi Si .

Mungkin saja S1 = S2 = … = Sn. Contoh: Si = {0, 1}, xi = 0 atau 1

b. Fungsi pembangkit nilai xkDinyatakan sebagai : T(k) T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi.

c. Fungsi pembatas (pada beberapa persoalan fungsi ini dinamakan fungsi kriteria)Dinyatakan sebagai B(x1, x2, …, xk) B bernilai true jika (x1, x2, …, xk) mengarah ke solusi. Jika true, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi jika false, maka (x1, x2, …, xk) dibuang dan tidak dipertimbangkan lagi dalam pencarian solusi

2

Prinsip pencarian solusi dengan metode runut-balik : Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan

pembentukan yang dipakai adalah mengikuti aturan pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E (Expand-node).

Tiap kali simpul-E diperluas, lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.

Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut-balik ke simpul hidup terdekat (simpul orangtua). Selanjutnya simpul ini menjadi simpul-E yang baru.

Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada lagi simpul hidup untuk runut-balik.

Tinjau persoalan Knapsack 0/1 dengan instansiasi:n = 3(w1, w2, w3) = (35, 32, 25)(p1, p2, p3) = (40, 25, 50)M = 30

Solusi dinyatakan sebagai X = (x1, x2, x3), xi {0, 1}. Fungsi pembatas

Pohon dinamis yang dibentuk selama pencarian untuk persoalan Knapsack 0/1 dengan n = 3, M = 30, w = (35, 32, 25) dan p = (40, 25, 50)

3

∑i=1

k

wi x i≤M

1

2 9

10 13

14 15

x1 =1 x1 =0

x2 =1 x2 =0

x3 =1 x3 =0

B

B

Penomoran ulang simpul-simpul sesuai urutan pembangkitannya

Setiap simpul dalam pohon ruang status berasosiasi dengan sebuah pemanggilan rekursif.

Jika jumlah simpul dalam pohon ruang status adalah 2n atau n!, maka untuk kasus terburuk, algoritma runut-balik membutuhkan waktu dalam O(p(n)2n) atau O(q(n)n!), dengan p(n) dan q(n) adalah polinom derajat n yang menyatakan waktu komputasi setiap simpul.

4

Contoh lainnya adalah : Sirkuit Hamilton dalam sebuah Graf di bawah ini.

Asumsikan jika terdapat Sirkuit Hamilton, dimulai dari simpul a ke a sebagai root dari lintasan tersebut dan state space dalam tree, berdasarkan pengurutan abjad.

Ini adalah state-space tree nya.

C. Kekuatan dan Kelemahan Algoritma Runut BalikAnalisa penggunaan teknik Backtracking pada lintasan Hamilton :

1. Keunggulan menggunakan algoritma backtracking yakni mudah merunut balik apa yang kita kerjakan, apabila kita salah melangkah maka kita akan kembali pada posisi yang mempunyai solusi permasalahan.

2. Kelemahan menggunakan algoritma backtracking yakni kita belum dapat mengetahui apakah langkah yang kita ambil merupakan langkah yang terbaik, sehingga memungkinkan terjadi terlalu banyak backtracking yang harus dilakukan.

5

D. Penggunaan Algoritma Runut BalikAlgoritma runut balik (backtracking) merupakan algoritma yang digunakan untuk mencari solusi persoalan secara lebih mangkus daripada menggunakan algoritma brute force.Algoritma ini akan mencari solusi berdasarkan ruang solusi yang ada secara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang akan diproses. (Rinaldi Munir, Diktat Strategi Algoritmik, Teknik Informatika ITB. 2005).

Algoritma backtracking mempunyai prinsip dasar yang sama seperti brute-force yaitu mencoba segala kemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebut secara DFS (depth field search) sampai ditemukan solusi yang layak.

6

BAB IIIPENUTUP

A. KesimpulanAlgoritma Runut Balik yang merupakan perkembangan dari Brute Force .Algoritma

Runut Balik adalah algoritma yang digunakan untuk mencari semua solusi yang ada. Algoritma Runut Balik berbasis pada DFS (Depth First Search) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian kedalam.

7

DAFTAR PUSTAKAMunir, Rinaldi. Algoritma Runut-balik (Backtracking).[Online]. Tersedia :

http://www.ittelkom.ac.id/staf/zka/Materi%20Desain%20Analisis%20Algoritma/M14Algoritma%20Runut-balik.pdf. [25 April 2013]

8