implementasi algoritma simplified memory...

Jurnal Ilmiah Komputer dan Informatika (KOMPUTA)1

Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

IMPLEMENTASI ALGORITMA SIMPLIFIED MEMORY BOUNDEDA* UNTUK PENCARIAN KATA PADA PERMAINAN WORD SEARCH

PUZZLE

Asih Joko Purnomo1, Galih Hermawan2

Program Studi Teknik InformatikaFakultas Teknik dan Ilmu Komputer. Universitas Komputer Indonesia

Jl. Dipatiukur No 112-116 Bandung. 40132E-mail : [email protected], [email protected]

ABSTRAK

Permainan word search puzzle adalah permainanuntuk mencari kata yang tersembunyi pada papanpermainan yang disusun dalam bentuk matriks.Kata-kata tersebut dapat disusun secara horizontal,vertikal maupun tersusun dengan lebih dari satu ruasgaris yang terhubung secara horizontal dan vertikal.Pencarian kata yang tersusun dengan lebih dari saturuas garis memiliki karakteristik yang sama denganpermasalahan pathfinding, sehingga membutuhkansuatu algoritma pathfinding untuk melakukanpencarian.

Algoritma Simplified Memory Bounded A*(SMA*) adalah salah satu algoritma pathfindingyang dapat digunakan untuk melakukan pencariankata pada pada permainan word search puzzle.Algoritma SMA* memiliki kelebihan padapenggunan memori yang lebih sedikit, hal inidikarenakan penggunaan memori dibatasi hinggajumlah simpul tertentu.

Berdasarkan hasil pengujian bahwa semakinpanjang karakter pada kata yang dicari maka waktupencarian akan semakin lama dan penggunaanmemori juga akan semakin besar. Semakin banyaksimpul yang tersedia untuk melakukan pancarianmaka waktu pencarian akan semakin cepat, dimanapersentase peningkatan kecepatan pencarian denganpenambahan simpul sebanyak 100% dapatmeningkat hingga 21,99% dibandingkan dengantidak ada penambahan simpul.

Kata kunci : Pencarian Jalur, Pencarian Kata,Simplified Memory Bounded A*, Game Puzzle

1. PENDAHULUANPermainan word search puzzle atau permainan

pencarian kata adalah permainan berbasis puzzleuntuk mencari kata-kata yang disusun dalam bentukmatriks. Kata-kata tersebut dapat disusun secarahorizontal, vertikal maupun tersusun dengan lebihdari satu ruas garis yang terhubung secara horizontaldan vertikal. Penyelesaian dari permainan word

search puzzle ini adalah menemukan semua katayang tersembunyi pada papan permainan yangberbentuk matriks. Permasalahan yang dihadapiadalah bagaimana sistem dapat menemukan semuakata yang tersembunyi di dalam puzzle yang telahtersusun secara random baik secara horizontal,vertikal maupun tersusun dengan lebih dari satu ruasgaris yang terhubung secara horizontal dan vertikal.

Sebelumnya telah ada penelitian tentang analisisperbandingan algoritma Knuth-Morris-Pratt denganalgoritma Boyer-Moore pada permainan wordsearch puzzle [1]. Dari penelitian tersebut diketahuibahwa algoritma Boyer-Moore efisien untukpencarian secara horizontal dan vertikal, sedangkanalgoritma Knuth-Morris-Pratt lebih efisien padapencarian secara diagonal. Akan tetapi algoritma initidak dapat digunakan dalam penyelesaianpermainan ini karena aturan pencarian pada katayang tersusun tidak hanya horizontal, vertikal dandiagonal saja.

Maka dari itu dalam penelitian ini digunakanalgoritma Simplified Memory Bounded A* untukmelakukan pencarian kata pada permainan wordsearch puzzle. Algoritma ini dipilih karena melihatkarakteristik permasalahan word search puzzletersebut sama dengan permasalahan padapathfinding. Algoritma ini adalah algoritma yangsering digunakan pada pencarian jalur terpendek danmerupakan algoritma pencarian heuristic. Algoritmaini memiliki kelebihan yaitu membutuhkan memoriyang lebih kecil dibandingkan dengan algoritma A*[2].

Berdasarkan penjelasan yang telah dipaparkan diatas, maka diharapkan solusi pada permainan wordsearch puzzle dapat ditemukan dan diketahui bahwaalgoritma yang dipilih merupakan algoritma yangefektif untuk melakukan pencarian kata padapermainan word search puzzle tersebut.

