Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 10

Page 1 of 10
next >

Jurnal Ilmiah Komputer dan Informatika (KOMPUTA)

1

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

IMPLEMENTASI ALGORITMA SIMPLIFIED MEMORY BOUNDED

A* UNTUK PENCARIAN KATA PADA PERMAINAN WORD SEARCH

PUZZLE

Asih Joko Purnomo

1

, Galih Hermawan

2

Program Studi Teknik Informatika

Fakultas Teknik dan Ilmu Komputer. Universitas Komputer Indonesia

Jl. Dipatiukur No 112-116 Bandung. 40132

E-mail : jokopurnomoa@gmail.com

1

, galih.hermawan@email.unikom.ac.id

2

ABSTRAK

word search puzzle

untuk mencari kata yang tersembunyi pada papan

permainan yang disusun dalam bentuk matriks.

Kata-kata tersebut dapat disusun secara horizontal,

vertikal maupun tersusun dengan lebih dari satu ruas

garis yang terhubung secara horizontal dan vertikal.

Pencarian kata yang tersusun dengan lebih dari satu

ruas garis memiliki karakteristik yang sama dengan

pathfinding

pathfinding

pencarian.

Simplified Memory Bounded A*

(SMA*)pathfinding

yang dapat digunakan untuk melakukan pencarian

word search puzzle

Algoritma SMA* memiliki kelebihan pada

penggunan memori yang lebih sedikit, hal ini

dikarenakan penggunaan memori dibatasi hingga

jumlah simpul tertentu.

Berdasarkan hasil pengujian bahwa semakin

panjang karakter pada kata yang dicari maka waktu

pencarian akan semakin lama dan penggunaan

memori juga akan semakin besar. Semakin banyak

simpul yang tersedia untuk melakukan pancarian

maka waktu pencarian akan semakin cepat, dimana

persentase peningkatan kecepatan pencarian dengan

penambahan simpul sebanyak 100% dapat

meningkat hingga 21,99% dibandingkan dengan

tidak ada penambahan simpul.

Kata kunci :

Simplified Memory Bounded A*

1. PENDAHULUAN

word search puzzle

puzzle

untuk mencari kata-kata yang disusun dalam bentuk

matriks. Kata-kata tersebut dapat disusun secara

horizontal, vertikal maupun tersusun dengan lebih

dari satu ruas garis yang terhubung secara horizontal

word

search puzzle

yang tersembunyi pada papan permainan yang

berbentuk matriks. Permasalahan yang dihadapi

adalah bagaimana sistem dapat menemukan semua

kata yang tersembunyi di dalam puzzle yang telah

tersusun secara random baik secara horizontal,

vertikal maupun tersusun dengan lebih dari satu ruas

garis yang terhubung secara horizontal dan vertikal.

Sebelumnya telah ada penelitian tentang analisis

Knuth-Morris-Pratt

Boyer-Mooreword

search puzzle.

Boyer-Moore

pencarian secara horizontal dan vertikal, sedangkan

Knuth-Morris-Pratt

pencarian secara diagonal. Akan tetapi algoritma ini

tidak dapat digunakan dalam penyelesaian

permainan ini karena aturan pencarian pada kata

yang tersusun tidak hanya horizontal, vertikal dan

diagonal saja.

Maka dari itu dalam penelitian ini digunakan

Simplified Memory Bounded A*

word

search puzzle

word search puzzle

tersebut sama dengan permasalahan pada

pathfinding

sering digunakan pada pencarian jalur terpendek dan

heuristic

ini memiliki kelebihan yaitu membutuhkan memori

yang lebih kecil dibandingkan dengan algoritma A*

[2].

Berdasarkan penjelasan yang telah dipaparkan di

word

search puzzle

algoritma yang dipilih merupakan algoritma yang

efektif untuk melakukan pencarian kata pada

word search puzzle

Tujuan yang diharapkan akan dicapai dalam

penelitian ini adalah:

1. Mengetahui apakah algoritma

Simplified

Memory-Bounded A*

word search

puzzle