Computer File

Implementasi solusi V-Shortest Path Problem dalam pembuatan pathfinder (metode brute force dan metode variasi KSP)

V-Shortest Path Problem, merupakan bentuk variasi pencarian jalur terpendek, yang mengunjungi V tempat dari tempat asal menuju tempat tujuannya. V akan mencakup juga tempat asal dan tempat tujuannya. Skripsi ini dibuat untuk mempelajari lebih lanjut tentang V-Shortest Path Problem beserta pencarian solusinya. Selain itu, solusi VSP akan diimplementasikan untuk membuat sebuah aplikasi pathfinder sederhana. Dalam karya tulis ini, pencarian solusi VSP akan menggunakan dua metode, yaitu metode brute force dan metode usulan. Metode brute force akan mencari solusi VSP dengan mengacu pada definisi VSP itu sendiri, yaitu dengan mencari semua kemungkinan jalur dari tempat asal ke tempat tujuan yang melalui V tempat, lalu mengambil jalur dengan jarak terkecil. Metode usulan , akan memanfaatkan ide dari algoritma K-Shortest Path, yaitu algoritma Yen’s. Ide yang diambil dari algoritma Yen’s adalah pemanfaatan optimal substructure, yaitu pemanfaatan sub-jalur dari jalur terpendek untuk mencari kemungkinan jalur alternatif yang melewati V tempat. Jalur terpendek akan didapat dengan memanfaatkan algoritma Dijkstra. Solusi yang dihasilkan dua metode selanjutnya akan diimplementasikan menjadi aplikasi pathfinder dengan bahasa pemrograman fungsional. Hasil dari penelitian ini menunjukan bahwa kedua metode yang diimplementasikan dapat mengembalikan solusi VSP. Ada perbedaan hasil yang dikeluarkan oleh dua metode. Dikarenakan metode brute force lebih akurat dalam menghasilkan solusi VSP, maka metode brute force yang akan dipakai sebagai tolak ukur ketepatan hasil solusi VSP. Hasil perbandingan dari 150 kasus menunjukan bahwa hanya 23,33% dari hasil metode usulan yang tepat sama dengan hasil yang diperoleh dari metode brute force. Kesimpulannya, VSP adalah sebuah permasalahan variasi dari permasalahan pencarian jalur terpendek yang mencari sebuah jalur terpendek yang melalui V tempat dalam satu perjalanan. VSP ini dapat diselesaikan dengan menggunakan metode brute force dan metode usulan yang memanfaatkan ide algoritma yang sudah ada, seperti algoritma Dijkstra dan algoritma Yen. Saran untuk penelitian selanjutnya adalah untuk mempelajari penelusuran jalur dengan algoritma Yen untuk mengoptimalkan hasil lebih lanjut.

Kata-kata kunci: jalur terpendek, V-shortest path problem, VSP, brute force, graf, algoritma Yen's, algoritma Djikstra, fungsional, Haskell, aplikasi, pathfinder.

Ketersediaan

Informasi Detail

Judul Seri

No. Panggil

INFO PRA i/16

Penerbit

Bandung : Program Studi Teknik Informatika Fakultas Teknologi Informasi dan Sains - UNPAR., 2016

Deskripsi Fisik

xx, 70 p. : il. ; 30 cm.

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

1379 - FTIS

Pernyataan Tanggungjawab

Evans Pratama

Versi lain/terkait

Lampiran Berkas

Komentar