Tujuan yang diharapkan akan dicapai dalampenelitian ini adalah:1. Mengetahui apakah algoritma Simplified

Memory-Bounded A* dapat digunakan untukmencari solusi pada permainan word searchpuzzle.


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

2. Mengetahui performansi dalam kecepatan danpenggunaan memori dari algoritma SimplifiedMemory-Bounded A* untuk pencarian kata padapermainan word search puzzle.

2. ISI PENELITIAN2.1Permainan Word Search Puzzle

Permainan word search puzzle dikenal sebagaiword find game, yang terkenal karena membantusiswa untuk mengenali kata-kata. Pada permainanini huruf dari sebuah kata terletak pada grid danbiasanya memiliki bentuk persegi. Untukmemainkan game ini, pemain mencari dan menandaisemua kata-kata tersembunyi di dalam grid. Dalampermainan word search puzzle, daftar katatersembunyi disediakan. Biasanya banyak kata yangterkait mudah bagi pemain untuk dicari. Kataterdaftar dapat diatur dalam arah horizontal, vertikalatau diagonal dalam grid. Semakin cepatpenyelesaian setiap tingkat, maka skor yang lebihtinggi akan didapatkan. Dalam mencari kata-kata,pengguna membaca dan menghafal kata-kata saatmereka bermain game yang membantu merekamempelajari kata-kata dan ejaan, huruf demi huruf,dalam teka-teki [5]. Berikut ini adalah gambar darisalah satu permainan word search puzzle:

Gambar 1. Word Search Puzzle [5]

2.2Metode Pencarian Heuristik (InformedSearch)Kata heuristic berasal dari sebuah kata kerja

bahasa Yunani, heuriskein, yang berarti ‘mencari’atau ‘menemukan’. Dalam dunia pemrograman,sebagian orang menggunakan kata heuristik sebagailawan kata dari algoritmik, dimana kata heuristik inidiartikan sebagai ‘suatu proses yang mungkin dapatmenyelesaikan suatu masalah tetapi tidak adajaminan bahwa solusi yang dicari selalu dapatditemukan’. Di dalam mempelajari metode-metodepencarian ini, kata heuristik diartikan sebagai suatufungsi yang memberikan suatu nilai berupa biayaperkiraan (estimasi dari suatu solusi) [2].

Metode-metode yang termasuk dalam teknikpencarian yang berdasarkan pada fungsi heuristikadalah: Generate and Test, Hill Climbing (SimpleHill Climbing dan Steepest-Ascent Hill Climbing),Simulated Annealing, Best First Search(Greedy BestFirst Search dan A* dengan berbagai varisinya,seperti Simplified Memory-Bounded A*).

2.3Algoritma Simplified Memory-Bounded A*(SMA*)Untuk masalah tertentu, di mana memori

komputer terbatas, algoritma A* mungkin tidakmampu menemukan solusi karena sudah tidaktersedia memori untuk menyimpan simpul-simpulyang dibangkitkan. Algoritma IDA* dapatdigunakan untuk kondisi seperti ini karena IDA*hanya membutuhkan sedikit memori. Tetapi, satukelemahan IDA* adalah bahwa pencarian yangdilakukan secara iteratif akan membutuhkan waktuyang lama karena harus membangkitkan simpulberulang kali [2].

Berlawanan dengan IDA* yang hanya mengingatsatu f-limit, algoritma SMA* mengingat f-Cost darisetiap iterasi sampai sejumlah simpul yang ada didalam memori. Karena batasan memori dalamjumlah tertentu, maka dapat membatasi pencarianhanya sampai pada simpul-simpul yang dapatdicapai dari root sepanjang suatu jalur yangmemorinya masih mencukupi. Kemudianmengembalikan suatu rute terbaik diantara rute-ruteyang ada dalam batasan jumlah simpul tersebut. Jikamemori komputer hanya mampu menyimpan 100simpul, maka bisa membatasi proses pencariansampai level 99.

Pada algoritma SMA* terdapat sebuah senaraiyang digunakan untuk memanipulasi antrian simpulyang terurut berdasarkan f-cost. Di sini yangdimaksud f-cost adalah gabungan biaya sebenarnyadan biaya perkiraan, yang secara matematikadinyatakan seperti pada persamaan (1) berikut:

f(n) = g(n) + h(n) (1)Dengan:n = simpul saat inig(n) = biaya (cost) dari simpul awal ke simpul n

