Globposzt

Ezen a vidám április elejei napon egy érdekes alkalmazásról írok. A Globulation nevű real-time (valós idejű) stratégiai alkalmazás valóságközelibb, mint a turn-based alkalmazások. Van offline, valamint  hálózatban futó változata. Több algoritmus van mögötte, különböző módokon próbálnak optimalizálni. Kétféle egység kaphat utasításokat, amelyeket az alkalmazás automatikusan oszt ki az egyes egységeknek, az egyik a worker, a másik a warrior, nevük is jelzi funkcióbeli különbségüket. Amennyiben az adott egység sérült vagy erőforráshiány lép fel, a feladatot visszautasíthatja. A cél  a presztízspontok mennyisége valamint az elfoglalt terület maximalizálása. A célfüggvény összetettsége miatt több optimális stratégia létezik, ez okozza a feladat nehézségét. A versenyképességi hányadosra éles korlát nem ismert a számítás komplexitása miatt, bár valójában kevesen foglalkoztak még a kérdéssel. Legtöbb esetben nem optimalizálni próbálnak, hanem egy adott célfüggvényértéket elérni, ennek elérése esetén nem növelik tovább a célfüggvényt, ilyen megközelítésben a versenyképességi hányadost számolni nincs értelme. Más célfüggvény vizsgálata merülhet fel ilyenkor, például az adott terület/pontérték eléréséhez szükséges idő, természetesen ennek a minimalizálása a cél. Sem éles versenyképességi korlátok, sem approximációs algoritmusok nem ismertek erre a kérdésre sem.