Misionari a kanibalove
Implementujte vlastni reseni problemu zvaneho Misionari a kanibalove. Pro implementaci pouzijte hledani do sirky ve stromu, ktery reprezentuje prostor vsech moznych reseni.
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.
- Stavy: stav se sklada z usporadane sekvence tri cisel reprezentujicich pocet misionaru, pocet kanibalu a pocet lodek na kazdem brehu.
- Operatory: z kazdeho stavu existuji mozne operatory: do lodky nastoupi 1 nebo 2 misionari, 1 nebo 2 kanibalove, nebo 1 misionar a 1 kanibal.
- Test cile: dosazni stavu (0,0,0) na vychozim brehu
- Cena cesty: pocet prejezdu pres reku
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
1.4.7