sepanjang jalur pencarianh(n) = perkiraan cost dari simpul n ke simpul

tujuan (nilai heuristic)f(n) = total cost dari simpul n ke simpul tujuan


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

Berikut ini adalah algoritma Simplified Memory-Bounded A* [2]:function SMA*(masalah) returns solusiinputs : masalah, sebuah masalahlocal variables : Queue, antrian nodes yang terurutberdasarkan f-costQueue MAKE-QUEUE({MAKE-SIMPUL(INITIAL-STATE[masalah])})loop do

if Queue kosong then return gagaln simpul di Queue yang memiliki f-cost

terkecil dan level terdalamif GOAL-TEST(n) then return suksessuk NEXT-SUCCESSOR(n)if suk bukan goal dan levelnya sudah

maksimum thenf(suk) INFINITE

elsef(suk)MAX(f(n), g(n) + h(n))

endif semua suksesor dari n sudah dibangkitkan

thenGanti f-cost pada n dengan nilaif(suk) yang terkecil. Gantikan nilaif(suk) terkecil ini ke semuaancestors dari n(ayah, kakek, danseterusnya keatas) kecualiancestors yang memiliki f-costlebih kecil daripada f(suk)terkecilitu.

if semua SUCCESSOR(n) sudah di memorithen

Keluarkan n dari Queue (tetapi tidakdihapus secara fisik di memori)

if memori penuh thenif suk = Goal and f(suk) = f(start) then

return sukses dan exitHapus simpul terburuk di dalamQueue yang memiliki f-costterbesar dan level terdangkal.Keluarkan simpul terburuktersebut dari daftar suksesorparent-nya.Masukkan parent dari simpulterburuk tersebut ke Queue jikaparent tersebut tidak ada di Queue.

endinsert suk in Queue

Gambar 2. Algoritma SMB A*

Misalnya terpadat masalah pencarian ruteterpendek seperti pada gambar berikut:

Gambar 3. Masalah Pencarian Rute

Berikut ini adalah langkah-langkah penyelesaianmenggunakan algoritma Simplified Memory-Bounded A*:

S80

Gambar 4. Langkah 1 Pencarian Rute

S

A

B

C

D

E

10

25

30

35

10

84(120)

f(A) - MAX(f(S),g(A)+h(A)) = MAX(80,90) = 90

f(B) = 85

f(C) = 100

f(D) = 120

f(E) = 84

Gambar 5. Langkah 2 Pencarian Rute

S

A

B

C

E

D

10

25

30

10

15

f(A) = 90

f(B) = 85

f(C) = 100

f(D) = MAX(f(E), g(D)+h(D))= MAX(84, 110) = 110

84(100, 120)

84

Gambar 6. Langkah 3a Pencarian Rute


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

S

A

B

E

D

10

25

10

15

f(A) = 90

f(B) = 85

f(D) = 110

85(100, 120)

J20

f(J) = MAX(f(E), g(J)+h(J))= MAX(84, 130) = 130

110 (110)

Gambar 7. Langkah 3b Pencarian Rute

S

A

10

90 (100, 110, 120)

f(G) = MAX(f(K), g(G)+h(G))= MAX(95, 95) = 95

95 (100)B

10F5

95

K40

95

G

3095

Gambar 8. Langkah 8 Pencarian Rute (hasil akhirpencarian)

2.4Analisis SistemPermainan word search puzzle terdiri dari 2

proses yaitu pengacakan kata dan pencarian kata.Proses pengacakan kata yaitu mengisi papanpermainan dengan kata yang tersusun secara acakdan mengisi huruf acak pada matriks yang kosong.Proses pencarian kata yaitu melakukan pencariankata pada papan permainan yang telah terisi katayang tersusun secara acak. Berikut ini adalahflowchart dari permainan word search puzzle:

Mulai

Pengacakan Kata

Daftar Kata

Pencarian Kata

SolusiPermainan

Selesai

Gambar 9. Flowchart Word Search Puzzle

Pada permainan word search puzzle terdapatbeberapa aturan yang berbeda antara satu permainandengan permainan lainnya. Untuk aturan yang adapada permainan ini antara lain sebagai berikut:a. Pencarian kata dapat dilakukan secara horizontal

dan vertikal, dan tidak bisa secara diagonal.

A G H X C D W N S A F

K J D C F G M X S D L X

G B E L A J A R J E A Q

M N W A S X C W K O P C

C B Z B H N N M E X D Z

