Mengembangkan Perancangan Algoritma Penghitungan Jarak Terpendek pada Stainer Tree dengan Pendekatan Kombinasi Metode Pemrograman Dinamis dan Greedy

D'Layla, Adifa Widyadhani Chanda and Riskynanda, Achmad Nashruddin (2024) Mengembangkan Perancangan Algoritma Penghitungan Jarak Terpendek pada Stainer Tree dengan Pendekatan Kombinasi Metode Pemrograman Dinamis dan Greedy. Project Report. [s.n.], [s.l.]. (Unpublished)

Text 5025201013_5025201021-Project_Report.pdf - Accepted Version Restricted to Repository staff only Download (5MB) | Request a copy

Abstract

Kerja Praktik ini membahas permasalahan pencarian Minimum Steiner Tree pada E-Olymp dengan kode 1445 berjudul Road Network. Inti permasalahan adalah menghitung jarak minimal untuk membangun jalan yang menghubungkan N pangkalan militer sehingga semua titik terhubung secara langsung maupun tidak langsung, dengan 1≤N≤10. Pertanyaan utama adalah bagaimana cara menghitung jarak minimal secara efisien untuk menghubungkan N pangkalan militer. Algoritma yang digunakan adalah Shortest Path Faster Algorithm (SPFA), yang menyelesaikan masalah single-source shortest path pada weighted graph G(V,E). SPFA berulang kali memilih vertex u ∈ V yang memiliki kemungkinan untuk terjadi relaksasi tanpa mencari vertex dengan perkiraan bobot minimal, sehingga cocok untuk menyelesaikan kasus Minimum Steiner Tree pada studi kasus E-Olymp 1445 – Road Network. Hasil penyelesaian permasalahan Steiner Tree menggunakan SPFA beserta Greedy dan Dynamic Programming akan didokumentasikan dalam jurnal ilmiah yang diharapkan dapat memberikan kontribusi bagi dunia akademik dan meningkatkan reputasi Teknik Informatika ITS, khususnya Lab Algoritma Pemrograman.

Item Type:	Monograph (Project Report)
Uncontrolled Keywords:	SPFA, Greedy, Steiner Tree
Subjects:	T Technology > T Technology (General)
Divisions:	Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	ADIFA WIDYADHANI CHANDA D’LAYLA
Date Deposited:	17 Jul 2024 00:37
Last Modified:	17 Jul 2024 00:37
URI:	http://repository.its.ac.id/id/eprint/108363

Actions (login required)

View Item