PENERAPAN METODE DEPTH FTRST SEARCH (DFS) PADA PERMAINAN }4ENARA HANOI (Depth First Search on Hanoi Tower Game) Nur Wakhidah
Fakultas Teknologi lnformasi dan Komunikasi Universitas Semarang
Abstract game u putz1 The Tower of Hanoi (also knownas lhe lowers of Bnhma) is a mathematical can slide onto any rd. Tb It consists of three rods, and a number of disks of different sizes whbh pirrtesfarfs rvdh the drsks neatly stacked in order of size on one rod, the slnqlle{,{,fhe of ionicatshape. tn this'problem, the sotution can be solved by applying Methd
tfl'-frf W
iiiiig i
Firsf Search (DFS). Key,vords
: Depth
Firsf Search, Tower of Hanoi
1.
PENDAHULUAN Menara Hanoi merupakan sebuah teka{eki yang ditemukan oleh seorang matematikawan
-Perancis,
Edouard Lucas pada tahun 1883. Legenda mengenai Menara Hanoi ini berasal dari sebuah kuil lndia, dimana terdapat sebuah ruangan besar dengan tiga buah menara raksasa. Permainan initerdiri dari tiga menara dan M buah piringan besar dengan ukurannya berbeda satu sama lainnya yang bisa dimasukkan ke menara mana saia.
Permainan dimulai dengan 64 buah piringan tersebut yang tersusun rapi berdasarkan ukurannya dalam salah satu menara dengan ukuran piringan terkecil diletakkan teratas, sehingga bentuknya menyerupai sebuah Piramid.
Menurut legenda tersebut,
dikatakan bahwa iika anda selesai memindahkan selunlt M piringan, pada saat itu juga dunia kiamal hi
menurut legenda, yang mungkin iuga benarBila legenda ini benar, bayangkan iika unEft setiap pemindahan memerlukan waktu 1 (sab) detik. Anda bisa menghitung berapa detik yarg diperlukan unfuk memindahkan seluruh 64 piringan dari menara asal ke menara tujuan Jika pendeta itu bisa memindahkan satt piringan tiap detik menggunakan pemindahan paling sedikit, maka akan memakan wakfu 2a-1
detik atau kurang lebih 584.582 milyar tahunSecara umum untuk menyelesaikan n buah piringan dipedukan pemindahan sebanyak
?
-
1 kali.
Menara Hanoi meruPakan salah
satu
permainan yang unik karena memiliki berbagai membutuhkan macam penyelesaian yang berbeda untuk tiap variasinya. Permainan ini sering digunakan
variasi Yang
dalam penelitian psikologis dalam
hal
pemecahan masalah. Selain itu, juga cukup dikenal oleh para mahasiswa ilmu komputer
Gambar 1 Model Menara Hanoi dengan 8 Piringan
44
karena sering digunakan pada pengenalan struktur data dan algoritma. Permainan iniiuga digunakan sebagai ujian ingatan oleh ahli
Penerapan Metode... (Nur W.)
psikolog syaraf dalam berupaya mengevaluasi amnesia.
A
sebagai menara asal, menara T sebagaimenam tujuan
Permasalahan pada permainan Menara
ini adalah bagaimana
cara
memindahkan semua piringan dari menara asal ke menara tujuan dengan banfuan satu menara bantu yaitu menara sementara. Adapun aturan-aturan permainannya, sebagai berikut i
. .
KeadaanAwal
Bila didefinisikan menara
2. ATURAN PERMAINAN Hanoi
a.
Dalam setiap pemindahan hanya dapat
S sebagai menara semeniara, 3 jumlah piringan yang masing-masing 9gl_g_rl didefinisikan sebagai p1, p2 dan p3 dimana ukuran P3 > P2 > p1. Menara A berisi 3 piringan dengan susunan p3, p2, pl dari baurah ke atas. Sedangkan menara T dan S dalam kondisi tidak ada piringan (kosong). Untuk lebih jelasnya dapat dilihat pada gambai3 berikut. dan menara
memindahkan 1 piringan saja.
Pada proses pemindahan hanya dapat menuju ke satu menara saja.
Piringan yang boleh dipindahkan adalah piringan paling atas ke menara tertentu.
-
Piringan yang lebih besar ditempatkan di
AST
bawah piringan yang lebih kecil.
Gambar 3 Keadaan Awal
3.
IDENTIFIKASIRUANGKEADMN Permainan Menara Hanoi yang akan di bahas dalam penulisan ini menggunakan 3 menara dan 3 piringan. Dlmana ukuran piringan tersebut berbeda satu sama lain. Semua piringan berada pada menara asal dengan susunan secara berurutan, yang terbesar berada pada posisi paling bawah dan yang terkecil pada posisi paling atas seperti yang
b. Keadaan Tujuan Menara
A dan S kosong, sedangkan
menara T berisi piringan p3, pi, p1 tensisun dari bawah ke atas seperti yang terlihat pada gambar 4 dibawah ini.
tampak pada gambar 2 di bawah ini.
ti
11.
E
AST Gambar 4 Keadaan tujuan
II li
'.!
5.
-. Gambar 2 ldentifikasi Ruang Keadaan
4. KEADMN AWAL DAN KEADMN TUJUAN
Dalam proses pemecahan
Untuk mencapai keadaan tujuan maka dibuatlah aturan-aturan yang dapat memenuhi semua keadaan yang mungkin terjadi. Adapun aturan-aturan tersebut adalah sebagai berikut : 1. Jika S kosong atau ps > pa, pindahkan pa
masalah
permainan Menara Hanoi perlu ditetapkan suatu keadaan awal dan keadaan tujuan untuk mempermudah penyelesaiannya.
PENUTUP
keS
2.
Jika T kosong atau pr > pa, pindahkan pe
keT
3. Jika A kosong atau pa > ps, pindahkan ps keA
JURNAL TRANSFORMATTIG, vorume 7, No. 1, Juri zoos : aa
-;o
45
9'
09
- W:
6002 lrnr 'L 'oN 'z aunron 'V)il-VNUOJSNVUT
sd uatqepurd ,sd < vd nele ouoso1 ,Hl vd uelqepurd 'vd < 1d nBle ouosol rfil ,il|
.t .z
vd uqqepud 'vd < sd nere ouoso1 .l mryoq re6eqas qelepe lnqasral uBrnle-uernle :
undepy 'lpelal urlDunu 6ue[ ueepeal enuos rqnuoueu ledep 0uel ue.,nle-uernle qellenqtp BIeu uenfnl ueepeal redecuau Inlun
drunNtd uenfn1 ueepea;1
rvNunr
'er(uueresala,iuad qepnuuedulauu
Inlun uenln1 ueepeol uep le/{p ueepeal qens ue1de1a1p npad toueH ereuayl ueureuad qeleseu ueqeceued seso.rd ulele6 NVnrnl
NWO\Ely NVO tVArrV NWOVI)| uespeay 6ueng tsollltluopl
Z
-?
rpquee
'9
, requeg
tut qe/neq rp T teque0 eped 1edue1 6ue,( pedas se;e 6ur1ed rsrsod eped ;ic.1ra1 6ue,( uep Our1ed rsrsod eped epe.raq
_qe/y\eq
eped leqrpal ouer pades't,}q;t?'1rffiff3 unsnsJal ld'Zd'96 ueOuurd lspoq ereuou
uelOuepes '6uoso>1
S
uep
I
V e.Gu.y,1
uenfnl uepppay
.q
lBruv ueBpBax g JequlBe
ISV
Jesaqlol 6ue[ ,ue1ruruaq etBcos ueunsns ueOuep lese eleuau eped ppetaq ueOuurd enuJss 'ulel eulBs qes epaqraq lnqasJal ue6uuld uanln eueu,tg .ue6uurd uep ereuau g ueleun66uou !u! ues;nuad tuelep seqBq rp ueIB 6ue,t rouep e.leuary ueuteuuad NWoV?)| eNVnU lsDilJtlN3ot .r 'ilcal qtqq Due,t ueDurrrd qervreq rp ue4edualtp resaq qgqal 0ue,i ue6uur6
'nluapq BJeuau aI sEe 6ur1ed ueOuurd r.lslBpe uelqepuldlp qaloq 6ue,{ ue0uur6
plpaq g rque6 eped leq1pp ledep e[usept qlqalrylun '(6uosog ue6up;d BpB lepg lslpuol uepp uep 1 eleuau uelOuepag .sEB aI S td 'Zd'td ueunsns ue0uep ueOuurd
qefieq pep
0
.Ld lspoq v erBuat/ll < zd < 0d uBrnln Bueutlp €d uep ed ,[d re6eqas ueltslugaplp Ouseur6ulseu 6uBi( ue6uuld qelurnt g ueOuap 'e.tEuouias eleuou, pOeqas S eJBuauJ uep uen[q aeuau p6eqas 1 BJBUauI ,1ese eleuaru reOeqas ersuorx uellsluuep'p ellg
efes ereueu n]es aI nfnueur ledep elueq ueqepurured soso.rd eped e[es ue6uuld I uelqeputu]au ledep e,(ueq ueqepuruad den., uele6
'e,(uueureured'ueJnl'-ueJnrr
"'ffi:J[?tot'
'BJEUAUIaS BJeUAUJ n1re,t nlueq eJeueuJ
nles uequeq ue6uap uenfn1 eJeuau,l eJBUeur
oI
lese
pep ue6uprd enuas uelLleputuau
eJBo eueure0eq qelepe lul
toueH
BJBuayI ueuraurad eped ueqeleseuJed NVNIWU3d NYUNIV
V
'I
tJi;;ffi
lE$V uBBpPoy 'E
rsenleneouau eledruaq uelep
rrrr^.
4. Jika T kosong atau Pr > Ps, pindahkan Ps
-
keT
5.
Jika terdapat lebih dari satu solusi yap sama tetapi berada pada level fag
urtl
Jika A kosong atau Pe > P1, pindahkan Pr
berbeda, maka DFS tidak menjamin menemukan solusiyang paling baik. Arthya
keA
6, Jika S kosong atau Ps > Pr, pindahkan Pr
DFS tidak optimal.
keS
Langkah-langkah pencarian sohsi
6. SOLUSI
menggunakan metode DFS
Salah satu metode yang dapat dipakai dalam proses pemecahan permasalahan pada permainan Menara Hanoi yaitu menggunakan
metode DFS {Depth F,rsf Search)
a.
atau
pencarian mendalam.
Metode
DFS (Depth Firsf
Search)
merupakan metode pencarian yang dilakukan pada suatu simpul dalam setiap level dari yang paling kiri, Jika pada level yang terdalam solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpulyang kiri
adalah
sebagai
berikut:
b. c.
Solusi dicari dengan membentuk linEsan dari akar sampai daun. Simpul-simpul yang sudah dilahirkan dinamakan simpul anak kiri dan simpulanak kanan. Simpul yang dibentuk, terlebih dahulu simpul sebelah kid dan mendalam sampai ditemukan solusi. Jika lintasan yang sedang dibentuk tidak
dapat dihapus dari memori. Jika pada level yang
mengarah ke solusi, maka lintasan yang sebelah kiri dihen$kan disebut simpul mati dan dilanjufl
paling dalam tidak ditemukan solusi, maka pencarian dilanjut
terdekat. Simpul yang sudah dihentikan (simpul mat) tidak akan pemah diperluas
Demikian seterusnya sampai ditemukan solusi.
lagi.
Kelebihan dari metode Depth First Search yaitu :
dibangkitkan, maka pencarian
-
Bila tidak ada lagi simpul anak yang dapat solusi
Jika solusi yang dicari berada pada level yang dalam dan paling kiri maka DFS akan
dilanjutkan dengan
menemukannya dengan cepat.
Selanjutnya simpul ini menjadi simpul hidup yang baru.
Jika
pembentukan
diimplementasikan dalam program,
penggunaan memori akan lebih sedikit karena hanya simpul-simpul pada lintasan
e.
melakukan
ke simpul hidup terdekal
Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi.
yang aktif saja yang disimpan. Adapun kelemahan dari metode Depth search yaitu
-
:
First
Solusi permasalahan unfuk pemindahan seluruh piringan dari menara asal ke menaftl tujuan pada permainan Menara Hanoi dengan
Jika pohon yang dibangkitkan mempunyai metode DFS dapat dilihat pada tabel 1 dan level yang sangat dalam (tak terhingga), gambar 5 berikut ini. maka tidak ada jaminan menemukan solusi. Artinya DFS tidak komplit.
Tabell Solusi Permainan Menara Hanoi No
4 I
Keadaan (P1,P2,P3)A (0,0,0)s (0,0,0)T
AWAL
46
Aturan
Aksi (0,P2,P3)A
2
Pindahkan P1 dariA ke T
(0,0,0)s (P1,0,0)
Penerapan Metode... (Nur W.)
L'
09
-w
: 6002
ltnt
slo uBlecPlad
'[
'oN 'L aunlon \Dill.VnuoJSNVUI tVNUnt
uorlod g rPquBg
rmli--".--.
1ilffi#kil LtrR, E:=!;+ffi
ffi*t,{r?gt4tr,f1 --------tqro,ry
ffiffirl -Tffi ffiffi,ffir+l
trff[i'----_.-
@@
:ryrnrvl
fr"'-s"y.-E ttrwrd----rwrd-------_
ffil
-,,.-.'-'tm[t
lrrunuv
ffiffi-Bl 2 tylhfv --.-- 2lffr -----.---
1 aI Vpep
Id uelqBpurd
Z
r(td'zd'o) s(o'o'o)
L
v(o'o'la)
ffiffiSffiY\tl:tlur.i
r(td-zd'0,
I
s(0'0'0)
aI
S
yepzd ualqPpurd
v(o'o'ld) r(gd'0'0) s(o'zd'o)
v aI s psp ld uElrtPpurd
t 0
v(o'o'Ld)
r(0d'0'0) s(o'zd'Id)
l
I
aI Vpep td uelqeputd
I(ed'0'0) s(o'zd'o) v(o'o'la) r(td'0'0) s(o'zd'td)
I I
v(o'o'o) 1(0'0'0) Z
v(o'o'o)
s(o'zd'la)
n
v(od'o'o)
r(0'0'0) s(o'zd'Id) v(td'o'o) 1(00'rd)
s
0)t l
pep ld
uDlqepurd
I
1(0'0'td) s(o'zd'o)
0
v(u'o'o) s aI v yepzd uexqepurd
s(o'ed'o) v(0d'0'0)
r(0'0'rd I
)
s(o'o'o)
Z
v(td'zd'o)
Dari aturan {ru/e base) yang ada dapat pula ditemukan beberapa altematif solusi permasalahan. Hal ini membuktikan bahwa langkah tersebut lebih panjang atau lebih lama (lambat) dalam proses penyelesaian masalah. Untuk lebih jelasnya dapat dilihat pada Tabel 2 dan Gambar 6 berikut
Tabel 2 Alternatif Solusi .
No
Keadaan
Aturan
'.,t+-ri.tiit[f!,
(P1,P2,P3)A
(0,P2,P3)A
(0,0,0)s 1
(0,0,0)T
1
Pindahkan P1 dariA ke S
(0,0,P3)A
(0,P2,P3)A
(P,l,0,0)s
2
Pindahkan P2 dariA ke T
(0,0,P3)A
4
(P1,0,0)s
3
Pindahkan P1 dari S ke A
(0.P2.0)T
(P1,0,P3)A
(P1,0,P3)A
(0,0,0)s
6
Pindahkan
n
dulT ke S
(0,P2,0)s
(0,0,Pl!)A 1
Pindahkan P1
daiA ke S
(0.0.0.)T
(o,0,PB)A (P1,P2,0)S
(0,0,0)A 2
Pindahkan P3 dariA ke T
(P1,P2,0)S (0,0,P3)T
(P1,0,0)A 3
Pindahkan P1 dariS ke A
4
Pindahkan P2 dariS ke T
(0.0.P3)T
I
(0,0,0)s (0.P2.ft117
(P1,0,0)A
,(01
(0,0,0)s
I-0j
(0,P2,P3)T
4B
(0,P2,0)s {0.0.PB)T (P1,0,0)A
(P1,0,0)A
(0,P2,0)s
(P1,P2,0)S
(0.0.H})T
(0,0,0)A
I
(P1,P2,0)S
(0^ 0.0)T
{0.0.0)T 7
(0,P2,0)s (0.0.0)T
(P1,0,P3)A
6
(Pl,0,P3)A (0,0,0)s
(0.P2.0)T
(0,P2,0)T 5
(P1,0,0)s (0.P2.017
(0,0,0)T 3
(P1,0,0)s (0,0,0)T
AWAL 2
.i..,Mrri:r.ilidf.l
' :,irdrH88l
2
Pindahkan P1 dariA ke T
"G
iGC
Penerapan Metode... (Nur W.)
6t
09
-w
: 6002
llnr 'L 'oN 'Z aunlon 'wlIVl^tuoJSNVUl- lVNUnt
e1e,(ua1 '11eI t. - uJ telueqas ueqepururad
uelnpadlp ueOuurd qenq N
'pq
'roueH BJeuaf{ ueureulad eped qe;esetu
6u11ed
ueqeceuad e/(qeq lllnqral qelol 'SJC opolaul eped ueqrqolal ue6uep tensas
Inlun
uBp uelBp 6ue[ 1ana1 eped epaeq uecrp 6ueI rsnlos lEq eueutp uelnureyp ladac 6ulted Oue[ rsnlos rlBlBpB lleq]a] 6ue,{ lnqosJol ueqeleseurad pep lsnlos BueuJtg 'rsnlos ederaqaq ue6uep uelresalasrp ledep
ueltesala,(ueu
ndtueu SJo
apolay,{
:]nIUaq
teDeqas uellndursrp ledep loueH Breuan ueureurad eped qeleseu uerlaoor.r.tad seso:d '(qcreag p11 qldeg)
Sl0 opoleu ue6uag Nv-rndilils3x
roueH eJeua]l ueureuued ueqegeseuuad
'L
rsnlos Jllpurollv uBleeslad uorlod g rEqueg
Eil
@
sfifri-i :
iri\.t.arr.t
'I1109
ffi ,""
i
T ,$->
ItJri/)St)H)e
ttlltr?x$:,
dengan menggunakan metode
DFS
terbukti pula untuk 3 buah pidngan dapat diselesaikan dengan 2 3- 1 langkah = 7 langkah. DAFTAR PUSTAKA
Atmavidya, Arif Nanda, Penenpan Algonfua
Backtracking dalam Penaian Solusi Menara Hanoi, lnstitut Teknologi Bandung, 2008
Mukti, Garibaldy
W,
Berbagai Solusi of Hanai dan
Pemecahan Masalah Tower
Represenlasi Grafnya, lnstitut Teknologi Bandung,2008
Santosa, lnsap, Sfrukfur Data menggunakan Tufio Pascal,Andi Offset Yogyakarta, 2003 Suyanto, Artifrcial lntelligence, lnformatika Bandung,2007 Wikipedia, h
ttp :/len.
wikipedia.orq/wikiffowe
diakses 10
50
r of Ha noi,
Desember
2008
Penerapan Metode... (Nur W.)
