algoritma runut-balik

7/26/2019 Algoritma Runut-balik

http://slidepdf.com/reader/full/algoritma-runut-balik 1/31

Algoritma Runut-balik

(Backtracking)

Bagian 1



Pendahuluan

• Runut-balik (backtracking) adalahalgoritma yang berbasis pada DFSuntuk mencari solusi persoalan

secara lebih mangkus.

• Runut-balik yang merupakanperbaikan dari algoritma brute-force

secara sistematis mencari solusipersoalan di antara semuakemungkinan solusi yang ada.



• Dengan metode runut-balik kita tidak perlumemeriksa semua kemungkinan solusi yang

ada. !anya pencarian yang mengarah kesolusi sa"a yang selalu dipertimbangkan.#kibatnya $aktu pencarian dapat dihemat.

• Saat ini algoritma runut-balik banyakditerapkan untuk program games (sepertipermainan tic-tac-toe menemukan "alan

keluar dalam sebuah labirin catur dll) danmasalah-masalah pada bidang kecerdasanbuatan (articial intelligence).



Properti Umum MetodeRunut-balik

1. Solusi persoalan.

• Solusi dinyatakan sebagai %ektor

dengan n-tuple& X ' ( x 1 x ( x n) x i ∈ Si .

• *ungkin sa"a S1 ' S( ' ' Sn.• +ontoh& Si ' , 1 x i ' atau 1



. Fungsi pembangkit nilai x k

Dinyatakan sebagai&T (k )

T (k ) membangkitkan nilai untuk x k

yang merupakan komponen %ektorsolusi.



/. Fungsi pembatas (pada beberapa persoalan0ungsi ini dinamakan 0ungsi kriteria)

• Dinyatakan sebagai

B( x 1 x x k )

• B bernilai true "ika ( x 1 x x k ) mengarah

ke solusi. ika true maka pembangkitannilai untuk x k 21 dilan"utkan tetapi "ika false

maka ( x 1 x x k ) dibuang dan tidak

dipertimbangkan lagi dalam pencariansolusi.



Pengorganisasian Solusi

• Semua kemungkinan solusi daripersoalan disebut ruang solusi (solution space).

• ika x i ∈ Si, maka S1 × S × × Sn

disebut ruang solusi.

• umlah anggota di dalam ruang solusiadalah 3 S13 ⋅ 3 S3 ⋅ ⋅ 3 Sn 3.



• 4in"au Knapsack 51 untuk n ' /.

• Solusi persoalan dinyatakan sebagai%ektor ( x 1 x x /) dengan x i ∈ ,1.

Ruang solusinya adalah

,1 × ,1 × ,1 ' ,( )

( 1 ) ( 1) (1 ) (1 1 )(1 1)

( 1 1) (1 1 1).



• Pada Knapsack 51 dengan n ' /terdapat n ' / ' 6 kemungkinan

solusi yaitu&

( ) ( 1 ) ( 1)

(1 ) (1 1 ) (1 1)( 1 1) dan (1 1 1).

• Penyelesaian secara exhaustive search adalah dengan mengu"i setiapkemungkinan solusi.



• Ruang solusi diorganisasikan ke dalamstruktur pohon.

• 4iap simpul pohon menyatakan status(state) persoalan sedangkan sisi (cabang)dilabeli dengan nilai-nilai x i.

• 7intasan dari akar ke daun menyatakansolusi yang mungkin.

• Seluruh lintasan dari akar ke daunmembentuk ruang solusi. Pengorganisasianpohon ruang solusi diacu sebagai pohonruang status (state space tree).



4in"au persoalan Knapsack 15 untuk n ' /.

Ruang solusinya&



Prinsip Pencarian Solusi denganMetode Runut-balik

• Solusi dicari dengan membentuklintasan dari akar ke daun. #turanpembentukan yang dipakai adalah

mengikuti aturan pencarianmendalam (DFS). Simpul-simpulyang sudah dilahirkan dinamakan

simpul hidup (live node). Simpulhidup yang sedang diperluasdinamakan simpul-E (Expand-node).



• 4iap kali simpul-8 diperluas lintasan

yang dibangun olehnya bertambahpan"ang. ika lintasan yang sedangdibentuk tidak mengarah ke solusimaka simpul-8 tersebut 9dibunuh:

sehingga men"adi simpul mati (dead node). Fungsi yang digunakanuntuk membunuh simpul-8 adalahdengan menerapkan fungsi

pembatas (bounding function).Simpul yang sudah mati tidak akanpernah diperluas lagi.



• ika pembentukan lintasan berakhir

dengan simpul mati maka prosespencarian diteruskan denganmembangkitkan simpul anak yanglainnya. Bila tidak ada lagi simpul

anak yang dapat dibangkitkanmaka pencarian solusi dilan"utkandengan melakukan runut-balik ke

simpul hidup terdekat (simpulorangtua). Selan"utnya simpul inimen"adi simpul-8 yang baru.



• Pencarian dihentikan bila kita telahmenemukan solusi atau tidak adalagi simpul hidup untuk runut-balik.



• 4in"au persoalan Knapsack 51 denganinstansiasi&

n ' /

(1 ( /) ' (/; / ;)

( p1 p( p/) ' (< ; ;)

! ' /

• Solusi dinyatakan sebagai X ' ( x 1 x ( x /)

x i ∈ , 1.

• Fungsi pembatas&



Pohon dinamis yang dibentuk selama pencarianuntuk persoalan Knapsack 51 dengan n ' /! ' /, ' (/; / ;) dan p ' (< ; ;)

1

2 9

1 01 3

1 4 1 5

x 1 = 1 x

1 = 0

x 2 = 1 x

2 = 0

x 3 = 1 x

3 = 0

B

B



Penomoran ulang simpul-simpul sesuaiurutan pembangkitannya

Solusi optimumnya adalah X = (0, 0, 1) dan F = 50.



Skema Umum Algoritma Runut-Balik

(ersi rekursif)



Skema Umum Algoritma Runut-Balik

(ersi iteratif)



• Setiap simpul dalam pohon ruang statusberasosiasi dengan sebuah pemanggilan

rekursi0.

• ika "umlah simpul dalam pohon ruang

status adalah n atau n= maka untukkasus terburuk algoritma runut-balikmembutuhkan $aktu dalam "( p(n)n)atau "(#(n)n$) dengan p(n) dan #(n)

adalah polinom dera"at n yangmenyatakan $aktu komputasi setiapsimpul.



Mencari !alan keluar di dalamlabirin (Maze Problem)"



Penyelesaian dengan bactracking&

• Bagi lintasan men"adi sederetanlangkah. Sebuah langkah terdiri daripergerakan satu unit sel pada arah

tertentu.

• #rah yang mungkin& ke atas (up) keba$ah (don) ke kiri (left ) ke kanan(right ).



>aris besar algoritma runut-baliknya&



• Bagaimana mengetahui langkah yang

mana yang perlu di"e"aki kembali?

• #da dua solusi untuk masalah ini&

pertama simpan semua langkah yangpernah dilakukan atau kedua gunakanrekursi (yang secara implisitmenyimpan semua langkah).

• Rekursi adalah solusi yang lebihmudah.



Contoh runut-ali! pada s"uah lairin. #unut-ali! dip"rlihat!an d"n$an

$aris putus-putus.



+ontoh lain&



@elebihan Backtracking &

- Dibandingkan dengan pencarian

lainnya ini lebih cepat "ika ditemukansolusi karena tidak mengu"inyasemua artinya hanya memilih yangbenar tanpa mengulangnya.



48RA*# @#SA!

algoritma runut-balik

Documents