Techno.COM, Vol. 10, No. 3, Agustns
20ll:98-107
SOLUSI PENCARIAN N-PTJZZLE DENGAI\I LANGKATI OPTIMAL : SUATU APLIKASI PENDEKATAN FUNGSIONAL Wijanarto Program Studi Teknik Informatika, Fakultas llmu Komputer, Universitas Dian Nuswantoro, Semarang 50131 E-mail :
[email protected]
Abstract This paper aims to determine a more optimal search techniques on a cqse study of n-puzzle problem solving. Some algorithms are in review as breadth-first sea'rch,
depth-first search, hill-climbing, beam, best-first searching and optimization with A * (A-stql) search becomes case study in simulated using a fuictional approach. Test simulation is based on the dfficulty level of the initiil siate that is givenfrom the category configuration easy, medium, hard and ugly, the cqlculation i7 th, amount of expansion produced by each algorithm are discussed, as well as th; fime profile (report-time) of the design solution in proposing, show that the search with a * optimization method gives optimum results on n-puzzle solving compared to all other algorithms. By understqnding the heuristic search algoithm is expected to help resolve the problem optimally is based on the case other than a puzzle. Keywords : A Star, Heuistic, N-Puzzle, Search,functional
1.
bidang ekonomi, robot pencari jejak (panas,
PENDAHULUAI\
Di sadari atau tidak, dalam praktek kehidupan sehari-hari, kita selalu melakukan kegiatan yang disebut
pencarian. Pencarian atau searching menempati isu yang penting dalam dunia komputasi khususnya dan ilmu komputer pada umumnya U,2,31. Konsep dasar teknik pencarian menernpati porsi yang sangat strategis, dimana hampir seluruh kegiatan komputasi mendasarkan pada kegiatan ini [4]. Mulai dari pemahaman konsep struktur data dan algoribna hioggu
artificial intelligence, teknik
pencarian
menjadi primadona bahasan utama [12].
Algoritona berbasis teknik
pencarian
(Searching Technique Atgorithms), bahkan
dapat
di
aplikasikan pada bidang diluar komputasi, pencocokan DNA pada (Genetic Algorithm) di bidang kedokteran dan biologi, neural network,optimasi pemilihan banyak kriteria dengan banyak alternatif di
sinyal) di bidang rekayasa robotika dan masih banyak lagi [8]. Selain bidang seperti diatas, game merupakan salah satu bidang
yang menarik yang berhubungan dengan teknik pencarian dalam artificial intelligence.
Permainan dapat menghasilkan ruang Ini cukup besar dan kompleks yang memerlukan pencarian yang sangat besar. Hal
teknik yang kuat untuk menentukan apakah alternatif yftng di pakai dalam mengeksplorasi problem space tersebut. Teknik ini disebut heuristik dan merupakan area utama penelitian artificial intelligence.
Heuristik adalah strategi
pemecahan
masalah yang berguna tetapi berpotensi dapat keliru, seperti memeriksa unhrk memastikan bahwa suatu alat tidak responsif. N-Puzzle adalah salah satu game klasik yang menarik untuk di amati guna mencapai pemahaman terhadap konsep pencarian solusi masalah. Salah satu varian dari N-Puzzle adalah 8-puzzle yaitu papan
20ll:
Techno.CAM, Yol. 10, No. 3, AgLtstlts
berukuran 3 x 3 yang terdiri dari delapan kotak angka dengan satu kotak kosong untu dapat dipindahkan. Walaupun space state lebih kecil dat'' ll-pr,uzle, namun tetap saja menjadi menarik jika kita ingin mengetahui
berapa langkah yang paling cepat atau pendek yang dapat di temukan Pada masalah ini. Dengan memberil
tingkat kesukaran tertentu
(mudah, d memeriksa
menenga[ sukar dan buruk) untuk selesaikan"
lalu kita akan
dengan algoritma teknik pencarian dengan
uninformed search
dan
hueristic,
diharapkan dapat mengetahui ekspansi terkecil dari path yang di hasilkan oleh masing-masing algoritrna yang dipakai untuk mengamatinya. Laporan beruPa profile waktu, jumlah pemanggilan fungsi,
konstruksi memory serta kebutuhan memory bagi fungsi menjadi infonnasi yang lengkap yang dapat di sediakan oleh alat
l2), pada jenis
99
algoritma ini
perbedaannya terletak pada urutan node yang akan di ekspan. Algoritma yang di bahas pada bagian ini meliputi breadth-first dan depth-first search. 2.1. Breadth First Search
Merupakan algoritna sederhana dengan strategi untuk melakukan ekpansi pertama mulai dari root kemudian seluruh adjencent node atau seluruh tetangga dari node tersebut akan di ekspansi (traversal node), begitu seterusnya hittgga mencapai semua tiap node terakhir (leaf) sudah di kunjungi [1,2,11]. Dengan kata lain, algoritma ini merupakan pencarian yang exhaustive ke seluruh graph tanpa mempertimbangkan ada atau tidaknya tujuan hingga seluruh node terkunjungi. Dengan memanfaatkan queue untuk menyimpan node root yang akan di ekspansi maka pencarian dengan
ini akan selalu mengeksplorasi adjencent node yang berada pada queue terdepan, dan berakhir saat queue sudah habis. Breadth-first search akan mengenerate seluruh node hingga kedalaman pada level d, atau I+b + b2+ b3 + . . . + bd iehingga di peroleh O(bd). Pada average case, setengah node pada kedalaman d harus di periks4 dan dengan demikian kompleksitas waktu pada average-case juga o(b") [2,9]. teknik
uji simulai.
ini akan memaparkan beberapa algoritma berbasis pencarian, baik yang
Paper
hueristic maupun uninformed
search.
Eksplorasi terhadap algoritma breadth-first
searc\ depth-first search, hill-climbing, beam, best-frst searching dan optimasi dengan A* (A-Star) search akan menjadi bahasan utama 11,2,3,5). Sedangkan studi
di pilih adalah pada penyelesaian masalah 8 puzz,le, semua algoriha akan di simulasikan dengan
kasus yang
menggunakan pendekatan fungsional yaitu bahasa CMU Common Lisp yang berjalan pada platform linux, dimana selunrh kode
yang di pakai untuk simulasi merupakan modifikasi dari [2] , [6] dan [3]. 2. UNINFORMED SEARCH
artikan juga sebagai blind search, yang berarti bahwa strategi ini tidak memiliki informasi tambahan tentang state di luar yang disediakan dalam definisi masalah. Pencarian pada ranah ini hanya
Istilah ini dapat
state
98-107
di
dapat menghasilkan suksesor
dan membedakan suatu goal state dan non-goal
2.2. Depth-First Search
Pencarian Depth-First akan melakukan pencarian dengan cepat ke node yang terdalam. Pencarian memproses secara cepat ke level terdalam pada tree hingga node tidak mernpunyai suksesor lagi. Implementasi teknik ini memanfaatkan suatu stach dan dengan demikian sering
kali di
implementasikan secara recursive, pada saat mencapai leal maka teknik ini akan kembali (bakctrack ke node di atasnya unnrk melakukan dfs pada adjencent node yang belum di hmjungi). Di sisi lain, pencarian depth-first bisa kehilangan arah karena terlalu jauh ke dalam graph, juga
Techno.COM, Vol. 10, No. 3, Agustts 201
kehilangan path terpendek ke tujuan atau bahkan menjadi terjebak dalam path yang tak terhingga yang tidak tidak mengarah ke tujuan[8]. Kompleksitas waktu dari pencarian mendalam dengan kedalaman d dan faktor branch b adalah O(bd), karena menghasilkan set node yang sama dengan breadt frst, tetapi dengan perbedaan urutan pencarian. Jadi, praktisnya, depth frst search mempunyai keterbatasan waktu dan space yang lebih besar [2,10].
3.IIEURISTIC SEARCH Heuristik adalah kriteria, metode, atau prinsip-prinsip untuk memutuskan yang mana antara beberapa altematif, dari aksiaksi yang menjanjikan paling efektif dalam rangka untuk mencapai tujuan tertentu. Teknik ini mewakili kompromi antara dua persyaratan: kebutuhan untuk membuat kriteria tersebut sederhana dan, pada saat yang sama, keinginan untuk melihat dan membedakan dengan benar diantara pilihan yang baik dan buruk. Bagian pertama dapat di a*ikan, bahwa suatu masalah mungkin tidak memiliki solusi yang tepat karena ambiguitas yang melekat pada pernyataan masalah atau data yang tersedia. Kedua, suatu masalah mungkin memiliki solusi yang tepat, tetapi cost komputasi untuk menemukan itu mungkin menjadi terlalu tinggi. Dalam banyak masalah (seperti game, catur), pertumbuhan state spac€ adalah kombinatorial eksplosif, dengan jumlah state yang mungkin meningkat secara eksponensial atau faktorial pada kedalaman pencarian. Dalam kasus ini, teknik pencarian seperti depth-first atau breadth-first mungkin gagal untuk menemukan solusi praltis. Heuristik mencoba menangkal kompleksitas ini dengan melakukan pencarian di sepanjang path yang paling "menjanjikan" melalui space yang ada. Dengan menghilangkan state yang "tidak menjanjikan", algoritma
heuristik bisa mengatasi
ledakan kombinatorial dan menemukan solusi yang dapat diterima.
I: 98- 107
100
3.1. Best-first Search
Best-fint search merupakan algoritma pencarian yang mengeksplorasi suatu graph
dengan melalcukan ekspanding pada node
ang paling menjanjikan yang di pilih berdasarkan aturan tertentu f1,2,5,7f. Dalam Algorima ini, ruang pencarian dievaluasi menurut fungsi heuristik. Node yang belum dievaluasi disimpan pada list TERBUKA dan mereka yang telah dievaluasi disimpan pada list TERTUTUP. List TERBUKA direpresentasikan dengan priority-queue, node yang belum dikunjungi bisa dequeued dalam fungsi evaluasi. Fungsi evaluasi f(n) dlbtat dengan fungsi hueristic (h(n)) seperti persamaan berikut,
f(n):
h(n) (l)
dimana h(n) akan mengestimasikan cost dengan path termurah dar node n ke goal node, dan jika n adalah goal node maka hfu)A. Kemudian List TERBUKA dibangun dalam rangka f(n), Hal ini membuat best-first search menjadi greedy karena selalu memilih kesempatan lokal terbaik dalam pencarian. Kompleksitas algoritna nI O(b^) baik pada space dan waktunya. 3.2.
A* (A-Star)
Bentuk yang paling luas dari best-first search adalah A* search (disebut juga "Astar searchn). Algoritma ini mengevaluasi node dengan mengkombinasikan g(n) , cost untuk mencapai node, dan h(n.), cost untuk mencapai dari node ke goal di notasikan dengan persaru&an (2) sebagai berikut
:
f(n)=g(n)+h(n) (2) Karena g(n/ memberikan cost path dari awal node ke node n , dan h(n) merupakan cost yang di estimasikan dari path terendah dari n ke goal state, sehingga dapat di tulis, f (n) : estimasi cost solusi termurah melalui n (3) Dari (3), jika kita mencoba menemukan solusi termura\ sangat masuk akal unfuk
mencoba yang pertama adalah dengan mencari nilai terendah dari g(n)+h(n). A Star di kenal sebagai algoritma yang
Techno.COM, Yol. 10, No. 3, Agttstts 2011: 98-107
komplit dan optimal [2]. Dikatakan komplit apabila memori mendukung kedalaman dan faktor branch dari tree, dan dikatakan optimaf apabila pada penggunaan fungsi
heuristic, bersifat admissible (mudah diterima). Karena algoritma ini tetap
melacak node yang di evaluasi dan juga akan mengevaluasi node yang ditemukan. Kompleksitas waktu dan space berada dalam 3.3.
O01.
Ilill-climbing
Hill-climbing adalah perbaikan algoritma iteratif yang mirip dengan best-first search, kecuali teknik backtracking yang tidak di ijinkan. Pada setiap step pencarian, node tunggal akan dipiih untuk di ikuti. Kriteria bagi node yang diikuti adalah merupakan state terbaik pada state saat itu. Karena batasan pencarian ada pada node tunggal, algoritna ini juga mirip dengan beam-
search yang menggunakan beam-width satu. Masalah dalam algoritma ini adalah node terbaik di enumerasi secara lokal yang mungkin bukan merupakan node terbaik secara global, oleh karenanya algoritna ini hanya menemukan lokal optimum dan bukan global optimum
[
1].
Sddl4r*H
101
3.4. Beam Search Merupakan varian lain dari pencarian bestfirst adalah pencarian pada graph dengan melakukan ekspansi pada node yang paling menjanjikan (dengan f(n)) pada himpunan
yang terbatas. Beam search hanya akan menyimpan satu kandidat set node terbaik untuk di ekspansi dan membuang lainnya [11]. Hal ini membuat beam-search lebih efisien dalam penggunaan memori daripada greedy best-first, tetapi sangat sulit dalam membuang node yang dapat memberikan
path optimal. Cara kerja algoritma ini adalah dengan tetap melacak sejumlah state Dimulai dengan men-generat state ft secara random. Pada setiap langkah, semua suksesor dari semua state k di generate. Jika salah satunya adalah suatu goal state, maka
k.
algoritrna berhenti. Selain itu algoritma akan memilih lr suksesor yang terbaik dari list state dan mengulanginya lagi [2].
Jadi
beam-search merupakan modifikasi dari pencarian best-first dimana semua state fr kecuali yang terbaik, akan di buang setiap kali iterasi. Dengan demikian diperlukan
suatu threshold untuk membatasi fr state tersebut, yang di sebut dengan beam-o*idth. Jika beam-width : null, maka dilakukan best-first. Beam-search diimplementasikan oleh metode problem combiner. Metode ini memanggil metode selanjutnya untuk mendapatkan list state yang di hasilkan oleh best-first, lalu mengekstrak elemen pertama dari state lr [l]. 3.5. Optimasi
Gambar
t. Stot"
rffi pada hitl-clinbing
I terlihat bahwa terdapat lokal optimum dan global optimurn" Goal Pada gambar
seharusnya memaksimalkan fungsi, tetapi jika kita terlalu jauh ke kiri dan bekerja ke arah global maksimum kita akan terjebak pada hanya lokal optimum saja.
A* (A-Star)
Optimasi yang di masksud pada bagian ini adalah dengan memfokuskan pada fungsi cost yang di pakai pada pengurutan ekspansi path dan melakukan combine (merge) ekspansi ke dalam priority-queue. Efek dari step pertukaran dalam sortir ekspansi path dan merging perlu di hitung ulang dengan fungsi evaluasi heuristic, yaitu dengan membuat flrngsi evaluasi statis dengan merubah representasi dari path yang di evaluasi, Sehingga dengan demikian kita
Techno.COM, Yol. 10, No. 3, Agustts 201I: 98-107
dapat menyimpan cost dari traversal pada
path (g) dan total cost (h)
kesulitan.
IQ2
Hal ini
dimaksudkan untuk
secara
mendapatkan sebaran yang dapat di percaya
menyeluruh pada Fg+h seperti yang ditulis secara fungsional pada [13].
dan valid bagi tiap-tiap algoritma yang di simulasikan. Konfigurasi tingkat kesulitan di bagi atas mudah, menengah, sukar dan jelek (worst), yang mungkin tak terselesaikan. Kriteria tingkat kesulitan ini merupakan inisial state yang di disain sepertipadaTabel 1.
4.N-PU?.ZLE, Masalah N-Puzzle terdiri dari papan persegi yang mengandung N kotak persegi dan satu kotak kosong disebut "kosong". Operasi dasar setiap pergeseran kotak yang berdekatan dengan kotak kosong ke posisi kotak kosong tersebut. Tugas kita adalah untuk mengatur ulang kotak dari beberapa
Tabel No
adalah ukuran dari ruang pencarian yang
dihasilkan oleh rencana yang
di
buat. Selama lebih dari dua dekade, 8-Puzzle dan
ini
dapat lebih
menjelaskan
ffi l'lelsl 8-Puzzle
Gambar 2- N-Puzzle
Sedangkan representasi data dari gambar di atas dapat berupa list [1 2 3 4 1213 14 5 l1
6 10 9 8 7l dan fi 23 8 x4 7 6 5),
sebagai goal state yang di kehendaki.
Strt rkhir
Keterangrn :
di
katakan
mudah jika
jarak
maksimum antara , initial state dengan ,
(134862?x5)
,
goal state "pendek" lminlgy1ry1n) Masalah
,
2
,,
initial state
'1
i
+-+ ri il
3
di
katakan
mudah jika
maksimum
(28t x43765)
(1238x4765) : (281463x75)
antara dengan
Boal state "sedang'
-
goal state "panjang"
path) jKategori masalah, (maximum
"worst"'
I
(5674x8321)
,
antara; 'maksimum ; initial state dengan ,
4
,
jarak
.-9u"1e:ry91 , ;Masalah di katakan , mudah jika jarak: :
mudah
:
sebenamya
diselesaikan m
!oleh manusia" disini nl: di cari perbedaanm. penyelesaianoleh l i jmanusia dan mesin l akan
l
j
ri
Keterangan
rET;I
15
Awal '
|1
mengenai 8-prrzz[6.
X
State
tMasalah
I
l5-Puzzle telah digunakan untuk teknik pengujian pencarian, terutama karena kesederhanaan mereka manipulasi dan keterwakilan baik untuk kelas tertenhl dalam suatu masalah [3]. Gambar 2 di
bawah
Kriteria Tingkat Kesulitan State |-Puzzle
ii,
konfigurasi awal secara acak ke dalam konfigurasi tujuan tertentu yang dirancang, perencanaan klasik, termasuk pencarian heuristik, tampaknya tidak bisa, bahkan pada komputer sangat kuat, untuk memecahkan kasus masalah N-Puzzle yang lebih besar dari 99, alasan yang palingjelas
I
I:
:
Kolom nomer menunjukan unftan
kesulitan dari mudah, menengah, suknr dan
bun*
Pembahasan di fokuskan pada dominasi beberapa properti pada setiap algoritrna yang di uji sebagai berikut : 1. Jumlah ekspansi path. 2. Jumlah konstmksi memory baru 3. Jumlah pemanggilan fungsi 4. Kecepatan eksekusi fungsi 5. Kecepatan eksekusi fungsi setiap pemanggilan
6.
Besar kebutuhan memory
per
pemanggilan fungsi. 5.
IHSIL DAN PEMBAIIASAN
Eksperimen untuk mendapatkan langkah optimal dari serangkaian algoritna yang diujikan pada masalah 8-puzzle dilakukan dengan menentukan konfigurasi tingkat
Properti pertama di peroleh dari simulasi program, sedang properti 2 hingga 6 di generate dari profile report-time dalam cmu common lisp. Tabel di bawah ini merupakan hasil pengujian terhadap semua
Techno.COM, Vol. 10, No. 3, Agusttu 201 I:
I I f f
I II
I I
I I I I
I
II I
I I
I
,.,.;h-n.; Seperti
di tunjukan tabel 3, pada
98-107
103
i"'firu;,,1f$,'ffT:*lX'L1T*;; tingkat
batasan kedalaman). Exponential time pada
O(bo), tapi hanya berada
di O(bd) untuk
5n*'tr;'fr:i#"H-#,;'#:I;#H: f#*lii1""Tfr;,;11: J":}ffiil
:Lf:t
"J,jH1i.l}:'T;i1"ffi*iff
5#*"tffl"f"oo'*il"",ffi-iJ,""'fri. Eksponensial
waktu dan anak)
'';,f:;::;:l:,:::::";:;l::!la
kompleksitas
ilffi'a*E;'"ffit1*I*kffiil jumlah pada node. (misalnya,
T:l*"*'secarakronorogis rob't
setiap
nenth-tirs'l
'
ltta
';:;;,^us";;i;
llrrl'r=lFt.-# i:Hn-rT""*,ffitn""::Htr lsrx memilikianakb,memilikitotall+b+b2+ 'q'ottzg,stz ...+bd :
'_
. ' i_,_
o.:szaiaa
_
Sedang 16(d+rl pada kasus "buruk" (worst), algoritrna tidak 5.3. Best-first \ I
(b_l) node.
llffiL#",liffiTffif trY:H"#J:l + 10
i
Dari taber 5, uji simurasi pada tingkat "'-;"#:;
il:ffi,illTo'Ti"f,uo,f;o::r;"1;;;'.1 f;Tlffi*"'"1*',' kedalaman 12 memiliki 0 anah ada 1
r__ i
*l'fi
menyelesaikan simulasi, properti dari adalah, urutannodepadalist
+ 100+ 1000+...+ 1012:11013-1;/9= algorinnaini
tr,["?:",* #f-Hl:il*tr'ffiil ru,-'*n:.Titr#T$:il-:f*1'd node
node/detik
dan
masing-masing
daiarn beberapa cara.
Ini adalah cara umurn
Techno.COM, Vol. 10, No. 3, Agustns
untuk merujuk pada kelas dari metode informed search. Menggunakan fungsi evaluasi f(n):h(n), menaikan rnlai f untuk
201l: 98-/07
104
Tabel 7: Rata-rata uji simulasi algoritma Beansearch dengan beam-width:3 pada penyelesaian problem 8-Puzzle
mengurutkan node. Ekspansi node dengan nilai fungsi (fl yang terkecil.
'A B ,
Tabel 5: Rata-rata uji simulasi Best-frst dengan S(n):0, pada penyelesaian problem 8-Puzzle
;D
C
t O
D .E F i--.
1,437
*
O.OOtt : to i
Srr
2
o : 1,044,780 :.zter j+t
:srr
3
o i 1,019,249:3.0286 +s
isrK
.....i_
;4 0: i;
l
-_.r__ i_.-_....
329,041 r0.3751 i43iSTK
5.4. Hitt-climbing
Dari tabel 8,
simulasi pada tingkat kesulian "mudah" hingga "worst" dengan beam-width:1, algorinna ddak menemukan solusi, tetapi pada beam-width:3 algoritma ini dapat menyelesaikan semua simulasi dan menemukan solusi. Pada beam-
J.4. Beam-search
Dari tabel 6 dan7, uji simulasi pada tingkat kesulitan 'omudah" hingga "worst" tidak menemukan solusi, tetapi algoritma ini dapat menyelesaikan simulasi. Algoritma Beam-search dengan beam-width: 1 dan 3 lebih jelek dari pada algoritma depth-first karena dia akan masuk kedalam pada sisi kiri tree hingga ketemu leaf dan berhenti, backtracking pada algoritrna ini tidak
diijinkan. properti dari algoritrna ini adalah, menggunakan fungsi evaluasi
f(n)=h(n), dengan ukuran maksimum list node adalah k, hanya menangani & node yang terbaik sebagai kandidat untuk ekspansi dan mernbuang sisanya. Lebih efisien space daripada Greedy Best-First Search, mungkin tidak dapat menemukan solusi, sehingga tidak dapat diterima
widtF3 untuk kasus buruk
dapat
menyelesaikan dan menemukan solusi mungkin karena keburuntunan saja, karena goal state berada di local maxima. Tabel 8: Uji simulasi algoritma Hill-climbing dengan beam-width j pada penyelesaian problem 8Puzzle
B iA,t::i . 2M,o6B o.zz57 i 42' sR I 5,8 l2 -9--*-9--ji. : ------. 2 t0,i57 8e6,301 1.3480 41 sK
------_'_---l i
,
1
,
;
3
10,756 r 896,163
1.3280 42 r SK
,
4
6,383 533,352
0.5264 | 42: SK
'
i
i
5.4. A-Star
Dari tabel
9, uji simulasi pada tingkat
kesulitan "mudah" hingga "sukat'',
(admissible). Tabel 6: Rata-rata uji simulasi algoritma Beam-search dengan beam-width: I pada penye I es aian prob I em 8- Puzz I e
c ,.-li n ii r ii r iAiBt I I : i:ilt)
:
uji
i i
r'o : tt,eroio.ooz tzz istK'
2 10 i26,693 i 0-0022 I 8,898 STK 3
0
13,984
0.001r
32
STK
4
0
23,168
o.oonl
nt
STK
algoritma menemukan solusi, pada kasus "brn'k" (worst) mirip pada breadth-first, simulasi di hentikan. Solusi lebih baik dari algorinna sebelumnya, namun lmrang optimal. Dalam algoritma ini sudah di capai hasil yang lebi baik dari sebelumnya (lebih optimal), baik dari segi jumlah ekspansi path, waktu pengerjaan algoritrna maupun konstmksi memori yang dihasilkan. Algoritma ini memang merupakan algorima optimasi dari best-fust, dimana
Techno.COM, Vol. 10, No. 3, Agusttts 201I: 98-107
105
perluasan path ditinjau dan di batasi dengan
algoriftna untuk menemukan solusi pada
tungsi f(n):g(n)+h(n).
kasus buruk, pada A-star dan A-star-OPT, karena tidak di ijinkannya backtracking
Tabet 9: Rata-rata uii
similasi algoritma A-star
pada penyelesaian
iA B
'-
Pro
. D
C
I I 20 29,115 , 0.9614, -
z too 549,934 -------
i
I
3
i4
539
!3
E
F
untuk membayar cost Pada sPace dan kecepatannya, selain itu lebar level seiap path sangat panjang membutuhkan waktu yang lama dan harus di hentikan- Pada depth-first tidak ada solusi yang di temukarl di sebabkan path yang terlalu panjang mendalam dan terdapat cycle hingga leaf. Pada Tabel 11, akan di sajikan pencapain keseluruhan algoritma pada
1Q8 : SK
1,0.0314 16s iSK
11,655,378 0.6757 109 SK
o
kasus mudah hingga buruk.
5.5. A-Star Optimaasi
uji simulasi pada kasus "mudah" hingga "sukat'' algoritrna dapat Dari
menyelesaikan dengan baik, untuk ekspansi
path hasilnya sama dengan A-Star, tetapi dalam kompleksitas waktu dan space lebih
ungpl. Namun Pada kasus "burukn'
hasilnya tidak berbeda dengan A-Star yaitu dihentikan secara paksa pada saat running, di karenakan ada kecendenrngan ekspansi
Tabel I I: Overall algoritma Elcspansi, Rata'rata Space dan Time (E,S,T) pada penyelesaian problem 8-Pnzzle
:il'-ii;"..'.;.--; _ , Depth-first
; t i
Tabel I0: Rats-ratq uil similasi algoritma A-star
op4s!!!2941 pzltzlelslqry ugbkq rylz?te
A,B
C
I
i-;
s2,746
| 0.017s
953
0
Hill-climbing
5,8
l?,'107,036 0.7560 r Selesai
i
1
i
!!:11 1'991 i3"1, l2
A-Star
244,068 0.2257
Selesai
29,115 0.0014
Selesai
855 0.0006 Selesai A-Star optimasi 20 ! Breadth-first 575 | i07,U2 0.0050 Selesai ' Deprh-Grst 0 ' t:42:!!1.._1J911, c"e"l :- - - --_ -_---_ 2.62210: Selesai Best-fust 1,482 .087,fi0 __=__j _,] 26,693 3.2191 ; Cagal Beam-search -+-,
;
i
I
i
I
D
43 100 I
B€st-first Beam-search
T*t:;111
14,222 0.0000: Selesai 18,630 0.0000 Cagal
43
Breadth-first
path akan panjang dan waktunya lama, mirip pada breadth-first kasus "buruk".
.:-_.
' 92J$
iSK
t.l+gO 'l Selesai ,,i
I
i
I
'sK
,: !srs to.a0t,qst iz.toso 10,'108,981'sK =i o io.oooo o ,STK ,l; o
I A-staroptimasi
1
loo
I
5.5. Overall Algoritma
Kesslur-phan running algoritnoa dapat di
kaakan berhasil meryelesaikan semua problem yang di kategorikan (dari mudah hioggu sukar) dengan kecepatan yang sangat optimal. Sedangkan pada kasus *buruk' hauya satu algoritna yang dapat menemukan solusi dikarenakan diberikan pembatasan pada le-bar path menuju goal state, namun de-ngan cost yang sangat besar pada ekspansi pathnya, dan mungftin ini karerra kebetulan saja. Ketidakmampuan
0 0.0000 Gaeal 'l- Br€adth-lisl 0 ' ---_-----o rzs,st: Deprh-firsr i ' liri8,- cg! , BTLfrsL ' z,zt6' zJ.lg4lz l.l2l0 cagal i
Hill-climbing A-Star
:
I
Techno.COM, Vol. 10, No.
OverallAlgoritma
QtimasiWaktu
14.0000
i
12.0000
*
10.0000
s :
8.0000
:
6.0000
',
4.oooo
'
*,
t i** "
r
Buruk
"
Sukar
.
Sedang
*Mudah
2.0000 t i H-r-r
o.oooo
r r 1r
kam-search
Breadth-first A-Staroptimasi
Algoritma
Gambar 1 Grafik Overall Algoitma pada optimasi waktu Ovenll Aleoritma oel iriiaii Eli-iiiiii?ar
j,
Agustrls 20II:98-107
r06
Ditunjukan pula overall hasil uji simulasi dalam gambar grafik 1, 2 dan 3, yang di tinjau dari perspektik jumlah ekspansi path, space ftonstruksi memory) dan waktu tempuh (detik) dari setiap performa algoritma yang di uji. Pada algoritnna depthfint tidak nampak hasilnya karena solusi tidak pernah di temukan pada semua kategori. Semua performa algoritrna mengarah pada optimasi yang lebih baik, baik dari segi ekspansi pattU waktu tempuh dan konstnrksi memori. Pada perspektif expansi path hanya algoritma hill-climbing saja yang menunjukan hasil tidak optimal di banding dengan lairurya. Konstruksi memory paling banyak di hasilkan oleh algorimra best-first, optimasi hingga kasus sukar tetap berada dalam kendali algoritma a-star baik yang biasa maupun yang di optimasi. Begitu pula kebutuhan waktu yang terjelak di hasilkan oleh algoritma best-first. 6. SIMPUI.AN
tr
Penelitan dan pengujian terhadap algoritma
40,0@
35,0@ {'99 6 25'000 E 'E zo.ooo
I :,:
i
pencarian baik pada uninformed maupun heuristic memberikan pengetahuan baru
Buruk
sukar
rs,ooo ' -* < to.ooo I s-ooo, 'g1..,|.,{^.
bagr kita bahwa dalam
'sedds 'Mudah
intelligenco,
l--*
Bst-firsr A-Star optimNi Breadth-fi rst Hill-climbing
Ekspmsi
Gambar 2 Grafik Overall Algoitma pada ekspansi
path Overall Algoritma Optimasi Space : :
20,000,000
t
15,000,000 ii
!
a I a
I to,ooo,ooo ,r 5 ,' ',
> 5,000,000 I r*
o
r-l
I
!
o
^ Buruk Sukar
.sedang
r
Mudah
d
It.
Beam-sarch
Breadth-fir$ A-Str
optimasi
l
Gambar Grafik Overall Algoritma pada optimasi space
dan
kasus-kasus
menunjukan bahwa
konsep pencarian menjadi sentral metode yang selalu dikembangkan. Hasil uji simulasi pada pencarian solusi pada puzzle 8, memberikan beberapa kesimpulan menarik yang diantaranya adalah, performa algoritrna yang tidak memberikan solusi menghasilkan performa paling buruk (depth-fmt), sedangkan algoritrna best-first dan breadth-first merupakan algoritna yang terjelak yang dapat memberikan solusi dengan jumlah capaian waktu, space dan ekspansi terbesar. Untuk konstnrksi memori pada algorima hill-climbing memberikan hasil yang terbesar (tidak optimal), namun dapat memberikan solusi pada setiap kesukaran yang di berikan. Optimasi terjadi pada algorima a-star dan a-star-opt dengan hasil yang signifikan pada keduanya. Penelitiandan uji simulasi ini masih jauh
107
Techno.COM, lrol. 10, No. 3, Agt'tsttrs 201I: 98-107
belum dapat di selesaikan oleh mesin.
dari sempunn untuk menuju keinginan manusia dalam mengembangkan suatu perangkat pembantu yang cerdas yang
Kedepan, dengan memahami teknik pencarian dan oPtimasinYa akan membimbing kita pada penyelesaian yang lebih baik. Modifftasi pengkodean pada seluruh algoritrna yang di tinjao untuk dapat di jalankan oleh mesin pararel (pararel computing), akan menjadi kajian menarik guna mendapatkan hasil yang lebih maksimal dan optimal.
mungkin akan mengantikan manusia (kasus deep blue yang mengalahakan Kasparov dalam perrnainan catur, merupakan revolusi yang spektakuler dalam dunia komputasi)'
Bagaimanapun
masih terdaPat
slsl
manusiawi yang lebih menonjol yang dapat menyelesaikan kasus-kasus yang mungkin
Problem Solving", Addison WesleY Longman, Inc. USA, 1998.
DAFTAR PUSTAKA
[1]
of futificial Intelligence Programming: Case Studies in Common LisP", Morgan
Peter Norvig,"Paradigms
E. Korf, "DePth-First Iterative-DeePening: An OPtimal Admissible Tree Search ", Artificial
[9] Richard
Kaufinann,1992
Intelligence, CiteSeerX, 1 985
Norvig, [2] - - Stuart Russell and Peter "6ttift"iul Intelligence: A Modern
"Artificial
l10l------
Approach (3rd)", Prentice Hall, 2010
Intelligence Search Algorithms", Artificial Intelligence, CiteSeerX,
Harold Abelson, Gerald Jay Sussman,
r996
[3]
Julie Sussman, "structure and interpretation of computer programs
Tim Jones, "Artificial ntelligence : A Systems Approach ", Copl'right by Infinity Science Press LLC India,
tlllM
",
MIT Press, 1985
[4] Knuth, Donald E., "The Art Of ComPuter Programming Vol l' 3rd ed.", Boston: Addison-WesleY, 1 997'
[5] Pearl, J.
2008.
Todd [12] Zdravko Markov, Ingrid Russell,
Neller, and Neli
"Pedagogical Possibilities
,
"Heuristics: Intelligent for ComPuter Strategies Search Addison-WesleY, Problem Solving", Christopher Thornton
Boulay
,
, Benedict
du
"Artificial lntelligence
:
Strategies, Applications, and Models
t7]
Through Search", Second Edition , AMACOM, 1998. V.J. Rayward-Smith, I. H' Osman' C' R. Reeves and G. D. Smith (Editor)' "Modem Heuristicsearch Methods ", John WileY & Sons Ltd England, 1996.
[8] George
F. Luger, William A'
Stubblefield" "Artificial Intelligence : Structures and Strategies for Complex
for the N-
Puzzle Problem ",36th ASEE/IEEE Frontiers in Education Conference, October 28-31,2006, San Diego, CA
1984.
[6]
Zlatarcva,
[ 1 3]
http://www.kantz.com/jasorVwriting/8puzzl9.h.tnq, diakses 10-01-2009, 14'28
WIB
[14]Alexis Drogoul and
Christophe Dubreuil , "A Distributed Approach To N-Puzzle Solving CiteSeerX,
",
1993
