Nathanael, Hans Sean (2024) Perbandingan Kinerja Algoritma Convex Hull Trick dan Knuth-Yao Quadrangle Inequality dalam Penyelesaian Permasalahan Studi Kasus SPOJ 40468 Mines of Moria II. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025201019-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025201019-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (4MB) | Request a copy |
Abstract
Permasalahan yang diangkat pada tugas akhir ini adalah permasalahan “Mines of Moria II” yang terdapat pada situs SPOJ. Pada permasalahan ini, terdapat sekumpulan batu yang harus diangkut dengan kereta-kereta tambang. Jumlah kereta tambang yang dapat digunakan tidak terbatas, namun semua kereta tambang memiliki sebuah nilai angkut optimal yang sama dan hanya dapat mengangkut batu yang berurutan. Nilai angkut optimal dan total berat yang diangkut memengaruhi nilai sebuah kereta tambang. Hasil akhir yang diminta adalah nilai total terkecil dari semua kereta tambang. Permasalahan utama dalam merancang solusi adalah harus memenuhi batasan waktu yang diberikan pada situs SPOJ. Pada tugas akhir ini dibahas analisis, perancangan, dan implementasi solusi yang memenuhi batasan waktu permasalahan.
Tugas akhir ini mengulas penerapan metode pemrograman dinamis dengan teknik optimasi Convex Hull Trick dan Knuth-Yao Quadrangle Inequality untuk mencari nilai total terkecil dari semua kereta tambang yang digunakan. Teknik optimasi digunakan untuk mempercepat solusi agar memenuhi batasan waktu. Solusi Convex Hull Trick memiliki kompleksitas waktu Ο(TN), sedangkan solusi Knuth-Yao Quadrangle Inequality memiliki kompleksitas waktu Ο(TN logN ).
Berdasarkan hasil uji coba pada situs SPOJ, solusi Convex Hull Trick lebih efisien dibandingkan dengan solusi Knuth-Yao Quadrangle Inequality. Solusi Convex Hull Trick menempati peringkat pertama pada situs SPOJ dengan waktu rata-rata 0,203 sekon dan memori rata-rata 5,2 MB, sedangkan solusi Knuth-Yao Quadrangle Inequality memiliki waktu rata-rata 0,285 sekon dan memori rata-rata 19,0 MB.
====================================================================================================================
The problem raised in this thesis is the “Mines of Moria II” problem from SPOJ website. In this problem, there are a group of stones that must be carried by minecarts. An unlimited number of minecarts can be used, but all minecarts have the same optimal load value and can only carry consecutive stones. The value of optimal load and total weight of stones carried influence the score of a minecart. Final objective is to calculate smallest possible total score of all minecarts. The main problem is designing a solution that must meet the time constraints given on the SPOJ website. This thesis discusses analysis, design, and implementation of solutions that meet the time constraints of the problem.
This thesis reviewed on the application of dynamic programming methods with Convex Hull Trick and Knuth-Yao Quadrangle Inequality optimization techniques to find the smallest total value of all minecarts used. Optimization techniques are used to speed up the solution to meet time constraint. The Convex Hull Trick solution has Ο(TN) time complexity, while the Knuth-Yao Quadrangle Inequality solution has Ο(TN logN ) time complexity.
Based on the test results on the SPOJ websites, the Convex Hull Trick solution is more efficient than the Knuth-Yao Quadrangle Inequality solution. The Convex Hull Trick solution ranked first on SPOJ website with an average time of 0.203 second and average memory of 5.2 MB, while the Knuth-Yao Quadrangle Inequality solution had an average time of 0.285 second and average memory of 19.0 MB.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Convex Hull Trick, Knuth-Yao Quadrangle Inequality, Pemrograman Dinamis, Dynamic Programming |
| Subjects: | Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.83 Dynamic programming |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Hans Sean Nathanael |
| Date Deposited: | 26 Jul 2024 06:27 |
| Last Modified: | 26 Jul 2024 06:27 |
| URI: | http://repository.its.ac.id/id/eprint/109070 |
Actions (login required)
 |
View Item |