Branch and Bound

[•david_bv2334]

Salut!
Am o mica problema cu aceasta tehnica. Sunt n canibali si n misionari pe malul unui rau. pe rau se afla o barca ce are capacitatea de k<n persoane si trebuie sa transport atat canib alii cat si misionarii pe celalalt mal al raului cu aceasta barca. Exista o restrictie: pe oricare dintre maluri nu pot sa fie mai multi canibali decat misionari, intrucat canibalii ar manca misionarii in acest caz. restrictia nu este valabila si pentru barca: in barca pot sa fie 2 canibali si un singur misionar de exemplu, iar barca nu trebuie neaparat sa fie plina.  Doresc sa scriu un program in C care sa imi returneze solutia cu numarul cel mai mic de traversari ale raului pentru a transfera canibalii si misionarii pe celalalt mal al apei.  Ideea e ca trebuie sa folosesc Branch and Bound pentru aceasta si caut o functie de bounding cat mai buna intrucat aceasta este cheia eficientei programului. Ceea ce va rog eu este sa imi propuneti o solutie pentru aceasta functie de bounding.

Mersi anticipat!

[•veleandu]

Daca numarul de canibali trebuie sa fie <= nr_misionari, tot timpul muti perechi de cate 2.
Nu are rost sa duci pe cineva inapoi, opinia mea.

Daca nu, incerci sa faci acelasi lucru, dar cu 2 canibali in barca tot timpul.
Sper sa fie ok.