Adi, Ibrahim Tamtama (2020) Implementasi Algoritma Pencarian Rute Berbasis Top-K Shortest Path With Diversity (KSPD) Dengan Tag Sesuai Preferensi Pengguna. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000018-Undergraduate_Thesis.pdf Download (1MB) | Preview |
Abstract
Shortest path merupakan rute dengan jarak atau total bobot terkecil dari suatu vertex ke vertex lain pada suatu graf. Masalah shortest path sendiri merupakan masalah umum yang sering ditemukan pada kehidupan sehari-hari. Banyak sekali algoritma yang dapat digunakan untuk mencari shortest path pada sebuah graf. Setiap jenis graf memiliki algoritma yang optimal dalam menyelesaikan masalah ini.
Tujuan dari pembuatan tugas akhir ini adalah untuk mendesain algoritma yang dapat mencari k shortest path. Namun tidak seperti k shortest path pada umumnya yang hanya memperhatikan jarak, algoritma ini dapat memberikan shortest path yang memenuhi kebutuhan dan keinginan pengguna dengan adanya tag-tag yang diberikan pengguna sebagai parameter tambahan dalam pencarian shortest path. Jadi, nantinya hasil dari algoritma ini adalah rute-rute dengan jarak terkecil dengan semua tag terpenuhi.
========================================================================================================================
Shortest path is a path with the shortest distance or smallest total weight between two vertex on a graph. The shortest path problem itself is a common problem that is often found in everyday life. There are many algorithms that can be used to find the shortest path on a graph. Each type of graph has its own algorithm in solving the problem optimally.
Goals of this research is to design an algorithm that can find k shortest path. But unlike the k shortest path in general that only considers distance, this algorithm can provide a shortest path that meets the needs and desires of the user with the tags given by the user as an additional parameter in searching the shortest path. So, the result of this algorithm will be the shortest paths with all tags fulfilled.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Adi i-1 • Adi, Ibrahim Tamtama |
| Uncontrolled Keywords: | Shortest Path, Path Finding, Road Network |
| Subjects: | H Social Sciences > HE Transportation and Communications > HE336.R68 Route choice Q Science > QA Mathematics > QA76.758 Software engineering Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Ibrahim Tamtama Adi |
| Date Deposited: | 04 Aug 2020 09:26 |
| Last Modified: | 10 May 2023 14:10 |
| URI: | http://repository.its.ac.id/id/eprint/76540 |
Actions (login required)
 |
View Item |