Hibridizacija požrešnih algoritmov in hitrega urejanja

Vehovec, Nina (author), Mihelič, Jurij (mentor)

Požrešna metoda je ena izmed najbolj uporabljenih tehnik pri načrtovanju algoritmov, za katero obstaja več vrst optimizacij. Naša ideja je bila optimiziranje požrešnih algoritmov s pomočjo algoritma hitrega urejanja. V algoritem hitrega urejanja smo vstavili požrešni algoritem. Na tak način ustvarjen hibridni algoritem, lahko na določenih primerih deluje precej hitreje kot navadni požrešni algoritem. Hibridizacijo smo preizkusili na problemih preprostega nahrbtnika, menjave kovancev in izbora aktivnosti ter na Kruskalovem algoritmu in pri razvrščanju poslov v delavnici z enim strojem. Hibridni algoritem je deloval bolje od navadnega požrešnega algoritma pri preprostem problemu nahrbtnika in pri problemu menjave kovancev.

• Language: Slovenian
• Keywords: požrešno, nahrbtnik, posli, aktivnosti, Kruskal, kovanci, urejanje, hibridizacija, algoritmi
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-95139
• Publication date in RUL: 15.09.2017

Secondary language

• Language: English
• Title: Hybridization of greedy algorithms and quicksort

Abstract

The greedy method is one of the most commonly used techniques in algorithm design and there are many different optimizations available. This thesis presents one of them. Our idea for optimization was improving the running time of greedy algorithms with the help of the quicksort algorithm. We integrated the greedy algorithm into quicksort to produce a hybrid algorithm, which can solve certain problems significantly faster than the normal greedy algorithm. In the thesis we chose to test hybridization on the activity-selection problem, the fractional knapsack problem, the coin changing problem, Kruskal's algorithm and unit-task scheduling. We experimentally confirmed that hybrid algorithms (do) indeed perform better with the coin changing problem and the fractional knapsack problem.

• Keywords: greedy, hybridization, algorithms, activity-selection, knapsack, Kruskal, coin-changing, quicksort, unit-tasks