Joc interesant pe mobil...

Post Reply
User avatar
Beniamin Bogosel
Co-admin
Posts: 710
Joined: Fri Mar 07, 2008 12:01 am
Location: Timisoara sau Sofronea (Arad)
Contact:

Joc interesant pe mobil...

Post by Beniamin Bogosel »

Un prieten are urmatorul joc pe mobil, si m-a rugat sa ma gandesc cum poate sa ajunga la punctajul maxim. Iata jocul:


Avem o tabla \( 5\times 5 \) impartita in 25 patrate unitate. Doua patrate se numesc vecine daca au o latura in comun.

Avem la dispozitie 4 culori: rosu(R), galben(G), albastru(A), verde (V), si initial toate patratele sunt albastre.
O mutare inseamna sa schimbam culoarea unui patratel cu una diferita de a sa in felul urmator:
-un patrat poate fi colorat cu R daca are un vecin A;
-un patrat poate fi colorat cu V daca are un vecin A si unul R;
-un patrat poate fi colorat cu G daca are un vecin A, unul R si unul V.
Culorile au punctajele urmatoare:
A: 1 punct;
R: 2 puncte;
V: 3 puncte;
G: 4 puncte;

Care este punctajul maxim posibil care poate fi atins folosind doar mutarile mentionate mai sus? (Am gasit rezultatul si este surprinzator de mare... :) )



Pentru cunoscatori, ar fi interesant de implementat un astfel de joc intr-un limbaj de programare... :)
User avatar
Ciprian Oprisa
Pitagora
Posts: 55
Joined: Tue Feb 19, 2008 8:01 pm
Location: Lyon sau Cluj sau Baia de Cris

Post by Ciprian Oprisa »

Nu am reusit sa implementez pe calculator, si cred ca e posibil sa nu prea se poata, cel putin nu prin "forta bruta". Optimul prin "forta bruta", implica generarea tuturor posibilitatilor. Backtrackingul ar intra in cicluri infinte, asa k nu este acceptabil.
O prima varianta, ar fi construirea unui graf, care sa contina toate configuratiile tablei de joc, cu legatura intre doua noduri daca se poate ajunge din unul in altul printr-o singura mutare. Apoi s-ar gasi cel mai mare nod care este in aceeasi componenta conexa cu cel initial.
Din pacate, avem \( 4^{25} \) noduri, ceea ce ar ocupa cam multa memorie, si mai ales, ar lua un timp de executie f mare.
O alta varianta ar fi folosirea metodei "Branch and Bound", dar cum se cer toate posibilitatile, ar genera si ea un timp f mare de executie si un consum insemnat de memorie.
Are cineva alte idei?
Un lucru este ceea ce este, nu ceea ce pare a fi.
Post Reply

Return to “Teoria jocurilor, economie si stiinte sociale”