T E D K E L B E L X Q Z

R L Q C V L K V A W T S

S A F K D M A G J A Z D

G J Z H X L K J U R I L

Z A C W V E B I A T N Y

A R S Z B D Z E H R J R

S E F N V L B X H K J V

W

0 21 3 4 5 6 7 8 9 10 11

0

1

2

3

4

5

6

7

8

9

10

11

Dapat dilakukan pencarian

Tidak dapat dilakukan pencarian

Gambar 10. Aturan Pencarian Kata

b. Pencarian kata juga dapat dilakukan denganberbelok-belok ke atas, ke bawah, ke kiri dan kekanan, tetapi antara karakter satu dengan yanglainnya harus terhubung secara horizontal atauvertikal.

A G H X C D W N S A F

K J D C F G M X S D L X

G F K L Z C V B J E A Q

M N B E S X C B K O P C

C H Z L H N N E E X D Z

T K D A J L B L L X Q Z

R B Q C A G K A J A R S

S V F K R M D G J A Z D

G B Z H X L K S U R I L

Z E C W J E B I K T N Y

A X L A B A Z E H A J R

S E F N V R B X H K J V

W

0 21 3 4 5 6 7 8 9 10 11

0

1

2

3

4

5

6

7

8

9

10

11

Dapat dilakukan pencarian

Tidak dapat dilakukan pencarian

Gambar 11. Aturan Pencarian Kata(2)

c. Pencarian dapat dimulai dari manapun antarakoordinat (0,0) hingga koordinat (19,19) padamatriks.

d. Panjang karakter pada kata yang dicari antara 5hingga 30 karakter.


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

2.5 Analisis MasalahPermasalahan yang muncul pada permainan

word search puzzle adalah bagaimana sistem dapatmenemukan semua kata yang tersembunyi di dalammatriks. Pertama dilakukan pencarian huruf pertamapada kata yang akan dicari, kemudian dicari hurufkedua dengan mencari ke atas, bawah, kiri dankanan yang mengelilingi huruf pertama tersebut.Metode tersebut diulang hingga kata yang dicariditemukan.

Untuk melakukan pencarian kata pada permainanword search puzzle dapat menggunakan algoritmapath finding. Terdapat beberapa algoritma pathfinding yang bisa digunakan. Algoritma yangdigunakan adalah algoritma Simplified Memory-Bounded A*. Algoritma Simplified Memory-Bounded A* (SMA*) merupakan pengembangan darialgoritma A* yang mengatasi masalah untukmelakukan pencarian kata pada permainan wordsearch puzzle. Algoritma ini mengatasi kelemahanyang dimiliki oleh algoritma A* yaitu penggunaanmemori yang besar.

Oleh karena itu , yang akan diteliti untukmengukur efektifitas penggunaan algoritma SMA*adalah sebagai berikut:1. Jumlah simpul yang dibangkitkan dan dihapus

selama proses pencarian.2. Waktu eksekusi untuk pencarian solusi.

2.6 Analisis Game Word Search PuzzleAnalisis pada game word search puzzle

dilakukan untuk melihat keefektifan dalam halwaktu eksekusi dan jumlah simpul yangdibangkitkan dan dihapus. Dalammengimplementasikan algoritma SMA* akandibangun sebuah prototype dengan gambaran gameword search puzzle adalah sebagai berikut:1. Game terdiri dari matriks dengan ukuran minimal

yaitu 3 baris x 3 kolom dan maksimal 20 baris x20 kolom.

2. Penerapan algoritma yang dipilih yaitu algoritmaSMA*.

3. Nilai masukan parameter yaitu jumlah simpulmaksimum.

4. Kata yang dicari diletakkan pada matriks secararandom.

5. Pencarian hanya bisa dilakukan secarahorizontal, vertikal, dan gabungan antarahorizontal dan vertikal yang terhubung denganlebih dari satu ruas garis.Papan permainan pada word search puzzle dibuat

dengan skala pixel yang berukuran panjang 500 pixeldan lebar 500 pixel. Dalam papan permainantersebut disimpan beberapa grid ukuran panjang 25pixel dan lebar 25 pixel, didapatkan 20 gridhorizontal dan 20 grid vertikal. Jika dijumlahkankeseluruhan grid-nya menjadi 400 grid.

Papan permainan seperti pada gambar berikut:Papan Permainan

20 grid horizontal

20 gridvertikal

Gambar 12. Papan Permainan

