domingo, 9 de junio de 2013

LECCIÓN 10: PROBLEMAS DINÁMICOS. ESTRATEGIA MEDIO - FINES.

Viernes, 07 de junio del 2013






Estrategia Medio – Fines

Sirve para tratar situaciones dinámicas que consiste en identificar una secuencia de acciones que transformen el estado inicial o de partida en el estado final.

Espacio del problema

Es un diagrama que representa  todos los estados a los que podemos tener acceso.
Si un estado aparece, podemos llegar a el ejecutando los operadores que dan lugar a su aparición caso contrario es imposible acceder a dicho estado.



Ejemplo:
Dos mestizos y dos indios están en una margen de un río que desean cruzar. Es necesario hacerlo usando el bote que disponen.  La capacidad máxima del bote es de dos personas. Existe una limitación: en un mismo sitio el numero de indios no puede exceder al de misioneros porque, si lo excede, los indios se comen los mestizos ¿Cómo pueden hacer para cruzar los cuatro el río para seguir su camino?

Sistema: Río con cuatro personas (dos mestizos y dos indios) y un bote.
Estado inicial: Los dos mestizos y los dos indios en una ribera del río con el bote
Estado final: Los dos mestizos y los dos indios en la ribera opuesta del río con el bote.
Operadores: Cruzando el río con el bote.

¿Cuántas restricciones tenemos en este problema? ¿Cuáles son esas restricciones?
Capacidad máxima del bote es de dos personas, y el número de indios no puede ser mayor al de los mestizos porque se lo comerían.

¿Cómo podemos describir el estado?
(M, M, C, C, b ::) – (C, C, M, M, b ::)

¿Qué posibilidades o alternativas existen para cruzar el río con el operador  tomando en cuenta la restricción de la capacidad del bote?

A1: Bote con dos indios.
A2: Bote con dos mestizos.
A3: Bote con un indio y un mestizo.
A4: Bote con un indio.
A5: Bote con un mestizo.

¿Qué estados aparecen después de ejecutar la primera acción actuando con las cinco alternativas del operador?  Dibuja el diagrama resultante de aplicar todas las alternativas del operador al estado inicial.

(M, M :: C, C, b )
(M, M, C, b :: C)
( C :: C, M, M, b)
(C, M, b :: C, M)
(:: M,M, C, C, b)


¿Qué ocurre con la alternativa de que un mestizo tome el bote y cruce el río?
No es posible, porque no hay quien retorne el bote de regreso.

Construye el diagrama después de las sucesivas aplicaciones del operador. ¿Cómo queda el diagrama?




Respuesta:

Primer viaje: Los dos indios cruzan el río, uno de ellos se queda al otro lado, y uno regresa.
Segundo viaje: El indio de regreso se queda y cruzan los dos mestizos, uno de ellos se queda y el otro regresa.

Tercer viaje: Un mestizo y un indio cruzan juntos en el bote y se encuentran con el otro mestizo y  el indio.     

No hay comentarios:

Publicar un comentario