Misionari a kanibalove

Zadani

Implementujte vlastni reseni problemu zvaneho Misionari a kanibalove. Pro implementaci pouzijte hledani do sirky ve stromu, ktery reprezentuje prostor vsech moznych reseni.

problému

Tri misionari a tri kanibalove sjou na jedne strane reky a maji k dispozici jednu lodku, ktera uveze jednoho nebo dva lidi. Ukolem je najit zpusob prepravy vsech sesti lidi na druhou stranu reky tak, aby nikdy nezustala skupina misionaru s ciselnou prevahou kanibalu na jednom miste. Ciselna prevaha neni v lodce mozna, takze zbyvaji pouze oba brehy jako moznosti. Pokud ma do lodky nastoupit cestujuci, je jedno, ktery kanibal ci misionar, na kterem brehu se zacina... apod.

Detaily

  1. Stavy: stav se sklada z usporadane sekvence tri cisel reprezentujicich pocet misionaru, pocet kanibalu a pocet lodek na kazdem brehu.
  2. Operatory: z kazdeho stavu existuji mozne operatory: do lodky nastoupi 1 nebo 2 misionari, 1 nebo 2 kanibalove, nebo 1 misionar a 1 kanibal.
  3. Test cile: dosazni stavu (0,0,0) na vychozim brehu
  4. Cena cesty: pocet prejezdu pres reku

Implementace

Popis implementace je uveden v dokumentaci k souboru misionari.cpp. Nase implementace je znacne nefektivni jak casove (je zbytecne nejdriv generovat strom a nasledneho ho prohledavat) tak prostorove, misto stromu by stacilo ukladat frontu stavu (pricemz by bylo zachovano prohledavani do sirky).
Generováno Thu Oct 5 20:35:31 2006 pro projekt Misionari a Kanibalove programem  doxygen 1.4.7