ANALISIS PERBANDINGAN ALGORITMA PATHFINDING GREEDY BEST-FIRST SEARCH DENGAN A*(STAR) DALAM MENENTUKAN LINTASAN PADA PETA Christophorus Yohannes Suhaili1; Mendy Irawan2; Raja Muhammad Fahrizal3; Antonius Herusutopo4 1,2,3,4
Computer Science Department, School of Computer Science, BINUS University, Jln. K.H. Syahdan No. 9, Palmerah, Jakarta Barat 11480
[email protected],
[email protected],
[email protected]
ABSTRACT There are various pathfinding algorithm which has advantages and disadvantages of each algorithm. The purpose of this study was to compare the pathfinding algorithm greedy best-first search with a * (star) in the case of determining the trajectory on the map in terms of the path traversed length and the length of time to think when the algorithm is executed. The method used in this research is the analysis method for analyzing any algorithm that can be applied in the search path. Then, the method followed by the greedy algorithm design method for a best-first search and A * in the form of a flowchart, a map of the Center of Java, the user interface to the algorithms testing application. The next method is the method of implementation, the greedy best-first search algorithm and A * algorithm is implemented to test applications. The latter method is a method of testing of the algorithms will be compared. Conclusions will be drawn from the results of the comparison algorithm. The results of this study is a comparison table between the distance and the time thinking greedy algorithm best-first search with A *. The conclusions of this study are greedy best-first algorithm has an average search time to think faster than the A * algorithm, but the A * algorithm provides a shorter path, or the same as the greedy algorithm best-first search Keyword: comparison algorithm, pathfinding algorithm, greedy best-first search, A*
ABSTRAK Terdapat bermacam-macam algoritma pathfinding yang memiliki kekurangan dan kelebihan masing-masing algoritma. Tujuan dari penelitian ini adalah membandingkan algoritma pathfinding greedy best-first search dengan A*(Star) dalam hal menentukan lintasan pada peta dari segi panjang lintasan yang dilalui dan lamanya waktu berpikir saat proses algoritma dijalankan. Metode yang digunakan dalam penelitian ini adalah metode analisis untuk menganalisis algoritma apa saja yang dapat diterapkan dalam pencarian lintasan. Kemudian, metode dilanjutkan dengan metode perancangan terhadap algoritma greedy best-first search dan A* dalam bentuk flowchart, peta Jawa Tengah, user interface pada aplikasi pengujian algoritma. Metode selanjutnya adalah metode implementasi, yaitu algoritma greedy best-first search dan A* diimplementasikan ke aplikasi pengujian algoritma. Metode terakhir adalah metode pengujian terhadap algoritma yang akan dibandingkan. Simpulan akan ditarik dari hasil perbandingan algoritma. Hasil dari penelitian ini adalah tabel perbandingan jarak dan waktu berpikir antara algoritma greedy best-first search dengan A*. Simpulan dari penelitian ini adalah algoritma greedy best-first search memiliki rata-rata waktu berpikir yang lebih cepat daripada algoritma A*, namun algoritma A* memberikan lintasan yang lebih pendek atau sama dengan algoritma greedy best-first search. Kata Kunci: perbandingan algoritma, algoritma pathfinding, greedy best-first search, A*
PENDAHULUAN Pada jaman serba modern ini, peta masih digunakan oleh kebanyakan orang untuk menuju suatu tempat. Lintasan yang dipilih untuk menuju tujuan pastilah lintasan yang paling pendek. Namun, pencarian lintasan terpendek secara manual, akan membutuhkan banyak waktu dan ketelitian. Masalah lintasan terpendek berkaitan dengan pencarian lintasan pada graf berbobot yang menghubungkan dua buah simpul (edge) sedemikian sehingga jumlah bobot pada sisi-sisi yang terpilih merupakan bobot minimum. Terdapat banyak algoritma yang dapat digunakan untuk pemecahan masalah dalam pencarian lintasan terpendek. Pemilihan algoritma yang paling optimal seringkali menjadi permasalahan dalam pencarian lintasan terpendek karena setiap algoritma memiliki kelebihan dan kekurangannya masing-masing (Hardianto, 2013: 79). Secara umum, algoritma pencarian dapat dibedakan menjadi dua metode yaitu, metode uninformed search dan metode informed search. Metode uninformed search merupakan metode matematika biasa dengan informasi yang jelas, sedangkan metode informed search merupakan metode pencarian yang menggunakan metode pendekatan pada proses pencariannya. Metode informed search diketahui lebih efisien dibandingkan dengan metode uninformed search (Russell & Norvig, 2010: 92). Dari sebab itulah maka akan dilakukan perbandingan terhadap algoritma greedy best-first search dengan A* yang merupakan metode pencarian informed search. Kedua algoritma tersebut merupakan algoritma yang paling terkenal dalam informed search. Tujuan dari penelitian ini adalah mengetahui metode algoritma A* dan algoritma greedy best-first search dalam menentukan lintasan terpendek, membuat perbandingan algoritma A* dan algoritma greedy best-first search dalam menentukan lintasan terpendek, membuktikan teori yang ada sebelumnya tentang algoritma greedy best-first search dan A* dalam menentukan lintasan terpendek Manfaat yang akan didapat adalah
menambah wawasan dan pengetahuan tentang
masalah pencarian lintasan terpendek dan lebih mengenal tentang algoritma A* dan algoritma greedy best-first search dalam masalah penentuan lintasan terpendek.
METODE PENELITIAN Metode penelitian yang digunakan dalam penelitian ini adalah : 1.
Metode Analisis Tahapan-tahapan yang dilakukan dalam metode analisis adalah analisis terhadap berbagai algoritma yang telah dan dapat diterapkan dalam pencarian lintasan terpendek dari beberapa sumber seperti jurnal lokal maupun jurnal internasional.
2.
Metode Perancangan Tahapan-tahapan
yang
dilakukan
dalam
metode
perancangan
adalah
merancang flowchart dari algoritma A* dan greedy best-first search untuk setiap tahapan pencarian lintasan terpendek pada peta. Kemudian, tahapan selanjutnya dalam metode perancangan adalah merancang peta dengan data
dari provinsi Jawa Tengah dan user interface untuk aplikasi pengujian algoritma. 3.
Metode Implementasi Metode implementasi dilakukan dengan menerapkan algoritma A* dan greedy best-first search yang telah dirancang ke dalam aplikasi pengujian algoritma.
4.
Metode Pengujian Dalam metode pengujian, algoritma A* dan greedy best-first search yang telah diterapkan dalam aplikasi akan diuji. Pengujian akan dilakukan dengan melihat algoritma mana yang memberikan lintasan lebih pendek dan waktu berpikir yang lebih singkat. Kemudian, dari hasil pengujian akan dilakukan penarikan kesimpulan.
HASIL DAN BAHASAN Berikut ini merupakan rancangan flowchart dari algoritma greedy best-first search :
Gambar 1 Flowchart Greedy Best-first Search
Dilihat dari gambar 1, berikut penjelasan urutan jalan algoritma greedy best-first search yang diterapkan dalam permainan aplikasi dimulai dari proses awal algoritma dijalankan, proses menentukan start node, proses pencarian goal node pada langkah ketiga sampai ketujuh, hingga proses selesai pada langkah kedelapan. 1. Mulai Fungsi greedy best-first search dipanggil dan dijalankan oleh class. Pemanggilan ini dilakukan ketika algoritma greedy best-first search melakukan penghitungan lintasan. 2. Inisiasi start node sebagai current node Pada proses ini, aplikasi akan menginisialisasi start node dari kota yang dipilih oleh user. Start node akan menjadi current node untuk melangkah ke proses selanjutnya untuk pencarian lintasan. 3. Apakah current node sudah sama dengan goal node? Pada proses ini, akan dilakukan pengecekan apakah current node merupakan goal node atau bukan. Jika ya, maka proses akan selesai. Jika tidak, maka proses dilanjutkan ke langkah selanjutnya. 4. Cek semua heuristic cost dari semua node yang terhubung pada current node. Proses ini merupakan kelanjutan dari proses pengecekan goal node. Apabila current node bukan merupakan goal node, maka aplikasi akan mengecek semua node yang terhubung pada current node. Pengecekan dilakukan terhadap heuristic cost pada nodenode yang terhubung ke current node. 5. Pilih node dengan heuristic cost terkecil dan tandai node tersebut dengan next node Setelah semua heuristic cost pada node yang terhubung ke current node selesai dicek, aplikasi akan memilih node dengan heuristic cost terendah. Node yang memiliki heuristic cost terendah akan digunakan menjadi node selanjutnya (next node). 6. Tabahkan current node ke dalam linked list dari actual path Tambahkan current node ke dalam linked list. Semua node yang ada di dalam linked list akan menjadi actual path dari algoritma greedy best-first search. 7. Ubah next node menjadi current node Pada proses ini, aplikasi akan mengubah next node menjadi current node untuk digunakan pada proses selanjutnya. Proses selanjutnya adalah mengecek kembali apakah current node adalah goal node atau bukan. 8.
Selesai Proses akan selesai apabila current node adalah goal node. Semua node dalam linked list merupakan solusi shortest path yang diberikan oleh algoritma greedy best-first search.
Berikut ini merupakan rancangan flowchart dari algoritma A*
Gambar 2 Flowchart A*
Dilihat dari gambar 2, berikut penjelasan urutan jalan algoritma A* yang diterapkan dalam permainan aplikasi dimulai dari proses awal algoritma dijalankan, proses menentukan start node, proses pencarian goal node pada langkah ketiga sampai dua belas, proses backtrack untuk mencari shortest path pada langkah tiga belas sampai delapan belas, hingga proses selesai pada langkah sembilan belas. 1.Mulai Fungsi A* dipanggil dan dijalankan oleh class. Pemanggilan ini dilakukan ketika algoritma A* melakukan penghitungan lintasan. 2.Inisiasi start node sebagai current node Pada proses ini, aplikasi akan menginisialisasi start node dari kota yang dipilih oleh user. Start node akan menjadi current node untuk melangkah ke proses selanjutnya. 3.Apakah current node sudah sama dengan goal node? Pada proses ini, akan dilakukan pengecekan apakah current node merupakan goal node atau bukan. Jika ya, maka proses akan dilanjutkan ke algoritma bactrack. Jika tidak, maka proses dilanjutkan ke langkah selanjutnya untuk pencarian lintasan. 4.Cek setiap node yang terhubung dengan current node Pada proses ini, dilakukan pengecekan terhadap semua node yang terhubung pada current node. Pengecekan ini bertujuan untuk mengetahui node apa saja yang terhubung dengan current node. 5.Hitung nilai dari node yang terhubung dengan current node.Pada tahap ini, dilakukan perhitungan terhadap node yang terhubung (connected node) pada current node kecuali node yang sudah ada pada done queue karena node tersebut sudah pernah dihitung nilai -nya. Nilai akan didapatkan dari penjumlahan actual cost dari start node sampai ke connected node dan heuristic cost dari conected node. 6.Masukkan connected node ke dalam pending queue Setelah semua nilai dari connected node sudah dihitung, masukkan semua connected node ke pending queue untuk diproses di tahap selanjutnya. 7.Masukkan current node dengan destination node ke dalam done queue Masukkan current node sebagai source node dengan destination node ke dalam done queue. Destination node didapatkan dari connected node yang memiliki nilai terendah. Jika terdapat nilai
yang sama, maka akan dipilih node dengan actual cost
terbesar. Done queue berisi node-node yang sudah dilalui dan akan diproses kembali pada algoritma backtrack. 8.Cek node pada pending queue yang memiliki nilai terendah Dalam proses ini, akan dilakukan pengecekan terhadap node dengan nilai terendah yang berada di dalam pending queue. Node dengan nilai terendah akan digunakan pada tahap selanjutnya.
9.Set node dengan nilai terendah sebagai current node Setelah dilakukan pengecekan terhadap node-node pada tahap 8, node dengan terendah akan menjadi current node yang baru untuk diproses pada algoritma A* kembali sampai current node adalah goal node. 10. Hapus node dengan nilai terendah pada pending queue Node dengan nilai terendah pada pending queue akan dihapus. Hal ini bertujuan untuk mencegah node tidak di cek kembali saat proses pengecekan pending queue. 11. Apakah current node ada di done queue? Pada proses ini, dilakukan pengecekan apakah current node sudah ada di done queue atau belum. Current node akan di cek dengan setiap source node yang ada pada done queue. Jika sudah ada, maka artinya node tersebut sudah pernah dikerjakan. Jika belum, node tersebut akan dilanjutkan sebagai current node untuk memulai kembali proses dari algoritma A*. 12. Apakah current node sudah sama dengan start node? Proses ini adalah tahap pertama dari algoritma backtrack. Proses ini merupakan pengecekan apakah current node adalah start node atau bukan. Jika current node bukan start node, maka current node akan diproses oleh algoritma backtrack. Jika current node adalah start node, maka algoritma selesai karena sudah mendapatkan shortest path dari algoritma A*. 13. Tambahkan current node ke dalam link list dari actual path Pada proses ini tambahkan current node ke dalam link list dari shortest path. Nodenode yang terdapat pada link list akan menjadi shortest path dari algoritma A*. 14. Cek semua node yang berada pada done queue Pada tahap ini akan dilakukan pengecekan terhadap node-node yang terdapat pada done queue untuk dilakukan proses backtrack. Node yang di cek adalah destination node. 15. Apakah current node sudah sama dengan destination node pada done queue? Pada tahap ini, proses backtrack dilakukan. Pada proses ini, dilakukan pengecekan terhadap node yang sudah diproses pada tahap 14, apakah current node adalah destination node. Jika ya, maka node tersebut akan di proses pada tahap selanjutnya. Jika tidak, maka node akan dilakukan pengecekkan kembali terhadap node yang ada di dalam done queue pada tahap 14. 16. Set source node dari destination node sebagai current node Setelah ditemukan destination node yang sama dengan current node, source node dari destination node akan menjadi current node dan akan diproses kembali pada algoritma backtrack. 17. Hapus node pada done queue yang menjadi actual path Sebelum algoritma backtrack diulang kembali, source node yang menjadi current node dengan destination node pada done queue perlu dihapus. Hal ini dilakukan supaya node tersebut tidak di cek kembali.
18. Selesai Proses akan selesai apabila current node adalah start node. Hal ini menandakan bahwa algoritma backtrack telah selesai. Semua node dalam linked list merupakan solusi shortest path yang diberikan oleh algoritma A*.
Dalam pengujian algoritma greedy best-first search dan A*, digunakan peta provinsi Jawa Tengah sebagai media perbandingan. Berikut ini merupakan gambaran peta yang digunakan dalam pengujian algoritma :
Gambar 3 Graf Peta Jawa Tengah
Gambar 3 merupakan rancangan graf dari peta Jawa Tengah yang akan digunakan dalam aplikasi untuk membandingkan algoritma greedy best-first search dengan A*. Graf dibuat dari peta provinsi Jawa Tengah. Terdapat 20 nodes yang merupakan kota-kota di Jawa Tengah. Koordinat bujur (X) dan lintang (Y) dari setiap node didapatkan dari aplikasi Google Earth dan digunakan untuk menentukan heuristic cost dengan metode straight line distance. Pada graf juga terdapat 31 edges tidak berarah yang menghubungkan node-node dengan bobot masing-masing yang sudah ada pada gambar 3.3. Panjang setiap edge didapatkan dari aplikasi Google Maps . Berikut ini merupakan tabel koordinat dan nilau heuristikdari setiap node dari graf peta Jawa Tengah:
Tabel 1 Koordinat Kota Kota
Koordinat X
Y
Boyolali
110°35' BT
07°32' LS
Brebes
109°03' BT
06°52' LS
Cilacap
109°00' BT
07°43' LS
Demak
110°38' BT
06°54' LS
Kebumen
109°40' BT
07°42' LS
Kroya
109º 14' BT
07º 39' LS
Magelang
110º 12' BT
07º 30' LS
Pekalongan
109°40' BT
06°53' LS
Pemalang
109°23' BT
06°53' LS
Purbalingga
109º 22' BT
07º 25' LS
Purwodadi
110°55' BT
07°07' LS
Purwokerto
109°14' BT
07°28' LS
Rembang
111°21' BT
06°42' LS
Salatiga
110°30' BT
07°19' LS
Semarang
110º 24' BT
07º 00' LS
Slawi
109º 08' BT
06º 59' LS
Sragen
111º 01' BT
07º 27' LS
Temanggung
110º 08' BT
07º 22' LS
Tegal
109º 10' BT
06º 54' LS
Wonosobo
109º 54' BT
07º 24' LS
Tabel 2 Nilai Heuristik
Cilacap
Demak
Kebumen
Kroya
Magelang
Pekalongan
Pemalang
Purbalingga
Purwodadi
Purwokerto
Rembang
Salatiga
Semarang
Slawi
Sragen
Temanggung
Tegal
Wonosobo
Boyolali Brebes Cilacap Demak Kebumen Kroya Magelang Pekalongan Pemalang Purbalingga Purwodadi Purwokerto Rembang Salatiga Semarang Slawi Sragen Temanggung Tegal Wonosobo
Brebes
Start Nodes
h(n)
Boyolali
Goal Nodes
0 189 180 71 105 153 43 127 154 138 66 152 128 26 61 175 49 54 175 78
189 0 96 179 117 90 148 69 37 71 212 70 260 171 153 16 232 134 13 113
180 96 0 206 75 27 137 120 103 53 229 38 289 175 177 84 230 134 94 107
71 179 206 0 141 179 83 109 141 154 36 170 84 49 28 169 75 77 165 100
105 117 75 141 0 49 64 92 97 46 159 55 221 103 114 101 155 64 106 42
153 90 27 179 49 0 110 99 88 30 202 20 262 148 151 76 202 106 85 80
43 148 137 83 64 110 0 92 115 94 95 109 158 39 60 134 92 16 135 35
127 69 120 109 92 99 92 0 32 69 142 82 191 106 83 61 165 75 56 64
154 37 103 141 97 88 115 32 0 60 174 68 223 135 115 30 198 100 24 82
138 71 53 165 46 30 94 69 60 0 180 16 238 128 126 55 186 86 62 60
66 212 229 36 159 202 95 142 174 180 0 196 62 55 58 201 46 95 198 121
152 70 38 170 55 20 190 82 68 16 169 0 254 144 142 55 201 102 64 75
128 206 289 84 221 262 158 191 223 238 62 254 0 118 112 252 92 156 247 182
26 171 175 49 103 148 39 106 135 128 55 144 118 0 37 159 60 41 158 68
63 153 177 28 114 151 60 83 115 126 85 142 112 37 0 143 86 51 139 72
175 16 84 169 101 76 134 61 30 55 201 55 252 159 143 0 219 121 10 98
49 232 230 75 155 202 92 165 195 186 46 201 92 60 86 219 0 100 218 126
54 134 134 77 64 106 16 75 100 86 95 102 156 41 51 121 100 0 121 26
175 13 94 165 106 85 135 56 24 62 198 64 247 157 139 10 218 121 0 100
78 113 107 100 42 80 35 64 82 60 121 75 182 68 72 98 126 26 100 0
Berikut ini merupakan hasil dari pengujian algoritma : Tabel 3 Waktu Berpikir Algoritma Total
Start Node
Rata - Rata
G
A
G
A
A
2,7147
3,3858
0,1429
0,1782
B
3,3151
3,7146
0,1745
0,1955
C
3,5067
4,1257
0,1846
0,2171
D
3,0429
3,3192
0,1602
0,1747
E
2,5350
2,8374
0,1334
0,1493
F
2,9280
3,8704
0,1541
0,2150
G
2,4921
3,0066
0,1312
0,1582
H
2,3639
2,6133
0,1244
0,1375
I
2,4623
2,6720
0,1296
0,1406
J
2,5282
2,7420
0,1331
0,1443
L
3,5815
3,8426
0,1885
0,2022
M
2,6485
3,6511
0,1394
0,1922
N
3,7721
4,2651
0,1985
0,2245
O
2,5755
2,9083
0,1356
0,1531
P
2,3674
2,6551
0,1246
0,1397
R
2,7122
3,1826
0,1427
0,1675
S
2,8427
3,2368
0,1496
0,1704
T
2,2071
3,1989
0,1162
0,1684
U
2,7892
3,0988
0,1468
0,1631
V
2,3693
2,9627
0,1247
0,1559
Tabel 4 Hasil Keunggulan Algoritma Greedy Best-first Search
Draw
A*
0%
68,68%
31,32%
Berdasarkan hasil dari perbandingan algoritma greedy best-first search dengan A* pada tabel 4.21 dan tabel 4.22, dapat disimpulkan bahwa algoritma greedy best-first search lebih unggul dari segi waktu berpikir, sedangkan algoritma A* lebih unggul dari segi lintasan terpendek yang dilalui. Hal ini disebabkan karena algoritma greedy best-first search hanya melihat heuristic cost dari node yang dilalui, sedangkan algoritma A* menghitung heuristic cost dan actual cost dari setiap node yang dilalui, sehingga algoritma A* membutuhkan waktu yang lebih lama daripada algoritma greedy bestfirst search untuk menentukan lintasan yang dilalui, namun algoritma A* dapat memberikan lintasan yang lebih optimal daripada algoritma greedy best-first search. Pada tabel 4.22, algoritma A* dan greedy best-first search menghasilkan panjang lintasan yang sama sebanyak 68,68%. Hal ini disebabkan karena nilai heuristik dari node yang dilalui hampir sama dengan nilai actual cost-nya. Sehingga, algoritma greedy best-first search menjadi optimal.
SIMPULAN DAN SARAN Berdasarkan hasil dari perbandingan yang telah dilakukan, maka dapat ditarik beberapa simpulan sebagai berikut : a.
Di dalam menentukan lintasan terpendek, algoritma greedy best-first search hanya menghitung nilai dari (heuristic cost) saja, sedangkan algoritma A* menghitung nilai (heuristic cost) dan (actual cost ).
b.
Algoritma greedy best-first search memberikan rata-rata waktu berpikir lebih cepat daripada algoritma A*, sedangkan algoritma A* memberikan lintasan lebih pendek daripada algoritma greedy best-first search dalam menentukan lintasan pada peta.
c.
Algoritma greedy best-first search hanya melihat kemungkinan lintasan terpendek di depannya saja, sedangkan algoritma A* melihat berbagai kemungkinan lintasan terpendek yang ada.
Pada penelitian ini masih terdapat beberapa hal lain perlu dikembangkan. Saran-saran yang dapat diberikan untuk perkembangan penelitian lebih lanjut yaitu : a.
Karena banyaknya algoritma pathfinding yang ada, dibutuhkan perkembangan lebih lanjut untuk dilakukan perbandingan antar algoritma. Sehingga, pada akhirnya dapat ditemukan satu algoritma yang paling unggul dibandingkan dengan algoritma yang lain.
b.
Berdasarkan fungsi heuristik yang digunakan dalam penelitian ini, yaitu Straight-line Distance, penelitian selanjutnya dapat menggunakan fungsi heuristik lain yang ada.
c.
Pada penelitian selanjutnya, dapat dilakukan perbandingan yang lebih bervariasi. Perbandingan dapat dilakukan untuk meninjau berbagai aspek yang dapat dibandingkan agar mendapatkan hasil yang lebih spesifik selain waktu berpikir dan panjang lintasan yang dilalui.
REFERENSI Hardianto. (2013). Implementasi Algoritma Heuristik untuk optimisasi rute terpendek. Jurnal Teknologi Informasi dan Komunikasi. 4(2): 79-88. Russel, S., & Norvig, P. (2010). Artificial Intelligence: A Modern Approach. New Jersey: Prentice Hall.
RIWAYAT HIDUP Christophorus Yohannes Suhaili lahir di kota Jakarta pada 15 Maret 1993. Penulis menamatkan pendidikan S1 di BINUS University dalam bidang Ilmu Komputer pada tahun 2015. Penulis aktif di dalam organisasi HIMTI sebagai activist. Mendy Irawan lahir di kota Jakarta pada tanggal 1 April 1993. Penulis menamatkan pendidikan S1 di BINUS University dalam bidang Ilmu Komputer pada tahun 2015. Raja Muhammad Fahrizal lahir di kota Jakarta pada tanggal 11 Mei 1993. Penulis menamatkan pendidikan S1 di BINUS University dalam bidang Ilmu Komputer pada tahun 2015.
