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

Simple item page
dc.contributor.advisorIno Suryana
dc.contributor.advisorErick Paulus
dc.contributor.authorRIO NUR ARDIANSYAH
dc.date.accessioned2024-05-30T06:50:58Z
dc.date.available2024-05-30T06:50:58Z
dc.date.issued2018-05-19
dc.description.abstractPermasalahan 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).
dc.identifier.urihttps://repository.unpad.ac.id/handle/kandaga/140810140024
dc.subjectJalur terpendek
dc.subjectAlgoritma
dc.subjectDijkstra
dc.titleANALISIS PERBANDINGAN ALGORITMA DIJKSTRA DAN A* DALAM MENENTUKAN JALUR KELUAR TERCEPAT PADA SIMULASI LABIRIN

Files

Original bundle
Now showing 1 - 5 of 12
No Thumbnail Available
Name:
S1-2018-140810140024-Cover.pdf
Size:
51.56 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
S1-2018-140810140024-Abstrak.pdf
Size:
14.52 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
S1-2018-140810140024-DaftarIsi.pdf
Size:
44.52 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
S1-2018-140810140024-Bab1.pdf
Size:
226.15 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
S1-2018-140810140024-Bab2.pdf
Size:
347 KB
Format:
Adobe Portable Document Format
Download

Collections

Teknik Informatika (S1)