Novian, Dicksen Alfersius (2023) Penghitungan Jarak Terpendek Antara Dua Titik pada Labirin Grid Dua Dimensi Berbasis Algoritma Dial's: Studi Kasus SPOJ 40642 CHIPSLL - Chips Challenge. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 05111940000076-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
05111940000076-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2025. Download (3MB) | Request a copy |
Abstract
Permasalahan dalam tugas akhir ini adalah SPOJ 40642 CHIPSLL – CHIPS CHALLENGE. Dalam permasalahan ini dicari nilai shortest path weight dari ruangan awal ke ruangan tujuan pada implicit graph labirin berbentuk Grid 2D. Tugas akhir ini membahas solusi permasalahan menggunakan algoritma-algoritma single pair shortest path dengan berbagai metode. Adapun metode yang dibahas meliputi Dijkstra’s Shortest Path Algorithm, A* Pathfinding Algorithm, dan Dial’s Algorithm. Metode Dijkstra menggunakan struktur data min priority queue dalam menentukan ruangan mana yang akan dikunjungi selanjutnya. Metode A* Pathfinding Algorithm menambahkan nilai heuristic pada ruangan-ruangan sehingga memberi pengaruh dalam pemilihan gerakan. Kedua metode tersebut dapat memberi hasil yang benar namun efisiensi program dapat ditingkatkan. Dengan mengetahui karakteristik khusus graph, dapat digunakan Dial’s Algorithm. Dial’s Algorithm menggunakan karakteristik bahwa nilai shortest path weight antara dua titik memiliki nilai maksimum k dan edge pada graf tidak bernilai negatif. Dengan pengetahuan mengenai nilai k, maka dapat dibuat program dengan efisiensi waktu yang lebih baik daripada dua metode pertama yang telah disebutkan. Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan metode Dijkstra’s Shortest Path dan A* Pathfinding Algorithm mendapatkan verdict Time Limit Exceeded, sedangkan Dial’s Algorithm mendapat verdict accepted dan membutuhkan rata-rata waktu sebesar 2,116 sekon dan besar memori 46 MB
===================================================================================================================================
The problem raised in this thesis is SPOJ 40642 CHIPSLL – CHIPS CHALLENGE. In this problem, the value of shortest path weight from a starting room to a destination room within a 2D Grid labyrinth shaped implicit graph is sought. This thesis discusses the solution of said problem using single pair shortest path algorithms of various methods. Such methods are Dijkstra’s Shortest Path Algorithm, A* Pathfinding Algorithm, and Dial’s Algorithm. Dijkstra method uses a min priority queue data structure in order to determine which room to visit next. The A* Pathfinding method adds a heuristic value to the rooms and so, affects the selection of movements. Both methods are capable of producing correct results but the program’s efficiency can be improved upon. By knowing certain characteristics of the graph, Dial’s Algorithm can be used. Dial’s Algorithm uses the fact that the shortest path weight value between two points has a maximum of k and the edge of the graph does not have negative values. With the knowledge of k, a program that is more efficient than the two first methods mentioned can be made. Based on the trials from the given case study, the solution using the method of Dijkstra’s Shortest Path and A* Pathfinding Algorithm yields a Time Limit Exceeded verdict, while Dial’s Algorithm yields accepted verdict with average time of 2,116 seconds and memory of 46 MB
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | A* Pathfinding, Dial’s Algorithm, Dijkstra’s Shortest Path, Efisiensi Program, Graph, Single Pair Shortest Path. A* Pathfinding, Dial’s Algorithm, Dijkstra’s Shortest Path, Graph, Program’s Efficiency, Single Pair Shortest Path. |
| Subjects: | T Technology > T Technology (General) T Technology > T Technology (General) > T58.8 Productivity. Efficiency |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Dicksen Alfersius Novian |
| Date Deposited: | 02 Feb 2023 06:37 |
| Last Modified: | 02 Feb 2023 06:37 |
| URI: | http://repository.its.ac.id/id/eprint/96049 |
Actions (login required)
 |
View Item |