De que manera se resuelve este problema de grafos?

El problema de cruzar el río:

Tenemos 3 misioneros y 3 caníbales y un bote para cruzar el río. El bote tiene capacidad para 2 personas a lo sumo. Se trata que los 6 individuos crucen el rio de forma que en ningún momento haya más caníbales que misioneros en cualquiera de los dos márgenes del río. Indiquemos con (i, j) el hecho que haya i misioneros y j caníbales en un dado margen. Entonces (i, j)→(i-1, j-1) significa una posible transición, es decir, cruzan el río un misionero y un caníbal. A continuación (i-1, j-1) → (i, j-1) significa que volvió el misionero solo. Imaginemos que dibujamos todos los pares (i, j) como puntos en el plano (i≥j) y unimos por flechas los pares que representan transiciones posibles. Se trata de hallar una sucesión de flechas consecutivas que parta de (3,3) y termine en (0,0)

0

Añade tu respuesta

Haz clic para o