Pada permainan ini terdapat 2 proses besar yangdilakukan antara lain:1. Pengacakan Kata2. Pencarian Kata

Proses pengacakan kata dilakukan denganmengisi matriks dengan kata-kata yang dicaridengan aturan sesuai dengan yang telah dijelaskandiatas, kemudian mengisi matriks yang kosongdengan huruf acak. Proses pencarian kata dilakukandengan melakukan pencarian kata sesuai denganaturan yang telah dijelaskan diatas, setelah pencarianditemukan maka disimpan koordinat dari kata yangdicari.

Untuk lebih jelasnya berikut ini adalah flowchartdari proses pengacakan kata:

Mulai

Menempatkan kata padapapan permainan secara

acak

Mengambilkata dari file

teks

Menempatkan karaktersecara acak pada matriks

yang kosong

Papanpermainantelah terisikata acak

Selesai

Gambar 13. Flowchart Pengacakan Kata


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

Pada penelitian ini proses yang akan dibahaslebih dalam adalah proses pencarian katamenggunakan algoritma Simplified Memory-Bounded A*. Pada proses pencarian kata terdapatbeberapa langkah, antara lain seperti pada flowchartberikut:

Mulai

Mencari posisi awalpencarian

Kata yangdicari

Melakukan pencarian katadengan algoritma SMA*

Hasilpencarian

kata

Selesai

Gambar 14. Flowchart Pencarian Kata

2.7 Analisis MasukanAnalisis data masukan yang dibutuhkan pada

algoritma SMA* yaitu posisi huruf pertama dari katayang dicari (initial state), kata yang dicari (goalstate). Posisi huruf pertama dicari secara sekuensialdari kolom pertama dan baris pertama hingga kolomterakhir dan baris terakhir atau sampai posisiditemukan. Selain itu, dalam pencarian algoritmaSMA*, dibutuhkan pencarian untuk menghitungnilai f(n).

Pencarian kata dilakukan pada papan permainanyang berukuran 20x20. Papan permainan telah terisikata yang dicari yang disusun secara acak. Papanpermainan terisi dengan kata dengan panjangmaksimal 30 karakter. Kata yang akan dimasukkanke dalam matriks tersebut disimpan di dalam fileteks, dan diambil secara acak untuk dimasukkan kedalam matriks.

Setelah proses penempatan kata pada papanpermainan, maka papan permainan telah terisi katayang tersusun secara acak. Papan permainan yangtelah terisi kata seperti pada gambar berikut:

A G H X C D W N S A F G P I T F V S

K J D C F G M X S D L X K Q Y T J E R R

G H J D R E D H J E A Q D F R E F J J M

M N W A S X C W K O P C V F G X G H G N

C V Z N H N N M E X D Z F Q I U Q T D

T Y D K D L B E L X Q Z F R Y K Z X D S

R W Q C V N K V A W T S D K D L O P E Q

S J F K D M K G J A Z D A X M X N C B V

G N Z H X L K S U R I L U L D Y H P Y R

Z Q C W V E B I R T N Y M U I T O P S

A W S Z B D Z E H H J R L J B N J X K L

S E F N V L B X H K J V X B F T V N F D

D G S Z C N M R X X J V B B K N M X Z J

D V X B C R C C X Z Z C V N B T Y L M U

V M B B N Z A N Z Z D T T M V N K C X

F N Q R X W R E V R T T F U D S I J O A

C X V C B B Z X N W T W T M T X E Z R H

H N V X Z C L L B B M N L K M L L J C P

A B Z N D H X M J I C O O L P V X N C M

Z A B S N D M Z F N Q G W E H R T J Y K

W O

Y

A

G

0 21 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

Gambar 15. Papan Permainan Yang Terisi Kata

Kemudian setelah proses penempatan kata, makaproses selanjutnya yaitu mengisi matriks yangkosong dengan huruf acak. Setelah matriks yangkosong terisi huruf acak, maka hasilnya seperti padagambar berikut:





















W O

Y

A

G

0 21 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

Gambar 16. Papan Permainan Yang Terisi HurufAcak

2.8 Analisis AlgoritmaAnalisis algoritma yang dilakukan dalam

penelitian ini adalah untuk menganalisis cara kerjaalgoritma SMA* (Simplified Memory-Bounded A*)terhadap masalah word search puzzle untukmelakukan pencarian kata. Pada bagian ini akandijelaskan proses secara manual untuk menghasilkanoutput.

