Számítástudományi és Információelméleti Tanszék
Témakiírás
Hogyan csomagoljon egy csomagküldő?
Az online vásárlások széles körű elterjedésével előkerült az
optimális csomagolás problémája. Adott néhány termék és egy doboz.
Belefér-e egyátalán? Ha többféle doboz méret van, akkor melyik a
legkisebb, amibe belefér? Esetleg
érdemes több, kisebb dobozba csomagolni?
Ezek a problémák a jól ismert és sokat kutatott Ládapakolás feladat
3 dimenziós változatai, amiről közismert, hogy NP-teljes. Ezért
várhatóan nem lehet megtalálni az optimális megoldást polinom
időben, helyette közelítő megoldásokat
érdemes keresni.
A hallgató feladata, hogy az irodalomban megtalálható különböző
algoritmusokat megvizsgálja, összehasonlítja abból a szempontból,
hogy melyiket érdemes használni egy kisvállalkozásnak. Az
algoritmusok egy részének elérhető
implementációja is, különböző programozási nyelveken, fejlesztői
rendszereken. Elvárás a hallgatótól, hogy tudja ezeket kezelni. Az
összehasonlítás módszere is kidolgozásra vár. Hogyan generáljunk
realisztikus inputokat?
Munkanyelv: angol.
Dr. Katona Gyula Y.
egyetemi docens
kiskat@cs.bme.hu