• Categories
• Algoritmos
• Conceptos matemáticos
• Algoritmos y estructuras de datos
• Áreas de la informática
• Ciencias de la computación teórica

Citation preview

El problema es que el granjero que tiene una gallina, un zorro y un saco de maíz, él tiene que cruzar un río en su bote, pero sólo puede llevas un objeto a la vez, no puede dejar solo al zorro con la gallina o a la gallina sola con el maíz porque se lo comerían. Cómo debe hacer para cruzar el río con sus 3 objetos intactos? Objetos: Gallina (G), Maiz (M) y Zorro (Z) Condiciones: 1. La gallina se come al maíz. 2. El zorro se come a la gallina 3. El granjero solo puede transportar un solo objeto a la vez. Estado inicial: G

M

Z

G

M

Z

Estado final:

Solución: 1º viaje: Se lleva a la gallina, entonces: G

M

Z

M

Z

G

2º viaje: Se lleva al zorro, pero como no puede dejarlo con la gallina, regresa la gallina a la posición inicial, entonces: M

G

Z

M

G

Z

M

G

Z

M

Z

3º viaje: Al retornar no puede dejar la gallina con el maíz, entonces, deja la gallina y se lleva el maíz, porque sabe que el zorro no se lo comerá, entonces:

G G

M

Z M

Z

4º viaje: Finalmente regresa por su gallina, entonces:

G G

M

Z

M

Z

El granjero deberá llevar la gallina al lado opuesto (B) dejando al zorro con el maíz, luego regresa al punto A, lleva al zorro al lado B, pero regresa a la gallina. Dejando a la gallina en el lado A, se lleva el maíz al lado B y finalmente regresa por la gallina.

Búsqueda A* con información de ciudades, mínimo 4 ciudades: Un vendedor desea ir de Piura a Ayacucho vendiendo sus frazadas por las ciudades señaladas como nodos del recorrido. Realice el recorrido de la búsqueda que maximice sus utilidades. Usted asigne los datos y las heurísticas necesarias para solucionar el problema. Sabemos que: Utilidades = Ventas – Costos Para maximizar las utilidades se debe maximizar las ventas y minimizar los costos. Con respecto a los costos se tienen las siguientes consideraciones: En un día el vendedor gasta en alimentación y estadía: Desayuno: S/. 5.00 Almuerzo: S/. 5.00 Cena: S/. 5.00 Extra: S/. 5.00 Estadía: S/. 20.00 El vendedor se queda un día en cada Departamento visitado. Por lo tanto, el gasto diario por alimentación y estadía es S/. 40. El costo de los pasajes se encuentra en la siguiente lista: GRAFO DE PRECIOS (COSTOS ENTRE CIUDADES)

Previamente se realizó un análisis para obtener esos valores: El grupo 2 llamó al teléfono 3115050 de la Empresa Cruz del Sur y solamente tenían información sobre el pasaje de Lima a Huaraz cuyo monto es S/. 85.00 en el primer piso del bus. A continuación calcularemos los demás montos mediante regla de tres simple considerando: Distancia entre Lima a Huaraz = 287 Km. Costo de pasaje Lima a Huaraz= S/. 85.00 Costo por kilómetro en Cruz del Sur: 0.296 soles/km.

RUTA DE CAMINOS PIURA-AYACUCHO CIUDADES PIURA-ANCASH PIURA-UCAYALI ANCASH-UCAYALI ANCASH-LIMA ANCASH- JUNIN UCAYALI-MADRE DE DIOS JUNIN-MADRE DE DIOS JUNIN-AYACUCHO LIMA-AYACUCHO MADRE DE DIOS-AYACUCHO UCAYALI-AYACUCHO

DISTANCIA 589 760 351 287 243 748 758 294 326 542 533

CIUDAD ORIGEN: PIURA CIUDAD DESTINO: AYACUCHO DISTANCIA LINEA RECTA CIUDAD PIURA ANCASH UCAYALI LIMA JUNIN MADRE DE DIOS AYACUCHO

DISTANCIA (KM) 1123 538 528 326 294 542 0

El precio de costo de una frazada en Piura es S/. 125.00 (Fuente: Mercado Libre)

Con respecto a las ventas se tienen las siguientes consideraciones: Precio de venta: S/. 200.00 Letra A B C D E F G

Ciudad Piura Ucayali Ancash Junín Lima Madre de Dios Ayacucho

Cantidad vendida por ciudad

Venta 3 3 5 5 3 3 5

600 600 1000 1000 600 600 1000

3, ciudad  costa  selva Cantidad vendida por ciudad  5, ciudad  sierra La heurística es Uij=Ventas – Costos. De acuerdo a la Programación Dinámica: Etapas: Cada tramo en que avanza desde A para alcanzar G. Variables de decisión: x n n  1,2,3 representan el destino inmediato en la etapa n. Variables de estado: y n , estado en el que se encuentra el vendedor. y n = A, B,..., G Función de transformación: Pasar de una etapa a otra: y n 1  y n  x n Función de Recursión: f n ( y n )  máxUij  f n 1 ( y n 1 ) En la etapa 3: y3 F B D E

x3=G 1000-161-40 1000-158-40 1000-87-40 1000-97-40

x3* G G G G

f(y3) 799 802 873 863

En la etapa 2: y2 B C D

x2=F 600+799-262 ---600+873-224-40

x2=B ---600+802-104-40 ----

x2=D ---1000+873-72-40 ----

x2=E ---600+863-85-40 ----

En la etapa 1: y1 A

x1=B 1000-174-40+1137

x1=C 600-225-40+1761

x1* C

f(y1) 2096

 El recorrido de la búsqueda que maximiza las utilidades es:

AC  D G

( Piura  Ancash  Junín  Ayacucho )

x2* F D F

f(y2) 1137 1761 1209