Pada algoritma SMA* (Simplified Memory-Bounded A*) untuk melakukan pencarian makadilakukan perhitungan f-cost untuk setiap simpulyang dibangkitkan. Untuk menghitung f-cost makasecara matematika dinyatakan pada persamaan (1)berikut:

f(n) = g(n) + h(n)


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

Dengan:n = simpul saat inig(n) = biaya (cost) dari simpul awal ke simpul nsepanjang jalur pencarianh(n) = perkiraan cost dari simpul n ke simpultujuan (nilai heuristic)f(n) = total cost dari simpul n ke simpul tujuan

Untuk menghitung nilai heuristic, maka dicarimengunakan total huruf pada kata yang dicaridikurangi total huruf yang benar dari pencarian.Perhitungan nilai heuristic adalah seperti berikut:

h(n) = Total huruf kata dicari – total huruf benar

Adapun langkah-langkah manual pencarianSMA* adalah seperti berikut:a. Pilih simpul dengan cost paling kecil dan level

terdalamb. Bangkitkan suksesor selanjutnya dari simpul n

suk = NEXT-SUCCESOR(n)c. Hitung f-cost dari suksesor yang telah

dibangkitkanf(suk) = MAX(f(n), g(n) + h(n))

d. Jika semua suksesor simpul terpilih sudahdibangkitkan, maka ganti f-cost pada n dengannilai f(suk) yang terkecil.

e. Jika semua suksesor n sudah di memori, makakeluarkan n dari Queue (tetapi tidak dihapussecara fisik di memori).

f. Jika memori penuh, maka hapus simpul terburukdi dalam Queue yang memiliki f-cost terbesardan level terdangkal. Keluarkan simpul terburuktersebut dari daftar suksesor parent-nyaMasukkan parent dari simpul terburuk tersebutke Queue jika parent tersebut tidak ada di Queue.

g. Masukkan simpul suksesor ke Queue

Dengan:n = simpul saat inisuk = simpul suksesor dari nf(suk) = f-cost simpul suksesor nMAX = nilai maksimumNEXT-SUCCESSOR(n) = simpul suksesorselanjutnya dari n

Misalnya pada kasus ini akan dicari kata“BELAJAR” pada matriks yang telah tersusunsecara random. Proses pertama yang dilakukanadalah mencari posisi dari huruf pertama dari katayang akan dicari. Untuk melakukan pencariantersebut maka harus dilakukan pencarian secarasekuensial dari kolom ke-0 dan baris ke-0. Disinidilakukan pencarian karakter B pada matrikstersebut. Kemungkinan huruf B pada matrikstersebut akan lebih dari satu, sehingga akan diambilhuruf yang pertama kali ditemukan. Apabila posisisudah ditemukan, maka akan dilakukan pencariandengan posisi awal simpul adalah posisi yang telahditemukan tersebut. Misalnya pada kasus tersebutjumlah simpul maksimum adalah 8 simpul.

Berikut ini adalah contoh matriks dengankarakter pertama pada kata yang telah ditemukan:





















W O

Y

A

G

0 21 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

Keterangan :

B Simpul Awal

Gambar 17. Kondisi Awal Pencarian Kata

Setelah huruf pertama ditemukan, makadilakukan pencarian menggunakan algoritma SMA*dengan langkah-langkah seperti berikut:

Gambar 18. Langkah 1 Pencarian Kata

Simpul yang telah diperiksa

Simpul yang sedang diperiksa

Simpul yang akan diperiksa

A G H X C D W N S A

K J D C F G M X S D L

G H J D R E D H J E A

M N W A S X C W K O P

C V Z N H N N M E X D

T Y D K D L B E L X Q

R W Q C V N K V A W T

S J F K D M K G J A Z

G N Z H X L K S U R I

Z Q C W V E B I R T N

A W S Z B D Z E H H J

W

0 21 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

Gambar 19. Matriks Langkah 2 Pencarian Kata


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

(5,6)

(5,5) (4,6) (5,7) (6,6)

1 1 1 16

f(5,5) = 7 f(4,6) = 7f(6,6) =MAX(f(5,6),g(6,6)+h(6,6))= MAX(6,7) = 7

f(5,7) = 6

Gambar 20. Langkah 2 Pencarian Kata




A G H X C D W N S A











W

0 21 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

Gambar 21. Matriks Langkah 3a Pencarian Kata

(5,6)

(5,5) (4,6) (5,7) (6,6)

1 1 1 16

