ANALISIS PERBANDINGAN ALGORITMA DIJKSTRA DAN A* DALAM MENENTUKAN JALUR KELUAR TERCEPAT PADA SIMULASI LABIRIN
No Thumbnail Available
Date
2018-05-19
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Permasalahan jalur terpendek (Shortest Path Problem) merupakan salah satu
topik permasalahan matematika yang paling popular dalam menjadi topik
penelitian. Permasalahan jalur terpendek merupakan bagaimana suatu algoritma
dapat menemukan jalur terpendek yang harus ditempuh dalam sebuah peta berjalur
(graf) dari titik awal menuju titik akhir yang telah ditentukan. Algoritma Dijkstra
dan A* merupakan algoritma pencarian jalur terpendek yang sampai saat ini masih
umum digunakan. Kedua algoritma tersebut memiliki cara kerja pencarian jalur
terpendek yang hampir sama, dengan tahap pengerjaan yang cukup sederhana.
Ketika dihadapkan pada graf yang sederhana, kinerja algoritma Dijkstra dan A*
cenderung sama. Namun, jika dihadapkan kepada graf yang besar dan memiliki
banyak kemungkinan jalur yang dapat diambil, kinerja kedua algoritma tersebut
akan berbeda. Graf yang memiliki jalur-jalur yang rumit salah satu contohnya
adalah sebuah labirin. Labirin dapat memiliki banyak kemungkinan jalur yang
dapat diambil dengan ukuran dan kondisi jalur yang tidak memiliki batasan, seperti
lalu lintas, arah jalur, keadaan jalur, dan batasan lainnya.
Penelitian ini dilakukan untuk mengetahui kinerja algoritma Dijkstra dan A*
dalam menentukan jalur keluar terpendek pada berbagai labirin. Terdapat 12 labirin
berukuran 512 x 512 sel yang diuji coba untuk mencari jalur keluar terpendek. Pada
penelitian, dikembangkan sebuah perangkat lunak untuk melakukan uji coba
algoritma Dijkstra dan A* dalam mencari jalur terpendek pada setiap labirin.
Berdasarkan penelitian, algoritma Dijkstra cenderung memiliki kinerja yang lebih
buruk dibandingkan algoritma A* dengan perbandingan waktu proses pencarian
1,95:1. Hal ini disebabkan oleh proses kerja algoritma Dijkstra yang melakukan
pengecekan terhadap seluruh kemungkinan jalur, berbeda dengan algoritma A*
yang melakukan pengecekan jalur secara terarah menuju titik akhir (titik tujuan).
Description
Keywords
Jalur terpendek, Algoritma, Dijkstra