Indra, Saputra (2015) Implementasi algoritma pencarian K solusi terbaik untuk permasalahan Knapsack. Undergraduate thesis, Institut Teknology Sepuluh Nopember.
Preview |
Text
5111100066-Undergraduate_Thesis.pdf Download (1MB) | Preview |
Abstract
Permasalahan knapsack adalah permasalahan klasik yang ada dalam bidang algoritma. Biasanya, dalam permasalahan knapsack, tujuan penyelesaian hanyalah mencari sebuah solusi terbaik dari semua kombinasi yang ada. Namun, pada kenyataannya, seringkali dibutuhkan beberapa solusi terbaik yang dapat digunakan sebagai rekomendasi.
Pencarian beberapa solusi terbaik pada permasalahan knapsack masih jarang diteliti. Beberapa algoritma yang diusulkan terbukti dapat mencari solusi terbaik tetapi memiliki waktu eksekusi yang sangat lambat. Beberapa lainnya memiliki waktu eksekusi yang cepat tetapi tidak dapat dipastikan bahwa hasilnya valid.
Tugas Akhir ini mengimplementasi pencarian beberapa solusi terbaik pada permasalahan knapsack dengan metode Branch and Bound. Metode Branch and Bound dipilih karena terbukti mampu menyelesaikan permasalahan kombinasi dengan waktu eksekusi yang cepat.
Hasil uji coba menunjukkan bahwa metode Branch and Bound mampu menyelesaikan permasalahan yang diajukan. Hasil uji coba kebenaran membuktikan bahwa metode Branch and Bound mampu memberikan hasil yang valid. Hasil uji coba kinerja membuktikan bahwa metode Branch and Bound mampu menyelesaikan 7 dari 8 kelas dataset yang tersedia.
==============================================================================================
Knapsack problem is a classic problem in the field of algorithm. Usually, in the knapsack problem, the main purpose is determining the best solution of all possible solutions. However, in fact, it needs more than one best solution that can be used as a recommendation.
Determining several best solutions of knapsack problem is still rarely discovered. Some proposed algorithms proved to be able to determine some best solutions but the execution time was very slow. The others have a rapid execution time but they can’t be guaranted that the result are valid.
This undergraduate thesis implements the Branch and Bound method to determine several best solutions of knapsack problem. Branch and Bound is chosen because it was proved to be able to solve combinational problem in no time.
The trial result shows that Branch and Bound method is able to solve the proposed problem. The trial result of correctness demonstrates that the Branch and Bound method is able to provide a valid result. The trial result of performance demonstrates that the Branch and Bound method is able to solve 7 out of 8 classes of datasets.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Sap i |
| Uncontrolled Keywords: | Branch and Bound; K Solusi Terbaik; Permasalahan Knapsack |
| Subjects: | Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | - Taufiq Rahmanu |
| Date Deposited: | 02 Oct 2019 03:43 |
| Last Modified: | 02 Oct 2019 03:43 |
| URI: | http://repository.its.ac.id/id/eprint/70947 |
Actions (login required)
 |
View Item |