f(5,5) = 7 f(4,6) = 7 f(6,6) = 7f(5,7) = 6

(4,7)f(4,7) =MAX(f(5,7),g(4,7)+h(4,7))= MAX(6,7) = 7

1

Gambar 22. Langkah 3a Pencarian Kata




A G H X C D W N S A











W

0 21 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

Gambar 23. Matriks Langkah 7b Pencarian Kata

(5,6)

(5,7)

1

6(7,7,7)

(5,8)

1

6(7,7)

6(7,7)

(6,8)

1

6(7,7)

(7,8)

1

6(7,7)

(7,9) f(7,9) = 6

1

(8,9)f(8,9) =MAX(f(7,9),g(8,9)+h(8,9))= MAX(6,6) = 6

1

(7,10)f(7,10) = 7

1

Gambar 24. Langkah 7b Pencarian Kata (Solusi)

Pada gambar diatas menunjukkan pencarian telahselesai, dengan jalur yang ditemukan adalah (5,6) –(5,7) – (5,8) – (6,8) – (7,8) – (7,9) – (8,9). Sehinggaapabila simpul tersebut digabungkan maka akanmembentuk kata “BELAJAR”.

2.9 Hasil Pengujian AlgoritmaPengujian algoritma dilakukan untuk menguji

algoritma Simplified Memory-Bounded A* dari segiperformansi dan penggunaan memori. Pengujiandilakukan dengan panjang karakter yang berbedadan simpul tambahan yang yang digunakan selamapencarian.

Banyaknya pengujian yang dilakukan yaitusebanyak 300 kali percobaan dengan panjangkarakter dari 5 hingga 30 karakter dan simpultambahan 0% hingga 100% dari panjang karakterpada kata yang dicari. Hasil pengujian waktupencarian algoritma SMA* yang didapat dapatdilihat pada tabel 1.


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

Tabel 1. Hasil Pengujian Waktu Pencarian Algoritma SMA*

PanjangKarakter

Simpul Tambahan0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

5 28.28 25.1 27.77 27.86 29.29 24.8 23.54 23.81 22.75 22.68 23.310 78.02 77.63 73.54 80.31 74.02 66.76 69.16 70.31 66 67.28 60.8615 149.13 132.55 143.39 148.09 140.71 136.99 136.18 127.34 119.95 117.63 116.620 252.78 279.58 246.57 239.4 252.57 235.3 212.45 210.65 215.39 197.47 220.0225 359.76 356.27 375.04 324.94 352.86 353.26 342.98 317.64 314.36 306.59 280.730 487.3 480.78 504.47 493.72 473.29 451.66 434.2 415.29 417.9 415.31 405.43

Ket : Waktu dalam ms (milisecond)

Gambar 25. Grafik Hasil Pengujian Waktu Pencarian Algoritma SMA*

Pada tabel 1 dan Gambar 25 terlihat bahwasemakin panjang karakter pada kata yang dicarimaka waktu pencarian akan semakin lama. Hal inidikarenakan semakin panjang karakter pada katayang dicari maka semakin banyak pula simpul yangharus dibangkitkan. Kemudian pada waktupencarian semakin banyak simpul yang digunakan,

maka semakin sedikit waktu yang digunakan. Hal inidikarenakan semakin banyak simpul yang tersediamaka proses penghapusan simpul menjadi lebihsedikit. Untuk pengujian waktu berdasarkan panjangkarakter dapat dilihat pada tabel 2.

Tabel 2. Kesimpulan Hasil Pengujian Waktu Pencarian Algoritma SMA*

Panjang Karakter Waktu Tercepat Simpul Tambahan PeningkatanKecepatan

5 22.68 ms 90% 19,8%10 60.86 ms 100% 21,99%15 116.6 ms 100% 21,81%20 197.47 ms 90% 21,88%25 280.7 ms 100% 21,98%30 405.43 ms 100% 16,8%

Data percobaan yang tertera pada tabel 2 terlihatbahwa penambahan simpul 100% memiliki waktupencarian yang lebih cepat, kecuali pada kata yangmemiliki panjang karakter 5 dan 20 karakter.Persentase peningkatan kecepatan pencarian tersebutyaitu 21,99% pada pencarian kata 10 karakter,21,81% pada pencarian kata 15 karakter, 21,98%pada pencarian kata 25 karakter dan 16,8% padapencarian kata 30 karakter. Sedangkan untuk

