Skripsi
Kajian Masalah Optimasi Rute dengan Algoritma Dijkstra, Floyd-Warshall dan A Star
- Bagikan:
ABSTRAK
Kajian Masalah Optimasi Rute Dengan Algoritma Dijkstra, Floyd-Warshall Dan A Star
Maria Helensia Ina (1701030057), Pembimbing I, Dr. Siprianus S. Garak, M.Sc; Pembimbing II, Dr. Damianus Dao Samo
Optimasi merupakan proses untuk memaksimumkan atau meminimumkan sebuah fungsi dengan mempertimbangkan beberapa kendala yang ada agar diperoleh hasil yang paling optimal. Ada beberapa persoalan terkait optimasi, salah satunya persoalan optimasi rute. Optimasi rute merupakan merupakan pencarian rute yang paling optimal (rute terpendek) dengan mempertimbangkan kendala-kendala yang ada. Untuk menyelesaikan persoalan optimasi rute, dapat digunakan algoritma Dijkstra, Floyd-Warshall dan A Star.
Penelitian ini merupakan penelitian murni yang bertujuan menjelaskan cara kerja algoritma Dijkstra, Floyd-Warshall dan A Star serta mengetahui perbandingan dari algoritma-algoritma tersebut dalam menyelesaikan persoalan optimasi rute. Tahap penelitian ini dimulai dengan penentuan topik pembahasan yang akan dikaji, melakukan studi literatur, dan melakukan pengembangan teori.
Hasil penelitian menunjukkan bahwa algoritma Dijkstra, Floyd-Warshall dan A Star dapat membantu menyelesaikan masalah terkait optimasi rute. Algoritma Dijkstra bekerja dengan menggunakan strategi greedy, dimana pada setiap langkah dipilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih, dengan tujuan untuk mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada solusi terbaik. Algoritma Floyd-Warshall bekerja berdasarkan formulasi dynamic programing, dimana setiap langkahnya akan menghitung bobot terkecil dari semua rute yang menghubungkan sebuah pasang titik, dan melakukannya sekaligus untuk semua pasangan titik. Sedangkan, algoritma A Star bekerja dengan menggunakan fungsi heuristik jarak ditambah biaya (biasa dinotasikan dengan f(x)) untuk menentukan urutan di mana search-nya melalui node-node yang ada di pohon. Perbandingan dan performa dari ketiga algoritma memperlihatkan bahwa setiap algoritma memiliki keunggulan dan kekurangan di setiap kriterianya sehingga pemilihan algoritma dalam penyelesaian rute terpendek dapat disesuaikan dengan masalah penentuan rute yang dihadapi.
Kata Kunci: Optimasi Rute, Algoritma, Dijkstra, Floyd-Warshall, A Star
Detail Information
| Item Type | |
|---|---|
| Penulis |
Maria Helensia Ina - Personal Name
|
| Student ID |
1701030057
|
| Dosen Pembimbing |
Siprianus Suban Garak - 196512311992031027 - Dosen Pembimbing 1
|
| Penguji |
Drs. Dominikus Saka Kerans, M.Pd - 195708051986011001 - Ketua Penguji
Dr. Siprianus Suban Garak,M.Sc - 196512311992031027 - Penguji 1 Damianus Dao Samo - 198312312012121003 - Penguji 2 |
| Kode Prodi PDDIKTI |
84202
|
| Edisi |
Published
|
| Departement |
Pendidikan Matematika
|
| Kontributor | |
| Bahasa |
Indonesia
|
| Penerbit | UPT Perpustakaan Undana : Kupang., 2022 |
| Edisi |
Published
|
| Subyek | |
| No Panggil |
842.02 Ina K
|
| Copyright |
Individu Penulis
|
| Doi |