Tanszéki konzulens: 

Strausz György associate professor Szoba: IE413 Tel.: +36 1 463-4394 Email: strausz (*) mit * bme * hu

Önálló labor téma 1 vagy 2 BSc hallgató számára

Konzulens: Kovács András
E-mail: akovacs@sztaki.hu 
Web: www.sztaki.hu/~akovacs 

Az élet különböző területein előforduló tervezési, optimalizálási feladatok gyakori jellemzője, hogy a megoldásnak sokféle műszaki, gazdaságossági, és egyéb feltételnek kell megfelelnie. Ezek a feltételek ráadásul gyakran változnak, más-más szituációban más-más feltételeket kell figyelembe venni.

A fentiekre jó példát szolgáltatnak a pakolási feladat különböző változatai, pl. a konténer rakodási feladat. A matematikai alapfeladat 3 dimenziós testek átlapolás nélküli elhelyezése egy befoglaló alakzatban. A gyakorlatban viszont sok más követelmény is felbukkanhat:

• - a dobozoknak nem szabad maguktól leborulniuk;
• - egyes dobozok megsérülhetnek, ha túl nagy súly kerül rájuk;
• - ha az egyes doboznak más-más a célállomása, akkor adott sorrendben kipakolhatóknak kell lenniük a - - konténerből más dobozok ki-be rakodása nélkül is;
• - az azonosító címkéknek láthatónak kell lenniük;
• - a rakomány súlypontja egy meghatárzott régióban kell, hogy legyen, stb. 

Ilyen feladatok modellezésére és megoldására ígéretes megközelítés a korlátozás programozás, mely a mesterséges intelligencia és az operációkutatás területéről származó módszereket ötvözi. A megoldandó feladatot deklaratívan, azaz a döntési változók és a rájuk vonatkozó korlátok felsorolásával modellezi, az így kapott modellt pedig egy általános korlátozás-alapú megoldó szoftver automatikusan megoldja. A feladat változása esetén elegendő a tömör, deklaratív modellt módosítani. Mindazonáltal, ha a cél egy bonyolult feladat gyors megoldása, akkor érdemes a megoldón belül futó algoritmusok, különféle keresési és következtetési módszerek részleteiben is elmerülni, és a feladat igényeinek megfelelően módosítani azokat.

A félév során a cél a pakolási feladat egy formális modelljének a definíciója, egy választott korlátozás-alapú megoldó megismerése, abban a feladat deklaratív modelljének az elkészítése. Különböző megoldási eljárásokkal fogunk kísérletezni, és néhány új, a feladathoz illeszkedő algoritmust fogunk fejleszteni.

 Szükséges előismeretek: algoritmuselméleti alapok, C++ vagy Java programozási nyelv, angol szövegértés.