Problema: Pe malul stâng al unui râu sunt n cupluri (soț-soție) și o barcă în care încap maxim două persoane. Găsiți o secvență de mutări, folosind barca, astfel încât toate persoanele să ajungă pe malul drept.
Știm că:
● Barca nu se poate deplasa de pe un mal pe celălalt decât cu cel puțin o persoană.
● Pe nici un mal nu poate fi vreodată o soție fără soțul său, dacă pe acel mal mai există cel puțin un soț.
Persoanele din barcă sunt considerate pe malul destinație (transferul este instantaneu).
Etape de rezolvare:
1. (0.2) Alegeți o reprezentare a unei stări a problemei. Reprezentarea trebuie să fie suficient de explicită pentru a conține toate informaţiile necesare pentru continuarea găsirii unei soluții dar trebuie să fie și suficient de formalizată pentru a fi ușor de prelucrat/memorat.
2. (0.2) Identificați stările speciale (inițială și finală) și implementați funcția de inițializare (primește ca parametrii instanța problemei, întoarce starea inițială) și funcția booleană care verifică dacă o stare primită ca parametru este finală.
3. (0.2) Implementați tranzițiile ca o funcție care primește ca parametri o stare și parametrii tranziției și întoarce starea rezultată în urma aplicării tranziției. Validarea tranziției se face într-o funcție booleană separată, cu aceeași parametrii.
4. (0.2) Implementați strategia Backtracking.
5. (0.2) Implementați strategia BFS.
6. (0.2) Implementați strategia Hillclimbing.
7. (0.2) Implementați strategia A*
8. (0.2) Implementați un meniu care permite, după introducerea instanței, selectarea strategiei care va fi încercată.
La afișarea soluției se vor indica toate tranzițiile făcute, câte una pe un rând.
Pentru primul laborator trebuie rezolvate cel puțin primele două puncte.
Pentru al doilea laborator trebuie rezolvate cel puțin primele 5 puncte.
Resurse utile:
● https://www.cs.uni.edu/~wallingf/teaching/cs3530/sessions/session23.html
