ANALISIS PERBANDINGAN ALGORITMA DIJKSTRA DAN A* DALAM MENENTUKAN JALUR KELUAR TERCEPAT PADA SIMULASI LABIRIN

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

Citation