I v
\
sn*KcdPATtEGARA
MAr-ASSAR
..ffi"!ka
umu Kan,sn sdhi*H;"$;9"1x"'i" rnffir(
KNffiK ffi@fl4
KONFERENSI NASIONAL SISIEM INFORMASI2AtA
Dfibffi@&a gafifiA. tem lnformasi 2OL4
Konfere
ds STIVIIK Dipane
ffipffi
PEilI
ari - O1 Maret 2AL1
@de ARA
Penerapan Visualisasi Algoritma BFS dan A-Star Mengfgfunakan Library Pathfinding.js Pada Kegiatan Perkuliahan
Komferensi Nasional Sistem Informasi2014, STMIK Dipanegara Makassar 27 Pebruari
- tMaret2014
KNSI2014-10 PE,NERAPAN VISUALISASI ALGORITMA BFS DAN A.STAR
MENGGT]NAKAN LIBRARY PATHFINDING.JS PADA KEGIATAN PERKULIAHAN R. Sandhika Galih A.
Teknik Informatika, Fakultas Teknik, Universitas Pasundan Bandung Jl. Dr. Setiabudhi No. 193, Bandung. Tetp (022) 2021440 Email : sandhikauaiih@Lurpas. ac.id
Abstrak
Teknologi visualisasi algoritma (VA) dibuat dengan tujuan untuk membantu para mahasiswa di bidang
-
informatika untuk memahami bagaimata cara kerja dari sebuah algoritma dalam pemrograman. Berdasarkan pengalaman selama memberikan materi mengenai dua algoritma tersebut, diketahui bahwa kebanyakan mahasiswa merasa bingung mengenai carakerja dan implementasi dari algoritma-algoritma ini. Untuk ituperlu dibuatkan visualisasi dari algoritma penelusuran ini dengan harapan agar mahasiswa dapat lebih mengerti dan memahami bagaimana cara kerja dari algoritrna jika disajikan secara visual dengan lebih menarik dan interaktif. Pada penelitian ini dibangun sebuah visualisasi algoritma penelusuran graf dengan menggunakan pathfindingjs sebagai library yang diimplementasikannya kedalam sebuah aplikasi dengan tema penelusuran jalinkeluar pada labirin. Penelitian ini dilakukan dengan fokus untuk mengukur aplikasi VA yang dibuat terhadap pemahamam mahasiswa terkait dengan materi penelusuran graf khususnya algoritma penelusuran Breadth-Firsi Search dan A*. Untuk mengetahui apakah VA ini sudah dapat memberikan pemahaman materi kepada mahasiswa, dilakukan pengujian terhadap aplikasi oleh beberapa orang mahasiswa sebagai partisipan dengan cara memberikan pertanyaan terkait dengan algoritrna penelusuran sebelum dan sesudatr m"rrgg.,nukan aplikasi yang dibuat. Kata kunci : visualisasi algoritma, breadth-first search, Ax, pathfindingjs.
1. PENDAHULUAN Teknologi visualisasi algoritma (VA)
dibuat dengan tujuan untuk men.rbantu para mahasiswa di bidang informatika untuk memahami bagaimana cara kerja dari sebuah algoritma dalam
pemrograman.
[]
Sejak tiga puluh tahun terakhir, evolusi dari teknologi VA sudah berusaha unhrk memperkaya pendidikan informatika dari berbagai
kapasitas. sebagai contoh, teknologi
VA
sudah
digunakan untuk:
1.
Membantu pengajar untuk mengilustrasikan operasi algoritmik di dalam kuliah.[2]
2. Membantu
mahasiswa untuk memahami dasar-
dasar algoritma pada kuliah
di
infonnatika.[3]
3.
Membantu mahasiswa untuk mempelajari operasi-operasi dasar dari tipe data abstrak yang
dipelajari pada kuliah di informatika.[4]
2 (dua) diantaranya adalah
yang dapat digunakan,
algoritma BFS (Breadth-First Search) dan Ax (AStar). Kedua algoritma ini memiliki perbedaan dan ke-khas-an tersendiri dalam melakukan penelusuran terhadap sebuah graf.
Berdasarkan pengalaman selama memberikan materi mengenai dua algoritma tersebut, diketahui bahwa kebanyakan mahasiswa merasa bingung
mengenai cara kerja dan implementasi dan algoritma-algoritma ini. Unfuk itu perlu dibuatkan visualisasi dari algoritma penelusuran ini dengan harapan agar mahasiswa dapat lebih mengerti dan memahami bagaimana carake4a dari algoritma jika disajikan secara visual dengan lebih menarik dan interaktif.
Pathfindingjs adalah sebuah library javascript menyediakan kumpulan kode hasil implementasi dari algoritma-algoritma penelusuran graf sehingga
Salah satu algoritrna yang selalu dibahas di dunia informatika khususnya di bidang kecerdasan buatan adalah algoritma penelusuran graf, dimana didalamnya terdapat banyak teknik penelusuran
KNSI 2014
kita dapat dengan mudah menggunakannya untuk aplikasi-aplikasi
yang
membutuhkannya seperti
game atat aplikasi berbasis web.
Pada penelitian
ini
dibangun sebuah visualisasi
50
Komferensi Nasional Sistem Informasi20T4,STMIK Dipanegara Makassar 27 Pebruari
algoritma penelusuran graf dengan menggunakan pathfindingjs sebagai library yang diimplementasikannya kedalam sebuah aplikasi dengan tema penelusuran jalan keluar pada labirin. Penelitian ini dilakukan dengan fokus untuk
mengukur aplikasi
VA yang dibuat
misalnya dimulai dari simpul /node v.
b) Kunjungi simpul v, bila simpul yang dicari ditemukan, maka pencarian selesai dan
c)
terhadap
pemahamam mahasiswa terl
kembalikan hasilnya.
Bila tidak ditemukan, kunjungi semuasimpul yang bertetangga dengan v, bilq tidak ditemukan
juga, cari lagi di simpul yang
belum dikunjungi yang bertetangga dengan simpul yang dikunjungi
apakah VA ini sudah dapat memberikan pemahaman materi kepada mahasiswa, diiakukan pengujian
sebeluntnya.
d) Begitu seterusnya sampai pencarian selesai
terhadap aplikasi oleh beberapa orang mahasiswa seba_eai panisipan dengan cara memberikan
(pencarian berhasil atau
tidak
ciitenrukon).181
pertanyaan terkait dengan algoritma penelusuran sebelum dan sesudah menggunakan aplikasi yang
Gambar 1. dibawah ini menunjukan urutan simpul yang dikunjungi jika ditelusuri
dibuat.
menggunakan algoritrna Breadth-First Search.
Sistematika penulisan pada paper. ini diawali dengan pendahuluan yang berisi latar belakang penelitian, lalu tinjauan pustaka yang menjelaskan mengenai teori-teori dan sfudi pustaka yang sudah dilakukan pada penelitian ini sepetti teori mengenai
visualisasi algoritma, penelusuran graph,
- LMaretZ0l4
dan
pathfindingjs. Bagian selanjutnya adalah metodologi penelitian mengenai metode dan langkah_ langkah yang digunakan dalam penelitian ini, dilanjutkan dengan hasil dan pembahasan yang mencakup pengujian yang dilakukan terhadap VA
yang membahas
Gambar l. Urutan penelusuan simpul pada BFS
yang telah dibuat.
Jika kita anggap simpul akhir atau simpul yang dicari adalah simpul nomor 7 makaurutan pencarian jika menggunakan algoritrna Breadth-
2.TINJAUAN PUSTAKA Penelusuran Graplt Penelusuran graf
/
First Search adalah l-2-34-5-6-7. Meskipun algoritrna Bread&-First Search
graph traversal merupakan
saiah satr.i teknik penyeiesaian masalah dengan / problem solving by searching dimana dengan teknik ini, sebuah agen cerdas / intelligent agent akan memufuskan apa yang akan dilakukan
kelihatannya bagus untuk mencari sofusi,
pencadan
namun
Saat sebuah solusi ditemukan,
Breadth-First Search diterapkan pada graf statis, yaitu graf yang sudah tersedia (dibentuk terlebih dahulu) sebelum pencarian solusi. Algortima pencarian menggunakan BFS dapat ditulis sebagai berikut
:
a) Penelusuran akan dilakukan pada suatugraf,
KNSI 2014
simpul buah baru. Simpul akar akan pada level ke-l, masing-masing simpul membangkitkan b buah membangkitkan simpul
simpul, total seluruhnya b2pada level ke-2.Tiap-
tiap
simpul ini akan membangkitkan b buah simpul baru pada level ke-3, total ada b3 buah simpul. Misalkan solusi ditemukan pada level ke-d, maka jumlah malsimum seluruh simpul
akan
mengunjungi / traverse simpul-simpul graf. Algoritma traversal adalah mengunjungi simpulsimpul dengan cara yang sistematik. Algoritma
algoritrnanya
Untuk menjelaskan hal ini,
misalkan setiap simpul dapat membangkitkan b
dengan cara menelusuri unrtan aksi yang berujr.rng pada sebuah keadaan / state tertentu. proses penelusuran urutan aksi tersebut disebut dengan pencarian / searching. Sebuah algoritma pencarian mengambil masalah sebagai input dan mengembalikan solusi dalam bentuk urutan aksi. direkomendasikan aksi apa yang harus dilakukan untuk mencapai solusi tersebut. [7] 1) BFS (Breadth First Search) Banyak persoalan yang dapat direpresentasikan dengan graf. Pencarian solusi dilakukan dengan
kompleksitas
keksponensial.
yang dibangkitkan adalah
I +b +b2+b3 +... +bd= oo+ t
2)
_
l)/(b _ 1)
A* Algoritma A* (dibaca: A Star), adalah algoritma penelusuran graf yatg merupakan A-Star /
pengembang an dari algorihna Best-First Search,
yang dimana didalamnya terdapat fungsi heuristic yang membantu membuat penelusuran menjadi lebih efektif. Pada saat algoritma A* ini menelusuri graf jalur yang dilalui adalah jalur yang memiliki
53
Komferensi Nasional Sistem
2014, STMIK
ntlai / biaya yang paling rendah, dengan cara menyimpan urutan prioritas jalur alternatif pada antrian / queue. Jika ditemukan biaya dari jalur yang sedang ditelusuri lebih besar dari biaya
jalur
altemative, maka jalur yarrg sedang ditempuh akan diabaikan, dan penelusuran berpindah ke jalur yang memiliki biaya yang
lebih kecil. Notasi yang dipakai pada aigoritrna
A* ini
adalah:
f(n):g(n)+h(n) Perbedaan cara kerja algoritma
A* dengan BFS al:,lah ailanr': lun,esi heuristik (h(n)). fltnssi :eu:i::t; ac,alah sebuah nijai perkiraan deng"an menghirung biaya i jarak terkecil sebuah state
anegara Makassar 27 Pebruari
-
lMaretZOLA
Visualisasi Algoritma
Visualisasi algoritma (VA) adalah
sebuah
metode yang dibuat dengan tujuan untuk membantu para mahasiswa di bidang informatika untuk
memahami bagaimana cara algoritma
dalam
ke{a dari sebuah
pemrograman.
Menurut Hundhausen (2002) [1], ada beberapa skenario penggunaan VA dalam dunia pendidikan, .gambar 3 dibawah ini menunjukkan skema penggunaan VA dalam dunia pendidikan;
.SEr,ira!':i{i
apabila ingin mencapai goal state.
iqri.*ii..tjatt
\rl
Pathfindingjs
Pathfindingjs adalah sebuah library javascript yang dibuat untuk membantu pengemburrg
gu*. dalam mengimplementasi penelusuran graf. _ ._
Library
ini
dapat berjalan pada server nodejs
Gambar 3. Skenario penggunaan VA di dunia
ataupun dengan menggunakan web browser. Di
dalam library ini sudah terdapat Y
pendidikan
beberapa
implementasi algoritma penelusuran seperti Breadth_ First Search, Best-First Search, A*, Djiksra dan
a. Kuliah, pada kegiatan perkuliahan di kelas, pada umumnya dosen program studi
tgrdaflJ juga properli Bi-directional search yang dapat kita gunakan untuk tiap-tiap algoritma.
fibra{
alamat
berikut
informatika menggunakan representasi grafik atau gambar untuk membantu mahasiswa memahami aspek-aspek yang ada di dalam algoritma. VA dalam perkuliahan pada dasarnya
ini memiliki lisensi MIT dan dipat diunduh pada
website
github
https ;//github. com/qi ao,/p athFinding j s. (terakhir di_ akses pada tanggal 29 Agusrus 2013j.
adalab, penghubung antara tulisan yang ada di
papan hrlis atau di slide kuliah. 3.
METODE PENELITIAN Benlut acialah metodologi ).ang digunakair
dalam penelitian ini:
:itudt Fuets,kfit VfsusL*a*i A!Eiri:ifi rt*
W Eksperimen
Gambar 2. Metodologi penelitian
Kegiatan pertama yang dilakukan adalah mempelajari literarur dan penelitian_per.relitian terdahulu terkait dengan VA, lalu setelah itu dibuat aplikasi VA dengan menggunakan library pathfindingjs dan setelah itu dilakukan eksperirnen untuk mengetahui bagaimana hasil penerapan VA p?du kegiatan perkuliahan Intelejensia Buatan khususnya matcri tentang BFS dan A;.
KNSI 2014
b. Belajar, mahasiswa informatika
yang
mengambil mata kuliah algoritma memiliki
waktu belajar untuk ujiau kapanpu mereka mau. Mahasiswa dapat membuat sendiri VA dengan cara melihat dan mempelaj an catatan atau, literatur kuliah yang mereka miliki.
c.
Tugas, mahasiswa menge{akan tugas kuliah
yang diberikan diluar waktu kuliah
mengumpulkanaya
pada waktu
dan yang
telahditentukan. Tugas yang diberikan dapatluga berupa pembuatan VA oleh mahasiswi seiara berkelompok. d. Diskusi, setelah menyelesaikan tugas yang
diberikan dengan membuat sendiri VA, VA yang telah mereka buat tersebut sebagai bahan untuk mahasiswa bisa menggunakan
berdiskusi dengan teman-temannya atau dengan dosen pengaj ar mata kuliah.
:
Praktikum, AV juga dapat digunakan pada
kegiatan
praktikum untuk
memberikan
garrharan secara interallif bagaimana cara keqa
sebuah algoritma dengan panduan
asisten
praktikum.
f. Ujian, didalam ujian, AV bisa digunakan sebagai alat bantu untuk memberikan pefianyaan. Soal yang diberikan tidak lagi
54
rr:riferensi Nasional Sistem Informasi2074, STMiK Dipanegara Makassar 27 Pebruari darzm bentuk kertas, melainkan dalam benfuk
iekri
fi
tas Visual isasi Algor:itrna
"A Meta Study of Algorithm Visualization System" yang dilakukan oleh Hundhausen [1], telah dilakukan sebanyak 24 eksperimen untuk rnengukur efektivitas dari berbagai macam VA. Hundhausen mengkategotikan Pada penelitian
ha-sil dari eksperimen tersebur ke dalam 3 (riga) grup Epis:enic Fideliw. Dual-Coding, dan
t::n r
,
LL-\..
--:--: -..-
-,--,-:,_.
i r Epistemic Fidelin' Epistemic
Cognitive Constructivism karena dirasa
cocok
mahasiswa karena pada metode ini mahasiswa dituntut untuk berperan aktif dan terlibat untuk
tidak hanya melihat dosen atau instruktur yarrg
menggunakan visualisasi
dan
n.rendengar
memberikan penjelasan.
Aplikasi Visualisasi Algoritma Aplikasi VA dibuat dengan memanfaatkan library pathfinding.js sebagai library penelusuran graf. Benkut ini adalah tampilan dari aplikasi VA yang telah dibuat:
Fidelity merupakan
teori
s;,
pengetahuan dimana diasumsikan bahwa setiap manusia di dalam kepalanya menyimpan modelmodel simbolis dari segala sesuatu yang ada di dunia, dan model-model tersebut menjadi dasar untuk melakukan aksi dan penalaran. Kunci asumsi dari Epistemic Fidelity ini adalah bahwa elemen grafis memiliki kemampuan yang sangat baik dalam hal
Y
Maret 2014
untuk diterapkan dalam kegiatan perkuliahan untuk memberikan pemahaman kepada
Yisualisasi dan animasi. E
1
menggambarkan model pemikiran algoritma dari seorang ahlisehingga akhirnya dapat disampaikan dengan baik kepada penggunanya. [10]
ji
ffi:M {@
ffi
ffi:ffru"-\i_j s"iW
ffp*f\ .*.J\ {#*= :". -l*f #'t
2) Dual Coding Dalam dunia psikologi ptoses encode adalah proses
mengkonversi sinyal pada syaraf kepada sebuah
bentuk yang dapat diterima oleh otak.Menurut penelitian Mayer dan Anderson [11], dikatakan
bahwa pengetahuan secara umum terdiri dari dua buah sistem simbolis yang saling terhubung satu sama lern tetaoi secara fungsional dapat berditi sendin. Salah sarunya mengkonversi sinyal verbal (perkataan), yang lainnya mengkonversi sinyal non-verbal (gambar). Sebuah visualisasi yallg menggabungkan kedua proses encode ini dapat mambangun representasi yang lebih baik pada saat
Gamba:' 4.
Berikut
Daripada menganggap bahwa pengetahuan adalah dari simbol atau objek-objek pada dunia nyata yang disimpan manusia di dalam kepalanya, Cognitive Constructivism menegaskan bahwa tidak ada pengetahualt yang mutlak yang
sebuah representasi
bisa secaralangsung merepresentasikan simbolsimbol. Melainkan bahwa seseorang itu selalu membangun pengetahuan mereka sendiri seiring dengan pengalaman subjektif mereka yang selalu bertambah pada saat berinteraksi dengan dunia. Dengan menjadi aktif terlibat dengan lingkungan
\
1f:\
t&J
Aplikasi VA menggunakan pathfindingjs
ini
adalah keterangan dari Gambar
4.
Diatas:
1. Grid berwama putih adalah kanvas
pada
aplikasi
2. Grid berwama hijau tua adalah
state awal
(initial state) penelusuran
disampaikan kepada penggunanya.
3) Cognitive Constructivism
{n} P&J'
*ssq{irrq8xsn&
3.
Grid berwarna merah adalah state akhir (goal state) penelusuran
4.
Grid ber.wama hijau muda adalah state-state yang sudah ditelusuri tetapi tidak mengarah pada goal state
5.
Grid berwama biru muda dan garis berwama kuning adalah jalur penelusuran optimal Panel pemilihan algoritma Tombol aksi
6. 7. 8. Keterangan penggunaan aplikasi 9. Properti hasil penelusuran
(panjang jalur penclusuran, waktu penelusuran, jurnlah operasi yang dilakukan)
sekitamya, seseorang dapat membangun pemahaman
baru dengan cara menginterpretasikan pengalaman baru kedalam sesuatu yang sudah mereka ketahui. [5] Setelah membandingan ke tiga gmp VA yang ada, pada penelitian ini dipilih merode
KNSI 2014
4.
EKSPERIMEN
Pada penelitian ini dilakukan eksperimen untuk menentukan sejauh mana aplikasi VA dapat
55
i.:':nfe:-ensi Nasional Sistem Informasi 2014, STMIK Dipanegara Makassar 27 Pebruari
:.:,:.:-:.. :;maharlan mahasiswa terhadap :.:-.-::: :;i:elusuran graf dengan menggunakan :-_:-::=f, BFS
dan
dilihat pada Gambar 5 dibawah ini:
A*.
s
F-rr-nenmen dilak-ukan kepada 10 (sepuluh) --:ii-r:: mahasisu'a sebagai partisipan dengan cara :3rlaxra-rama menjelaskan terlebih dahulu materi
r
rn3ngenai Breadth-First Search dan A>* menssunakan slide presentasi tekshral, lalu setelah itu mahasis*.a diberikan 1 buah soai mengenai terkait dengan materi -vans sudah dijelaskan
tadi,
F
,f
Y
lr
d
6
rfl
$
s
jika
:::hasisrta tidak bisa menjatvab soal lalu :.-:s-s'i: :3:s:l-I i-har.rskal unntk menggunakan ",::! i:,.r cil:at s:ianta klrang 1eb'ti '-:-*i-.- i',r
Gambar'5. Soal penelusuran graf
Pertanyaan yang diberikan untuk soal pada
-:.tJ5 merur dengan skenario rertentu dan terlebih dahulu drjelaskan bagaimarla cara menggunakan
gambar diatas adalah: "Diketahui sebuah
aplikasi tersebut.
diketahui initial state-nya adalah s dan goal state-
Setelah
selesai
menggunakan aptikasi,
mahasiswa tersebut kembali diberikan soal yang
tidak bisa dia jawab tadi. Apabila mahasiswa tersebut dapat menjawab soai yang diberikan, maka dapat disimpulkan bahwa aplikasi VA yang telah dibuat dapat memberikan pemahaman yang lebih baik daripada pemberian materi menggunakan slide
v
- 1 Maret 2014
presentasi yang biasa dilakukan.
labirin sedethana seperti pada
gambar,
nya adalah g. Tentukan urutan state pada labirin jika ditelusuri menggunakan algoritma Breadth-First Search dan A*".
Setelah didapatkan jawaban dari mahasiswa, dipilih kembali mahasiswa yang salah dalam menjawab soal untuk menjadi partisipan eksperimen tahap 2. Mahasiswa yang menjawab soal
dengan benar tidak diikutsertakan
pada
eksperimen tahap 2.
Analisis Partisipan
Mahasiswa yang dipilih sebagai parlisipan untuk penelitian ini adalah mahasiswa yang sedang mengambil mata kuliah Intelejensia Buatan pada
semester pendek tahun ajaran 2012/2013 di Universitas Pasundan Bandung. Mahasiswa yang dipilih memiliki kriteria sebagai bedkut:
1. Sebelurnn,va sudah memiliki
2.
pengetahuan tentang teori graf (sudali pemah mengambil mata kuliah intelejensia buatan) Tidak paham tentang teori BFS dan A+
Skenario Eksperimen
Berikut adalah skenario dari eksperimen
2)
Tahap 2
Setelah didapatkan mahasiswa / parlisipan yang tidak dapat mengerjakan atau salah dalam mengerjakan soal yang diberikan, partisipan
tersebut kemudian diharuskan untuk aplikasi VA dengan skenario teftentu selama 30-45 menit. Sebelum r.r.renggur.rakan aplikasi, dosen rnemberikan n.renggunakan
instruksi mengenai cara penggunaan aptikasi, cara
memilih lgoritma penelusuran dan bagaimana nrembuat sendiri labirin untuk ditelusuri,
bagaimana menentukan initial state, goal state, dan penghaiang / pembatas padalabirin yang dibuat.
yang dilakukan pada penelitian ini:
1) Tahap
3) 1
(sepuluh) mahasiswa partisipan dikumpulkan dalam kelas lalu diberikan materi
Peftama-tama, 10
mengenai teori penelusuran graf khususnya algoritma Breadth-First Search dan A* selama kurang lebih 30 menit menggunakan teknik pemberian mateti secara lisan dengan bantuan slide presentasi, materi yang diberikan seputar tujuan, cara kerja, dan urutan state yang ditelusuri untuk mencapai goal pada kedua algoritma pencarian tersebut.
Setelah itu,
seluruh partisipan
diberikan soal terkait dengan algoritma Breadth-First Search dan A*, dimana partisipan dirninta untuk menelusuri urutan state pencarian untuk
initial state clan goal state-nya, soal yang diberikan dapat sebuah kasus dengan diketahui
KNSI 20L4
Tahap
3
Setelah
mahasiswa
/
partisipan selesai
menggunakan aplikasi dan sudah dapat membuat sendiri labirin serta menelusuri labirin tersebut menggunakan
kedua
algoritma
Dilakukan kembali pengujian seperti pada tahap 1, partisipan diberi lagi soal yang sama seperti sebelumnya
dan diminta untuk mengerjakannya
kembali Skenario Penggunaan Aplikasi
Sebelum melakukan eksperimen tahap
2,
partisipan diberikan instruksi terlebih dahulu tentang bagaimana rnenggunakan aplikasi VA yang telah
dibuat. Berikut
ini
adalah instruksi-instruksi yang
diberikan:
56
"--
.-.-.
l,=_.,_::. Sisrem Informasi2014,STMIK Di
.: --1--:. :--::.:-,:- .rl ::fmUka aplikaSi VA, :::: :-::,: ::-:::::iukan initial State, goal :-.. ::_-- ;::rnbuat penghalang untuk
.
':----:
.-J--:,:ne:enCarian.
l
srr:ksi :ren_genai lanckah-lanskah
pembuatan
: I :-,'-
.'.-..-
:.:.:1 ;::.g::1 rteli.tet
r ang di-rlnkan.
\Iempelalari properti hasil
penelusuran pada ketiga
tiap-tiap
labirin yang
telali
Mempelajari ur.utan state yang ditelusuri dengan cara melihat animasi pada aplikasi.
8. Melakukan penelusuran menggunakan algoritma BFS dan
A* pada setiap labirin
yang
telah dibuat.
Gambar
I
1:lr{^l^o^c-r-i{"h-o
s-h^tro'E
drhll.l r;o;r"id
,
{r } ' 0 -:-r.:1 i- h^ n s" Lirlrk^u^rt-e ailihi!ll;{,{{nt+L1io -x{,
}??
L1
tit
r:::::::i
{-i:Ft^r.l'q
?
s-llhr:-Lqr+,r^rt-6.s
1) Hasil Tahap
1
Eksperimen tahap 1 ini untuk mengetahui mahasiswa mana saja yang memang masih
belum tlerlaharni materi terkait dengan algoritrla penelusuran BFS dan Ax. Jawaban yang benar dari soal yang diberikan adalah sebagai
dibuat. 7.
Skor
rit
.:
mengetahui
il ditelusuri).
g::tti.r 6
.{
i.lisi$ls i
JxrrthrnSorl
i:b+-l{t-r-r-a{^b^z I r-J:hiilkrri";lUll:ht:i.!rr s"lih+-k.o^r:r-*l.h"il"r-n,n,r s'
i
?rrrsiun;'
s-::sil'rkasr pencarian (u,aktu pencarian, urutan _'a1ur oencarian, dan jumlah state yane sudah
-
lrrt;sipr f
Jar.abtrn Sq;rl BFS
- tMaret2074
l:a
I:-s:::kst mengenai menu untuk
Ir
\o,
rariisiparr
f,rr!,,r,is
l)nrtsipih:i
-:-.::--:t rt;ngenai Bagaimana cara memilih
I :rha-r
Makassar 27 Pebruari
belikut:
Tabel 1. Kunci Jawaban pertanyaan
Jtunbarr So*l tll$i
J*rratianSual A*
F f'-h- n- h-r.I-c-r-a-t-b-s alau
"-h-k -l'-ir-q*'t-g
s-h-t L-p-c-q-a-r-b-1.::
Jawaban dari tiap-tiap mahasiswa
6 dan 7 berikut ini
menunjukkan salah satu labirin yang dibuat beserta hasil penelusuran menggunakan algoritma BFS dan A*:
ffi ffi
setelah diberikan soal adalah
sebagai
berikut: Tabel 2. Jawaban mahasiswa P*rtisilritr i*o,
Jlw{hxh.ionl
tr)*usrour il
s^f-i.p^l-s-r.r-i j-b-s r"i:l!IJ"k.q-e-r-r.t-Lrs
li:rti:i:
r ^ll-
$
r-{:
L-ir-Lri-<-:-u -5.x
.r::
l
|)llsiFiu ![
l-i rt't,
BFS
r-a-1
"
.h-X^L9'r1.a'!q
b,l <.I"1"1:l-q'r, lo
* [+I*l-g
3-[h.p-L-q,c-r-{.1.4-s
s -lt -li
s-I:h*r-t-c-c-r-a+*i^r
*'h-i-f r'(.
s-l':lFp-l-q-r-r-lt-$c
W :.
i,l
,
:-
:
!q
i.,.1
I lnl mahasiswa yang
mengerjakan soal, hanya 3 yang berhasil menjawab dengan sempuma. Aftinya, yang akan ikut serta dalam ekperimen tahap Z ada 7 orung. 2) Hasil Tahap 2
Setelah diketahui bahwa ada 7 (tujuh) tidak dapat menjawab kedua pertanyaan dengan benar, maka mahasiswa_ mahasiswa tersebutlah yang dapat mengikuti eksperin.ren tahap 2. Pada eksperimen tahap 2 ini mahasiswa yar,g
mahasiswa yang
t:
r^
s-h,ii1I.(.!!g
Hasil dari eksperimen tahap didapatkaii bahiva dari l0 orang Gambar 6. Penelusuran dengan algoritma BFS
Skor
s^h.l-f p-{"rj.!
tidak berhasil mengerjakan
soal
dipersilahkan untuk menggunakan aplikasi VA yang telah dibuat berdasarkan scenar-io eksperimen yang sudah drjelaskan sebelumnya.
3) Hasil Tahap 3 Gambar 7. Penelusuran dengan algoritma
5.
A*
Setelah selesai menggunakan aplikasi selama waktu yang telah ditentukan dan mahasiswa sudah berliasil nTelakukan instruksi yang diperintahkan, rnahasiswa kemudian diberikan
HASIL DAN PEMBAIIASAN
Berikut ini adalah hasil dari ekperimen yang
sama dengan sebelumnya. Berikut dari eksperimen tahap 3:
lagi soal yang ini adalah hasil
telah dilak-ukan:
KNSI 2014
57
!
t
\asional Sistem Inform
6.
KESIMPI]LAN
Kesimpulan
dari penelitian ini
2014,STMIK Di
[11] adalah dapat
behwa visualisa-si algoritma digurakan untuk membatu mahasisia
dnlrm
asi
meningkatkaa pemahaman dari sebuah
negara Makassar 27 pebruari
- lMaret2014
R. E. Mayer & R. B. Anderson (1991). Animationsneed narrations: an experimental test
ofadual-coding hypothesis. Journam of
Educational, psychology g3.
alguitma yang diberikan, walaupun dalam
penelitian ini sngat
sederhaaa
lingkupnya
dan
masih
pengukurannya pun
dilalnrkan kepada sampel yang relatif sedikit.
Untuk kedepanaya perlu
dilakukan
penelitian lanjutan dengan menambah algoritma lrnelusuran seperti Depth-First Search (DFS),
!es*-I* Selain
S€arch,
Djiksra rtan yang
lair::eya.
ou*r'*drrukokuo a.tt; / partisipan yang teLin
menggunakan sampel banyak lagi.
Pathfindingjs merupakan alat bantu yang sangat cocok untuk digunakan dalam
pembuatan visualisasi algoritma penelusuran graf berbasis web. Dengan dukungan aigoriima
penelusuran yang cukup lengkap membuat library ini cocok untuk pembuatan visualisasi algoritma.
DAFTARPUSTAKA t1l
C.
D
Hundhausen (2002).
A Meta study of
Algorithm Vsualization Effectiveness. Jou.r*l of
Visual Languages and Computing
13.
L2l M. H. Brown ( I988). Algorithnr Anirnarion. The MIT Press. Caurbridge, MA.
i3l t4)
tsl
P. Gloor (1998). Sol.i,vare Visualization: progran.r_
Ti"q 1. Multimedia Experience. The lv1lT"press, Cambridge, MA T. Naps (1990). Algorithm visualization in computer science laboratories. proceedings of tne ifsi SIGCSE Technical Symposium on Conrputer Science Education. ACM press, New york. L.B. Resnick (1989). Knowing, Leaming and Instruction: Essays in Honor of Robert 6laser.
Hillsdale, NJ.
t6l
Powell, K., & Katina, C. (2009). Cognitive and social constructivism: Developing tJols for an
effective classroollt. Education.
lll
S. J. Russel, P. Norvig (2003). Afiificial Intelligence: A N{odem Approach, Second Edition.
Prentice Hall. NJ.
i8l
A. Ramdhani 2008. Menggerakkan Karakter Game Menggunakan Algor.itma Breadth_First Search (BFS) dan Algoritma A*(A Star). Makalah IF255l
Strategi Algoritmik. Infbr.matika Insitut Teknolosi
Bandung.
tel
htg.s:rr en.wik iped ia.org/wiki/Breadth_ firsr_searc h, Diakses ranggal 25 Juli 20t3.
it 0l E. Wenger (1987). Artificial Intelligence
and
Tutoring System. Morgan Kaufmann] Los Altos,
CA.
KNSI 2014
5B
