27 ianuarie 2013

Problema canibalilor si a misionarilor

Mi-am dezmortit putin cunostintele de C, facand problema "canibalilor si a misionarilor" , propusa de AI-planning. (chiar nu am vrut sa recurg la C, dar asta este cea mai buna varianta pentru un calculator pe care rulez tot timpul Ubuntu live)

Problema suna cam asa: "Un rau are 2 maluri. Pe malul din stanga se afla 3 misionari si 3 canibali, care vor sa ajunga pe malul din dreapta. Ei au la dispozitie o barca, cu capacitate maxima de 2 persoane. Cum pot trece ei astfel incat misionarii sa nu fie mancati de canibali? Daca pe unul din maluri exista misionari si ei sunt mai putini la numar decat canibalii, atunci vor fi mancati."

Am aflat ca aceasta problema este clasica in AI-planning , si are si o varianta mai extinsa a unor cupluri geloase. Momentan, m-am limitat la o implementare simpla in C, in care accentul cade pe modul cum se reprezinta starile si actiunile. Ce inseamna success si failure. Cum alegem sa facem cautarea - in depth, in breadth? Eu am ales varianta in adancime (recursivitate). Iar implementarea se poate vedea aici (cu 4 solutii gasite, care au aceeasi "lungime").