pencarian kata 5 karakter adalah 19,8% dan padapencarian kata 20 karakter adalah 21,88% padapenambahan simpul 90%. Pada pengujian tersebutterdapat rata-rata simpul yang digunakan selamapencarian. Penggunaan simpul diambil dari simpulyang dibangkitkan dikurangi dengan simpul yangdihapus selama pencarian. Hasil pengujianpenggunaan simpul dapat dilihat pada tabel 3.


Vol. 5, No. 1, Maret 2016, ISSN : 2089-9033

Tabel 3. Hasil Pengujian Penggunaan Simpul Pencarian Algoritma SMA*PanjangKarakter

Simpul Tambahan0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

5 5 6 5 5 6 6 7 7 8 8 910 10 10 11 12 13 14 15 16 17 18 1915 15 15 17 18 20 21 23 24 26 27 2920 20 24 23 25 27 29 31 33 35 37 3925 25 36 29 31 34 36 39 41 44 46 4930 30 43 35 38 41 44 47 50 53 56 59

Ket : value = simpul yang digunakan

Gambar 26. Grafik Hasil Pengujian PenggunaanSimpul Pencarian Algoritma SMA*

Pada tabel 3 dan Gambar 26 terlihat bahwa semakinpanjang karakter pada kata yang dicari maka simpulyang digunakan akan semakin banyak. Kemudianpenambahan simpul juga berpengaruh padapenggunaan simpul selama pencarian. Semakinbanyak penambahan simpul maka semakin banyakjuga simpul yang digunakan.

3 PENUTUP3.1 Kesimpulan

Berdasarkan penelitian mengenai implementasialgoritma Simplified Memory-Bounded A* untukpencarian kata pada permainan word search puzzlemaka dapat dibuat kesimpulan:1. Algoritma Simplified Memory-Bounded A* dapat

digunakan untuk melakukan pencarian kata padapermainan word search puzzle.

2. Berdasarkan hasil pengujian bahwa semakinpanjang karakter pada kata yang dicari makawaktu pencarian akan semakin lama danpenggunaan memori juga akan semakin besar.Semakin banyak simpul yang tersedia untukmelakukan pencarian maka waktu pencarian akansemakin cepat, dimana persentase peningkatankecepatan pencarian dengan penambahan simpulsebanyak 100% dapat meningkat hingga 21,99%dibandingkan dengan tidak ada penambahansimpul.

3.2 SaranAdapun saran yang dapat diberikan untuk

pengembangan selanjutnya antara lain adalahsebagai berikut.

1. Menentukan persentase penambahan simpul yangoptimal untuk setiap kasus pencarian.

2. Penambahan daftar kata dapat dilakukan secaraotomatis oleh sistem dengan mengambil kata darikamus Bahasa Indonesia.

DAFTAR PUSTAKA

[1] A. Rojali, "Analisis Perbandingan AlgoritmaKnuthmorris-Pratt dengan Algoritma Boyer-Moore Pada Permainana Word Search Puzzle,"Skripsi Teknik Informatika, UniversitasKomputer Indonesia, 2014.

[2] Suyanto, Artificial Intelligence Searching,Reasoning, Planning dan Learning, Bandung:Informatika Bandung, 2014.

[3] M. Nazir, Metodologi Penelitian, Bogor: GhaliaIndonesia, 2005.

[4] R. S. Pressman, Rekayasa Perangkat LunakPendekatan Praktis, Yogyakarta: Andi, 2012.

[5] A. Sukstrienwong and P. Vongsumedh,"Software Development of Word Search Gameon Smart Phones in English VocabularyLearning," International Conference onEducation and Modern EducationalTechnologies, 2013.

[6] S. Russel and P. Norvig, Artificial Intelligence:A Modern Approach, Prentice HallInternational, Inc, 1995.

[7] B. Hariyanto, Esensi-esensi BahasaPemrograman Java, Bandung: Informatika,2014.

[8] A. Nugroho, Rational Rose Untuk PemodelanBerorientasi Objek, Bandung: Informatika,2005.

[9] Munawar, Pemodelan Visual dengan UML,Yogyakarta: Graha Ilmu, 2005.

[10] K. Hamilton and R. Miles, Learning UML 2.0,Sebastopol: O'Reilly Media, Inc., 2006.

[11] Ayuliana, "Teknik Pengujian PerangkatLunak," Jurnal Teknik Informatika, UniversitasGunadarma, 2009.

implementasi algoritma simplified memory...

Documents