Kényszerkielégítési problémák megoldása

OData támogatás
Konzulens:
Dr. Mann Zoltán Ádám
Számítástudományi és Információelméleti Tanszék

A kényszerkielégítési probléma (constraint satisfaction problem) számos kombinatorikai probléma természetes, kézenfekvő modellje, ezért sok különböző algoritmus ismert kényszerkielégítési problémák megoldására. Ezek közül az egyik leggyakrabban alkalmazott egzakt algoritmus a visszalépéses algoritmus. Mivel a kényszerkielégítési probléma NP-teljes, ezért az ismert egzakt algoritmusok futásideje a legrosszabb esetben igen gyorsan nő, a gyakorlatban azonban sok problémát hatékonyan tudunk kezelni. Fontos tehát olyan heurisztikákat, gyorsításokat találni, amelyek alkalmazásával a visszalépéses keresés hatékonysága anélkül növelhető, hogy egzakt volta sérülne.

Szakdolgozatom a következőekre terjed ki:

• Bemutatom a visszalépéses algoritmust és ennek ismert heurisztikáit és gyorsításait. Ezeket leíró jelleggel és formálisan is definiálom. Bemutatom a gyakori újraindítás technikáját és a visszalépéses keresés alapú saját best-first-search algoritmusomat.

• Bemutatom az általam elkészített keretrendszer felépítését, amelyben az algoritmusokat implementálom. Az implementáció során többek közt megvalósítom a konfliktusvezérelt visszalépést, a gyakori újraindítást és a előzőekben leírt BFS-jellegű bejárást a visszalépéses algoritmus segítségével.

• Összehasonlítom az elkészített algoritmusok eredményeit különböző valós és véletlenszerű, megoldható és megoldhatatlan problémapéldányokra, és következtetéseket vonok le a leírt gyorsítások, és kiemelten a gyakori újraindítás és a BFS-jellegű bejárás hatékonyságára vonatkozólag.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.