Problema canibalilor si a misionarilor

Pe malul drept al unui rau se afla trei canibali si trei misionari. Cei sase trebuie sa ajunga pe malul drept. Daca la un moment dat pe un mal se afla mai multi canibali decat misionari atunci canibalii vor manca misionarii. Gasiti o modalitate de a traversa pe malul stang astfel incaat sa nu fie mancat nici un misionar.

Pentru o simulare a problemei studiati site-ul : http://www.plastelina.net/games/game2.html

A. Un model matematic de rezolvare este:

{ (a,b,c,d,e,f) | a,b,c,d,e,f din {0,1,2,3} }

B. Definirea formala a problemei:

� Starea initiala

Mal Stang Barca Mal drept M M M C C C � pasii spre rezolvare Pas Mal stang Barca Mal drept

M M M C C C 1 C C M M M C 2 C C M M M C 3 C C C M M M 4 C C C M M M 5 C C M M M C 6 C M M C M C 7 C M M M C C 8 M M M C C C 9 M M M C C C 10 C M M M C C 11 C M M M C C 12 C C C M M M � Starea finala:

Mal Stang Barca Mal drept C C C M M M

C. Operatorii:

c_md_b, � canibal de pe mal Drept in barca

c_ms_b, � canibal de pe mal Stang in barca c_b_md, � canibal din barca pe mal Drept c_b_ms, � canibal din barca pe mal Stang m_md_b, � misionar de pe mal Drept in barca m_ms_b, � misionar de pe mal Stang in barca m_b_md, � misionar din barca pe mal Drept m_b_ms, � misionar din barca pe mal Stang

D. Spatiul starilor:

S={ (canibali,misionari) canibali={0,1,2,3 }, misionari={0,1,2,3} }

E. Arborele de stari:

Problema lup, capra, varza

Un taran are un lup, o capra si o varza. El se afla pe malul stang al unei ape si trebuie sa treaca cele trei animale pe malul drept. Daca raman nesupravagheate lupul poate manca capra, iar capra poate manca varza. Se cere sa se gaseasca o solutie astfel incat toate cele trei animale sa ajunga pe malul drept in conditiile expuse mai sus.

A. Un model matematic de rezolvare este: { (a,b,c,d,e,f,g) | a,b,c,d,e,f,g din {0,1} }

B. Definirea formala a problemei:

� Starea initiala

Mal Stang Barca Mal drept L C V

� pasii spre rezolvare Pas Mal stang Barca Mal drept

L C V 1 C L V 2 C L V 3 C L V V L 4 L V C V L 5 L V V L C 6 L V C 7 L V C 8 L C V � Starea finala:

Mal Stang Barca Mal drept L C V

C. Operatorii:

c_md_b, � capra de pe mal Drept in barca c_ms_b, � capra de pe mal Stang in barca c_b_md, � capra din barca pe mal Drept c_b_ms, � capra din barca pe mal Stang

l_md_b, � lup de pe mal Drept in barca l_ms_b, � lup de pe mal Stang in barca � asta nu se intampla niciodata l_b_md, � lup din barca pe mal Drept � asta nu se intampla niciodata l_b_ms, � lup din barca pe mal Stang v_md_b, � varza de pe mal Drept in barca v_ms_b, � varza de pe mal Stang in barca � asta nu se intampla niciodata v_b_md, � varza din barca pe mal Drept � asta nu se intampla niciodata v_b_ms � varza din barca pe mal Stang

D. Spatiul starilor:

S={ x | x din {l , c, v } }

E. Arborele de stari: