| Proiect AA |
|
|
eLights2003: Scurta prezentare a algoritmului Un astfel de joc are o rezolvare care se preteaza a fi implementata cu metoda de programare Branch & Bound.
Aceasta metoda se aplica tuturor problemelor a coror rezolvare presupune u n timp de rulare indelungat, si pentru care nu se cunoaste un algoritm mai rapid de rezolvare. Acest tip de rezolvare si de ganidre a algoritmilor tine de discipline foarte avansate cum ar fi Cercetari Operationale si Intelegenta Artificiala. Rezolvarea problemei eLights se bazeaza pe realizarea arborelui de cautare a solutiei, arbore obtinut prin expandarea succesiva a nodurilor, prin acest procedeu obtinandu-se solutia optima. Trebuie precizat ca timpul de rulare creste exponential odata ce numarul de beculete creste, la fel ca si spatiul de memorie ocupat.
Construirea arborelui de solutii se face tinand cont ca de la o configuratie data de beculete se poate ajunge la n^2 configuratii ulterioare prin schimbarea starii feicarui bec in parte (de aici rezulta si complexitatea ridicata a algorimului).
|
