Abstrak
Setiap manusia ingin
menyelesaikan permasalahan yang dihadapi dengan secepat-cepatnya dan
mendapatkan keuntungan sebanyak-banyaknya dengan mengefisienkan sumber daya
yang dimiliki terhadap batasan-batasan yang ditemui pada suatu masalah.
Khususnya permasalahan yang selalu terdapat pada bidang informatika adalah
pencarian metode atau algoritma yang lebih mangkus untuk mencapai solusi. Oleh
karena itu dibutuhkan langkah-langkah tertentu yang dapat dijadikan acuan untuk
membantu pemecahan masalah tersebut. Salah satunya adalah pemecahan algoritma
runut balik (backtracking) yang sering digunakan untuk membuat program
khususnya permainan dan kecerdasan buatan. Algoritma-algoritma selain runut
balik pun sebenarnya cukup mangkus untuk mencari solusi di antara kemungkinan
solusi yang ada. Akan tetapi, waktu komputasi yang dibutuhkan algoritma lain
biasanya akan meningkat dengan drastis seiring dengan pertambahan ukuran
persoalan yang membesar. Karena itulah dibutuhkan metode untuk lebih
memangkuskan algoritma tersebut. Salah satu metode yang dapat digunakan adalah
menggunakan metode runut balik. Runut balik itu sendiri adalah algoritma yang
berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus. Dengan
metode runut balik, kita tidak perlu memeriksa semua kemungkinan solusi yang
ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan.
Akibatnya, waktu pencarian dapat dihemat.
KATA PENGANTAR
Rasa syukur yang dalam kami sampaikan ke
hadirat Allah swt,
karena berkat kemurahanNya makalah ini dapat kami selesaikan sesuai yang
diharapkan.Dalam makalah ini kami membahas “Backtracking,
Algoritma serta Implementasinya”, suatu permasalahan para programmer
sekaligus solusi dalam pembuatan algoritma yang ingin dibuatnya di antara
berbagai algoritma-algoritma yang ada.
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 dan sekaligus melakukan apa yang menjadi
tugas mahasiswa yang mengikuti mata kuliah “Algoritma
dan Pemrograman II”
Dalam proses pendalaman materi Backtracking ini,
tentunya kami mendapatkan bimbingan, arahan, koreksi dan saran, untuk itu
rasa terima kasih yang dalam-dalamnya
kami sampaikan :
- Dr. Dedi
Rohendi, MT. selaku dosen mata kuliah “Algoritma
dan Pemrograman II”
- Rekan-rekan mahasiwa yang telah
banyak memberikan masukan
untuk makalah ini.
Demikian
makalah ini kami buat semoga bermanfaat,
Bandung, Desember
2010
Penyusun
BAB
I Pendahuluan
1.1
Latar
Belakang Masalah
Di
dalam kehidupannya, manusia selalu menemui masalah atau persoalan. Hal ini
mungkin didasarkan dari sifat dasar manusia itu sendiri yang selalu ingin tahu
segala sesuatu. Deskripsi dari masalah menurut [NEA96] adalah pertanyaan atau
tugas yang kita cari jawabannya.
Dalam
menghadapi permasalahan, untuk menyelesaikannya manusia memerlukan
langkah-langkah yang benar sehingga permasalah tersebut dapat terselesaikan.
Urutan langkah-langkah untuk memecahkan suatu masalah tersebutlah yang
dinamakan dengan algoritma. Definisi lain dari algoritma adalah deretan
langkah-langkah komputasi yang mentranformasikan data masukan menjadi keluaran
[COR92].
Dalam
menentukan langkah-langkah tersebut diperlukan suatu strategi agar langkah-langkah
yang dipakai tersebut dapat menyelesaikan permasalahan secara mangkus
(efisien). Strategi menurut kamus besar bahasa indonesia adalah rencana yang
cermat mengenai kegiatan untuk mencapai sasaran khusus. Rencana itu sendiri
dapat berisi suatu metode atau teknik yang digunakan untuk mencapai sasaran
khusus tersebut.
Dengan
pengertian algoritma dan strategi tersebut, kita dapat mendefinisikan strategi
algoritmik sebagai kumpulan metode atau teknik untuk memecahkan masalah guna
mencapai tujuan yang ditentukan, yang dalam hal ini deskripsi metode atau
teknik tersebut dinyatakan dalam suatu urutan langkah-langkah penyelesaian.
Secara
umum, strategi pemecahan masalah dapat dikelompokan menjadi:
1. Strategi
solusi langsung, metode yang termasuk ke dalam strategi ini adalah: Algoritma Brute Force dan Algoritma Greedy
2. Strategi
berbasis pencarian pada ruang status, metode yang termasuk ke dalam strategi
ini adalah: Algoritma Backtracking dan
Algoritma Brach and Bound
3. Strategi
solusi atas-bawah, metode yang termasuk ke dalam strategi ini adalah Algoritma Divide and Conquer.
4. Strategi
solusi bawah-atas, metode yang termasuk ke dalam strategi ini adalah Dynamic Programming.
Strategi yang akan dibahas pada makalah
ini adalah strategi berbasis pencarian pada ruang status. Secara spesifik,
metode yang dibahas adalah Algoritma runut balik (backtracking). Permasalahan ini akan dibahas lebih lanjut dalam bab
selanjutnya.
1.2
Perumusan
Masalah
Dari latar belakang
yang telah diuraikan, maka timbul beberapa pertanyaan yang merupakan rumusan
masalah, yakni sebagai berikut:
1. Apakah
yang dimaksud dengan algoritma runut balik (backtracking)
?
2. Apa
keunggulan serta kelemahan algoritma runut balik (backtracking) dibandingkan dengan algoritma-algoritma yang ada?
3. Bagaimana
prosedur algoritma runut balik (backtracking)
?
4. Bagaimana
Implementasi algoritma runut balik (backtracking)
dalam pemrograman ?
1.3 Maksud dan Tujuan
1.3.1
Maksud Pembahasan
Berdasarkan
uraian latar belakang dan rumusan masalah di atas, maka maksud dari pembahasan
ini adalah untuk mengetahui dengan jelas hal-hal yang berkaitan dengan sebuah
algoritma yang dinamakan dengan algoritma runut balik (backtracking).
1.3.2 Tujuan Pembahasan
Tujuan
pembahasan ini dapat dirumuskan untuk:
1. Menganalisis
definisi yang dimiliki oleh algoritma runut balik (backtracking).
2. Menganalisis
prosedur algoritma dalam algoritma runut balik (backtracking).
3. Menganalisis
implementasi algoritma runut balik (backtracking).
BAB
II Isi
2.1
Algoritma Runut Balik (backtracking)
Algoritma runut balik pertama kali diperkenalkan oleh D.H
Lehmer pada tahun 1950. Algoritma ini cukup mangkus untuk digunakan dalam
beberapa penyelesaian masalah dan juga untuk memberikan kecerdasan buatan dalam
game. Beberapa game populer semisal Sudoku, Labirin, Catur juga bisa
diimplementasikan dengan menggunakan algoritma runut balik.
Algoritma 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 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 mendalam. Simpul-simpul yang sudah
dilahirkan (diperiksa) dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E
atau Expand Node.
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.
2.2
Properti Umum Metode runut balik (Backtracking)
Untuk
menerapkan metode runut-balik, properti berikut didefinisikan:
1. Solusi
persoalan.
Solusi dinyatakan sebagai vektor
n-tuple:
X=(x1,
x2, ..., xn), xi anggota himpunan berhingga Si .
Mungkin
saja S1 = S2 = ... = Sn.
Contoh:
Si = {0,1}
Si
= 0 atau 1
2.
Fungsi pembangkit nilai
xk
Dinyatakan sebagai:
T(k)
T(k)
membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi
3. Fungsi
Pembatas (fungsi kriteria)
Dinyatakan sebagai:
B(x1,
x2, ..., xk)
Fungsi pembatas menentukan apakah
(x1, x2, ..., xk) mengarah ke solusi. Jika ya, maka pembangkitan nilai untuk
xk+1 dilanjutkan, tetapi jika tidak, maka (x1, x2, ..., xk) dibuang dan tidak
dipertimbangkan lagi dalam pencarian solusi.
2.3 Pengorganisasian Solusi
Semua
kemungkinan solusi dari persoalan disebut ruang
solusi (solution space).
Jika xi
Î Si, maka S1 ´
S2 ´
… ´
Sn disebut ruang solusi. Jumlah anggota di dalam
ruang solusi adalah | S1| ×
| S2| ×
… ×
| Sn |. Tinjau persoalan Knapsack 0/1 untuk n = 3. Solusi persoalan dinyatakan sebagai vektor (x1, x2, x3)
dengan xi Î
{0,1}. Ruang solusinya adalah
{0,1}
´
{0,1} ´ {0,1} = {(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0),
(1, 0, 1),
(0, 1, 1), (1, 1, 1)}.
Pada
persoalan Knapsack 0/1 dengan n = 3 terdapat 2n = 23 = 8 kemungkinan solusi, yaitu:
(0,
0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1), dan
(1, 1, 1).
Penyelesaian secara exhaustive search adalah dengan menguji setiap kemungkinan
solusi. Ruang solusi diorganisasikan ke
dalam struktur pohon. Tiap simpul pohon menyatakan status (state) persoalan, sedangkan sisi (cabang) dilabeli dengan
nilai-nilai xi. Lintasan
dari akar ke daun menyatakan solusi yang mungkin. Seluruh lintasan dari akar ke
daun membentuk ruang solusi. Pengorganisasian pohon ruang solusi diacu sebagai
pohon ruang status (state space tree).
Tinjau kembali persoalan Knapsack 1/0
untuk n = 3. Ruang solusinya:
Gambar Ruang solusi untuk persoalan Knapsack 0/1 dengan n = 3
2.4 Prinsip Pencarian Solusi dengan Metode Runut
Balik
Langkah-langkah
pencarian solusi dengan metode runut balik adalah sebagai berikut:
1. Solusi
dicari dengan membentuk lintasan dari akar ke daun. Aturan yang dipakai adalah
mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan
dinamakan simpul hidupm dan simpul hidup yang sedang diperluas dinamakan
simpul-E. Simpul dinomori dari atas ke bawah sesuai dengan kelahirannya.
2. Jika
lintasan yang diperluas yang sedang dibentuk tidak mengarah ke solusi, maka
simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Simpul yang sudah mati ini tidak akan diperluas lagi.
3. Jika
pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian
diteruskan dengan membangkitkan simpul anak lainnya. Bila tidak ada lagi simpul
anak yang dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan
runut-balik (backtracking) ke simpul
hidup terdekat. Selanjutnya simpul ini menjadi simpul-E yang terbaru.
4. Pencarian
dihentikan bila telah ditemukan solusi atau tidak ada lagi simpul hidup untuk
runut balik (backtracking).
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:
Gambar (a) Pohon
dinamis yang dibentuk selama pencarian untuk persoalan Knapsack 0/1 dengan n =
3,
w = (35, 32, 25) dan p = (40, 25, 50)
(b)
Penomoran ulang simpul-simpul sesuai urutan pembangkitannya
Solusi
optimumnya adalah X = (0, 0, 1) dan F =
50.
2.5 Skema Umum Algoritma Backtracking
(a)
Versi rekursif
|
procedure RunutBalikR(input k:integer)
{Mencari semua solusi persoalan dengan metode runut-balik;
skema rekursif
Masukan: k, yaitu
indeks komponen vektor solusi, x[k]
Keluaran: solusi x
= (x[1], x[2], …, x[n])
}
Algoritma:
for tiap x[k] yang belum dicoba sedemikian sehingga
( x[k]¬T(k))
and B(x[1], x[2], ... ,x[k])= true do
if (x[1], x[2], ... ,x[k])
adalah lintasan dari akar ke daun
then
CetakSolusi(x)
endif
RunutBalikR(k+1) {
tentukan nilai untuk x[k+1]}
endfor
|
Pemanggilan
prosedur pertama kali: RunutBalikR(1)
(b) Versi iteratif
|
procedure RunutBalikI(input n:integer)
{Mencari semua solusi persoalan dengan metode runut-balik;
skema iteratif.
Masukan: n, yaitu
panjang vektor solusi
Keluaran: solusi x
= (x[1], x[2], …, x[n])
}
Delarasi:
k : integer
Algoritma:
k¬1
while k > 0 do
if (x[k] belum dicoba sedemikian
sehingga x[k]¬T(k)) and
(B(x[1], x[2], ... ,x[k])= true)
then
if (x[1],x[2],...,x[k])
adalah lintasan dari akar ke daun
then
CetakSolusi(x)
endif
k¬k+1 {indeks anggota
tupple berikutnya}
else {x[1], x[2], …, x[k]
tidak mengarah ke simpul solusi }
k¬k-1
{runut-balik ke anggota tupple sebelumnya}
endif
endwhile
{ k = 0 }
|
Pemanggilan
prosedur pertama kali: RunutBalikI(n)
·
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.
Pembuatan
algoritma dengan menggunakan prinsip backtracking
banyak digunakan dalam menyelesaikan berbagai masalah. Adapun
masalah-masalah yang dapat diselesaikan dengan teknik tersebut, antara lain:
1.
Banyaknya
Himpunan Bagian Suatu Himpunan (Sum Of
Subsets)
Masalah utama dari Sum Of Subsets adalah jika terdapat n bilangan
real dan ingin dihitung semua kombinasi yang mungkin dari himpunan bilangan
tersebut. Kombinasi yang diinginkan yaitu kombinasi yang jumlah seluruh
elemennya sama dengan M (tertentu).
Sebelum kita selesaikan masalah tersebut dengan menggunakan teknik
backtracking, perhatikan terlebih dahulu penyajian permasalahan dan
penyelesaiannya dalam bentuk pohon.
Misalkan banyaknya bilangan
real tersebut adalah 4 (n=4) akan ditentukan lebih dahulu kombinasi-kombinasi
dari elemen-elemen bilangan tersebut. hal itu dikenal dengan istilah himpunan
bagian (subsets). Dari pohon berikut digambarkan bahwa setiap ruas (edge) diberi label sedemikian sehingga
ruas dari simpul (vertex/node)
tingkat I ke simpul tingkat I + 1 akan mewakili nilai dari xi. Pada
setiap simpul, ruang penyelesaian dibagi (dipartisi) menjadi ruang-ruang
penyelesaian bagian. Ruang penyelesaian didefinisikan oleh semua jalur dari
akar simpul (node root) ke simpul
lainnya di dalam pohon tersenut. Kemungkinan jalur-jalur tersebut adalah ()
atau kosong, ini berarti tidak ada jalur dari akar simpul ke dirinya sendiri
(1), (1,2), (1,2,3), (1,2,3,4), (1,2,4), (1,3,4), (2), (2,3), (2,3,4) dan
seterusnya.
Jalur-jalur tersebut
mempunyai ukuran tuple yang
berbeda-beda, yang merupakan ruang penyelesaiannya. Secara struktur data,
pencari ruang solusi di atas menggunakan queue, yang disebut juga dengan breadth first search (BFS)
Gambar Pohon dari ruang penyelesaian dalam breadth first search (BFS)
Adapun bentuk penyajian lain
dari pencarian ruang penyelesaian permasalahan tersebut di atas, adalah dengan
menggunakan ukuran tuple yang sama
(tetap). Bahwa untuk setiap ruas dari simpul-simpul tingkat I ke simpul-simpul
tingkat i+1 diberi nama dengan nilai Xi=0 atau Xi=1.
Semua jalur dari akar ke daun didefenisikan sebagai ruang penyelesaian. Pohon
bagian (sub tree) di sebelah kiri
dari akar sama dengan semua himpunan bagaian yang berisi W1.
sementara itu untuk pohon bagaian disebelah kanannya adalah merupakan semua
himpunan bagaian yang tidak mengandung W1 dan seterusnya. Pendarian
simpul-simpul dari pohon tersebut sehingga diperoleh ruang penyelesaiannya
menggunakan metode stack. Hal I
tersebut dinamakan juga dengan istilah Depth
First Search (DFS).
Gambar Pohon Dari Penyelesaian Ruang DFS
Kedua bentuk penyajian pohon dari persoalan sum of subsets, merupakan tahapan pertama dalam proses mendapatkan
solusi sesungguhnya (solusi optimal). Untuk mendapatkan solusi yang optimal
dari ruang penyelesaian digunakan suatu algoritma lain. Algoritma tersebut
menggunakan teknik backtracking, yang
selanjutnya disebut dengan algoritma SUMOFSUB.
PROCEDURE SUMOFSUB(s,k,r)
GLOBAL INTEGER M,n
GLOBAL REAL W(1:n)
GLOBAL BOOLEAN X(1:n)
REAL r,s; INTEGER k,j
X(k) = 1
IF s + W(k) = M THEN PRINT (X(j), j ← 1 TO k)
ELSE
IF s + W(k) + W(k+1) ≤ M THEN
CALL SUMOFSUB(s+W(k), k+1, r-W(k))
ENDIF
ENDIF
IF s + r - W(k) ≥ M AND s + W(k) ≤ M THEN
X(k) 0
CALL SUMOFSUB(s, k+1, r-W(k))
ENDIF
END SUMOFSUB
2.
Pewarnaan
Graph (Graph Coloring)
Misalkan G adalah sebuah graph dan m adalah bilangan yang
positif. Kita ingin menemukan simpul-simpul dari G yang dapat diwarnai
sedemikian rupa sehingga dua simpul yang berdampingan tidak mempunyai warna
yang sama, sehingga hanya m warna yang dipakai. Masalah keputusan pewarnaan m
bertujuan untuk menanyakan bilangan yang terkesil dimana graph G dapat diwarnai. Bilangan ini disebut sebagai bilangan khromatik dari sebuah graph.
Sebuah graph dikatakan planar jika tidak ada dua buah titik yang saling
berpotongan. Sebuah kasus yang terkenal dari “m colorability decision problem” yaitu masalah 4 warna dari suatu graph planar. Masalah ini disertai
pertanyaan sebagai berikut: berikan beberapa map yang dapat menimbulkan
daerah-daerah yang diwarnai sedemikian rupa sehingga daerah-daerah yang
berdampingan tidak memiliki warna yang sama, tapi hanya empat buah warna yang
dipakai oleh sebuah masalah dimana graph-
graph masalah itu berubah menjadi sangat berguna, karena sebuah map dapat
dengan mudah dirubah bentuknya menjadi sebuah graph.
Masing-masing daerah dari map itu
menjadi sebuah titik dan jika dua buah daerah berdampingan maka kedua buah
titiknya berhubungan, kemudian kedua titik itu dihubungkan dengan sebuah edge.
Dalam bagaian ini kita
mempertimbangkan tidak hanya graph- graph
yang dibuat untuk map-map tetapi semua graph
diperhitungkan juga.
Kita tarik dalam mendeterminankan
semua cara-cara yang berbeda yang mana graph tampil mungkin dengan memakai yang
terbanyak m warna.
Gambar Sebuah map dan representasi graph planarnya
Jika kita unpamakan sebuah graph dengan matrik adjacency GRAPH (1:n, 1:n),
dimana graph (I,j) = benar jika (I,j)
adalah sebuah garis dari G dan graph
(I,j) yang lainnya adalah salah. Kita labih senang menggunakan nilai-nilai dari
Boolean sejak algoritma hanya akan menarik dengan ada atau tidaknya sebuah
titik. Warna-warna tersebut diumpakan dengan bilangan 1,2,2,…,m dan pemecahan
akan diberikan dengan n-tuple. (x(1),… x(n0 dimana x(i) adalah warna dari node(i).
Dengan mempergunakan rumus backtracking seperti yang telah diberikan dalam algoritam maka
hasil dari program tersebut adalah MCOLORING. Disebutkan bahwa state space tree yang sering
dipergunakan adalah sebuah tree
dengan tingkat m dan panjang = n+1. Setiap node
pada derajat I mempunyai m cabang yang berhubungan ke m yang mungkin untuk x
(i), dimana 1 ≤ I ≤ n.
Node-node pada n+1 adalah daun-daunnya node.
|
|
Procedure MCOLORING (k)
Global integer m,n, X(1:n) boolean
GRAPH (1:n,1:n)
Integer k
Loop
Call NEXTVALUE (k)
if X(k) = 0 then Exit
Andif
if k = n
then
print (X)
else
call MCOLORING (k+1)
endif
repeat
end MCOLORING
|
|
Prosedur MCOLORING dimulai pertama-tama dengan
pembagian graph untuk matrik adjacency-nya, membuat harga x =
0, dan kemudian memanggil statement call
MCOLORING.
Prosedur NEXTVALUE menghasilkan kemungkinan
warna-warna untuk X9k) setelah X(1) samapi X(k-1).
Gambar State space
tree untuk MCOLORING ketika n=3 dan m=3
Loop yang utama
dari MCOLORING secara berulang mengambil sebuah elemen, dari berbagai
kemungkin-kemungkinan, kemudian membaginya ke dalam X(k) dan kemudian memanggil
MCOLORING.
Procedure NEXTVALUE (k)
Global integer m,n, X(1:n) boolean
GRAPH (1:n,1:n)
Integer k
Loop
X(k) –(X(k)+1) mod (m+1)
if X(k) = 0 then return andif
for j-1 to n do
if GRAPH(k,j) and
X(k) = X(j)
then
exit endif
repeat
if
j = n+1 then return endif
repeat
end NEXTVALUE
|
|
Setiap path
untuk sebuah daun diwakili dengan sebuah pewarna yang memakai tiga warna. Bahwa
hanya 12 warna penyelesaian yang keluar dengan tepat tiga warna.
Gambar Sebuah graph dengan 4 node dan 3 pewarnaan yang
mungkin
3.
Lingkaran Hamiltonian (Hamilton Cyclles)
Misal G = (V,E) adalah graph terhubung dengan vertice.
Lingkaran Hamilton (diciptakan oleh Sir William Hamilton) adalah buah circuit dengan n edge dari G yang dikunjungi sekali oleh setiap vertex dan kembali pada posisi semula. Dengan perkataan lain jika
sebuah lingkaran Hamilton dimulai dengan beberapa vertex v1 dan vn+1 yang sama.
Kita sekarang akan melihat pada algoritma backtracking yang menemukan semua
lingkaran Hamilton ini di dalam Graph.
Graph itu mungkin terhubung tetapi
mungkin saja tidak. Hanya circuit yang
berbeda yang akan menjadi keluarannya.
Gambar Dua graph,
hanya satu yang mengandung lingkaran Hamilton
Pemecahan dengan backtracking
vector (xi, …, xn)
telah dibatasi sehingga x1 yang diwakilkannya telah dikunjungi vertex dari rencana circuit. Sekarang yang perlu kita lakukan adalah menyelesaikan
bagaimana menghitung vertice yang
mungkin dari xk jika x1, x2, …,xk-1
siap dipilih.
Jika k=1, maka x(1) didapatkan n vertex.
Cara lainnya untuk menghindarkan n kali bekas-bekas
lingkaran yang sama, kita menghendaki x(1)=1.
Jika 1 k n, kemudian X(k) menjadi beberapa vertex v yang berbeda dari x(1), x(2),…,
x(k-1) dan v dihubungkan dengan sebuah edge
untuk x(k-1).
X(n) hanya dapat menjadi satu-satunya vertex dan merupakan hubungan dari
x(n-1) dan x(1). Kita mulai dengan prosedur NEXTVALUE yang menyelesaikan vertex selanjutnya yang mungkin, dari circuit yang sudah direncanakan.
|
|
Procedure NEXTVALUE (k)
Global integer n, x(1:n) boolean GRAPH
(1:n,1:n)
Integer k, j
Loop
X(k) –(X(k)+1) mod
(n+1)
if x(k) = 0 then
return andif
if GRAOH(x(k)-1), x(k))
then
for j-1 to k-1 do
if
x(j)=x(k)
then
exit
endif
repeat
if j=k
then if k n or (k=n and
GRAPH (x(n),1))
then return
endif
endif
endif
endif
repeat
end NEXTVALUE
|
|
Dengan memakai prosedur NEXTVALUE kita dapat
menyebutkan satu demi satu skema backtracking
secara rekursif untuk menemukan semua Hamiltonian
cycle.
|
|
Procedure HAMILTONIAN (k)
Global integer x(1:n)
Local integer k,n
Loop
Call NEXTVALUE(k)
If x(k)=0 then return andif
If x(k)=n
Then
print (x,’1’)
Else
call HAMILTONIAN (k+1)
Endif
Repeat
And HAMILTONIAN
|
|
Prosedur ini dimulai matrik adjacency GRAPH (1:n, 1:n), kemudian memasukkan x(2:n) ß0, x(1) ß1 dan kemudian melakukan call HAMILTONIAN(2).
4. Masalah
Knapsack (Knapsack Problem)
Persoalan
knapsack ini mempertimbangkan kembali section,
yang mana akan didefinisikan serta memecahkan permasalahan algoritma
pemrograman secara dinamika. The Zero-One
yaitu mencari hasil yang paling baik secara zero-one
pada knapsack tersebut.
Procedure BOUND (p,n,k,m) determinan upper bound didapat solusi
yang lebih baik. Dengan perkembangan node
z pada level k+1 dari space state
tree. Hal yang utama berat dan totalnya W(i) dan P(i).
(i) dan dengan asumsi itu P(i)/W(i) ≥
P(i+1)/W(i+1)
|
|
Procedure BOUND (k)
Global integer n, PC(1:n),W(1:n)
integer k,i: rela b,c,p,w,M
b ßp ; c ßW
for i ß k+1 to n do
c ß cw(i)
if c < M then d ß p + P(i)
else return (b+(1-(c-M)/W(i)) *
p(i))
endif
repeat
return (b)
end BOUND
|
|
2.4 Implementasi
Algoritma runut balik
Algoritma runut balik ini banyak
digunakan pada beberapa program, seperti program permainan sudoku, program
permainan kuda menyebrang jembatan dengan lintasan Hamilton, program pencarian
solusi game maz (labirin), dan juga
digunakan dalam gerak animasi 3D, dan beberapa program yang lainnya.
2.4.1
Program permainan Sudoku
2.4.1.1
Gambaran umum teka-teki Sudoku
Sudoku adalah suatu permainan teka-teki
yang memiliki aturan sederhana. Teka-teki ini terdiri atas 9 buah blok yang
berupa tabel 3 × 3. Sebagian sel tabel dalam teka-teki ini telah diisi dengan
angka-angka yang berupa patokan untuk menyelesaikan teka-teki. Tujuan permainan
ini adalah untuk mengisi setiap sel tabel yang masih kosong dengan angkaangka, sedemikian
sehingga dalam 1 blok hanya terdiri atas angka 1-9 yang tidak berulang dan
tidak ada angka yang berulang dalam 1 baris maupun kolom. Meskipun aturannya
sederhana namun penyelesaian teka-teki ini tidak semudah aturannya. Tentu saja
tingkat kesulitan tiap teka-teki dapat bervariasi. 2.2 Strategi umum penyelesaian teka-teki
Sudoku Secara umum, Sudoku dapat diselesaikan dengan kombinasi teknik
pemindaian (scanning), penandaan ( marking), dan analisa (analysing). Beberapa tekiteki Sudoku yang tergolong
mudah dapat diselesaikan hanya dengan salah satu proses, namun pada umumnya
kita harus mengkombinasikan ketiga teknik tersebut.
a. Pemindaian
Berupa proses memindai baris atau kolom
untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka-angka
tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara
sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang
nilai-nilai yang tidak mungkin.
b. Penandaan
Berupa analisa logika, dengan menandai
kandidat angka yang dapat dimasukkan dalam sebuah sel.
c. Analisa
Berupa eliminasi kandidat, dimana kemajuan
dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah
sel hanya punya 1 kandidat.
2.4.1.2 Penerapan algoritma runut balik dalam
teka-teki Sudoku
Algoritma runut balik sangat efektif dalam
mengurangi jumlah pencarian kemungkinan solusi teka-teki. Menurut perhitungan
ada sebanyak 6,670,903,752,021,072,936,960 jumlah kemungkinan status untuk
teka-teki Sudoku berukuran 9 x 9. Suatu angka yang sangat besar jika ingin
dicari secara brute-force, dengan kompleksitas. Garis besar algoritma runut-balik untuk
menyelesaikan teka-teki diberikan di bawah ini:
procedure solve()
{
menyelesaikan teka-teki Sudoku
pada papan n2 * n2,
versi: rekursif
}
Algoritma
if( isDone() ) then
exit()
{papan sudah selesai diisi
program selesai}
else
updateTabel()
{update sel tabel yang masih
kosong}
if( not isValidBaris() ) then
backtrack()
else
{jika baris valid maka
periksa kolom}
if( not isValidKolom())
then
backtrack()
else
{jika kolom valid maka
periksa blok}
if ( not isValidBlok())
then backtrack()
else
{jika blok valid maka
panggil rekursif}
solve()
|
|
Deklarasi
Global
|
|
N : integer
{adalah ukuran papan sudoku }
tabel : array[1.. N2] of
array[1..N2]
{representasi papan sudoku}
|
|
2.4.2
Program Permainan Kuda Menyebrang Jembatan
2.4.2.1 Permasalahan game
Persoalan
yang muncul pada game kuda menyeberang jembatan adalah bagaimana menghabiskan
balok / kotak dan kuda kembali ke posisi awal. Setiap kali berpindah balok,
maka balok tersebut akan jatuh, ini berarti kuda tidak dapat menggunakan
lintasan yang sama dalam perjalanannya.
2.4.2.2
Penyelesaian Lintasan Hamilton
Salah
satu permasalahan dalam penyelesaian lintasan Hamilton pada game kuda
menyebrang jembatan yakni :
Diberikan
sebuah papan yang berisikan kotak – kotak yang berjumlah 14 kotak. Kuda
diletakan pada posisi awal yakni posisi bebas (misal : kita taruh posisi kuda
pada kotak 1 ), kuda harus bisa melewati semua kotak tanpa harus balik lagi
dengan aturan jalan (membentuk huruf L) sampai semua kotak itu habis dan kuda
harus balik ke posisi awal yakni posisi 1 agar kuda dapat menyebrangi jembatan
dengan selamat. Persoalan perjalanan kuda catur ini merupakan permainan kecerdasan
logika di mana pemain harus memikirkan strategi dalam setiap langkah kuda.
Penyelesaian:
1.
Solusi
persoalan
Solusi persoalan dituliskan dalam
vektor dengan 14 kotak / tuple yang berisi urutan dari kotak yang dilalui oleh
kuda. Posisi kotak dituliskan dalam bentuk dua digit integer. Misal : posisi
kuda di nomor 1 maka dia bisa melangkah / jalan ke nomor 7,8,10. Solusi dicapai
apabila seluruh kotak dalam papan sudah dilewati oleh kuda.
Contoh solusi:
S
= (12,23,31,..dst)
|
|
12
|
13
|
14
|
|
8
|
9
|
10
|
11
|
|
4
|
5
|
6
|
7
|
|
|
1
|
2
|
3
|
Dikatakan solusi apabila kuda telah mengambil langkah
seluruh kotak / tuple dan tidak kembali lagi ke kotak semula sampai dia kembali
ke posisi awal pertama kali kuda mengambil posisi.
2. Fungsi
pembangkit
Fungsi
JalanKuda(k) membangkitkan kotak berikutnya yang dilalui kuda dan memasukkan
kotak tersebut ke dalam solusi persoalan. Kotak berikutnya didapat dengan
memilih salah satu elemen dari list yang dihasilkan fungsi JalanBerikut(k).
Dari list tersebut dipilih posisi dengan
jumlah elemen JalanBerikut(k+1) yang terkecil.
Fungsi – fungsi bantuan:
Fungsi jalanBerikut(k) menghasilkan ListJalan yang berisi
list dari posisi kotak berikutnya yang dapat dilewati oleh kuda, serta jumlah
elemen dari ListJalan pada jalanBerikut(k+1).
Contoh:
Fungsi
JalanBerikut(1) menghasilkan ListJalan : {(7,8,10)}.
Artinya kuda dari kotak 1 bisa berjalan ke kotak 7
atau 8 atau 10 sehingga kuda mempunyai 3 kemungkinan, demikian juga setelah
kuda berjalan ke kotak berikutnya maka kuda mempunyai beberapa kemungkinan
tergantung kuda tersebut mempunyai kemungkinan untuk melangkah. Dari list
tersebut dipilih kotak dengan alternatif jalan berikutnya yang paling kecil,
jika sama maka pilih salah satu dan kotak yang lain dimasukkan ke dalam alternatif
jalan bila diharuskan melakukan runut balik.
3. Fungsi
pembatas
Bila kuda tidak bisa berjalan lagi tetapi masih ada kotak
yang belum dilewati maka kotak tersebut dilewati dan melakukan runut-balik ke
penanda runut balik terdekat.
Aturan yang
berlaku agar bisa menemukan solusi :
1.
Langkah
berikutnya harus mempunyai jumlah kemungkinan langkah selanjutnya yang lebih
kecil dibandingkan langkah yang lain. Bila ada jumlah langkah selanjutnya yang
sama, maka menjadi penanda bila terjadi runut-balik.
2.
Bila
langkah yang dipilih ternyata tidak menemukan solusi, maka runut-balik ke
penanda
runut-balik yang
terdekat.
3.
Lakukan
langkah tersebut hingga ditemukan solusi.
Analisa 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 / belum mengetahui
apakah langkah yang kita ambil merupakan langkah yang terbaik, sehingga
memungkinkan terjadi terlalu banyak backtracking yang harus dilakukan.
Hal ini dapat diminimalisasi dengan menggunakan
fungsi Heuristik untuk menentukan langkah yang lebih optimal.
Penggambaran proses pencarian solusi
menggunakan algoritma runut-balik dengan pohon graf alur perjalanan kuda :
|
|
Runut
balik disini ditunjukkan
(karena
terlalu banyak)
Tidak
ditemukan solusi dan
runut balik ke atas
|
|
2.4.2
Program Permainan Maze (Labirin)
2.4.2.1 Gambaran umum game
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.
2.4.2.1
Konsep game
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.
2.4.2.1
Solusi
function SolveMaze(input M : labirin) boolean
{ true jika solusi ditemukan, false jika tidak }
Deklarasi
arah : integer { up = 1, down, 2, left = 3,
right = 4 }
Algoritma:
if solusi
sudah ditemukan then
return true
else
for tiap
arah gerakan (up, down, left, right) do
move(M,arah) {pindah satu langkah (satu sel)
sesuai arah tersebut }
if SolveMaze(M)
then
return true
else
unmove(M, arah) { backtrack }
endif
endfor
return false
{ semua arah sudah dicoba, tetapi tetap buntu,
maka kesimpulannya: tidak ada solusi }
endif
|
|
Ada
dua solusi yang bisa digunakan untuk permainan ini, yakni secara iteratif dan
rekursif. Di bawah ini akan disajikan solusi secara iteratif:
Algoritma nya adalah sebagai berikut:
Dalam game ini, algoritma akan
membagi 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).
|
|
|
|
|
Contoh runut balik pada sebuah labirin, runut balik diperlihatkan
dengan garis putus-putus
|
|
|
|
|
Contoh runut balik pada labirin penuh
|
|
BAB
III Penutup
3.1
Kesimpulan
3.2
Saran-saran
Daftar
Pustaka
Tanggal 20 Desember 2010
