Problema era bineinteles o problema exponentiala, care putea fi rezolvata
fie prin backtracking, fie prin metode euristice. Rezolvarea cea mai buna
consta in imbinarea acestor 2 metode. Amintesc 2 euristici destul de bune:
1. Cand incercam sa punem o piesa, incepem cu pozitiile cele mai joase
(deci pentru care inaltimea cea mai mare la care s-a ajuns pana la
momentul respectiv este minima) si continuam crescator pana la pozitiile
cele mai inalte
2. Nu lasam goluri sub piese
Exista si alte euristici, dar acestea doua mi s-au parut cele mai bune.
Il felicit pe Bogdan Batog, a carui solutie mi-a placut foarte mult.
Vreau de asemenea sa-i multumesc foarte mult lui Alexandru Iosup, un
prieten care m-a ajutat la propunerea acestei probleme si care a oferit
o solutie nu numai foarte buna, dar si foarte elegant prezentata. Atasez
programul lui, scris in CBuilder. Programul are o interfata grafica draguta
si implementeaza 2 metode de rezolvare. Cea de a doua metoda obtine punctaj
maxim, iar prima metoda obtine 90%, dar este ceva mai rapida.
Morala acestei probleme: nu subestimati problemele exponentiale !
|
|