• Author / Uploaded
• Ana Panameño

Citation preview

Taller de Soluciones a Problemas Inteligencia Artificia

ANA MILENA PANAMEÑO PEREA MIGUEL SOLIS PRISCILA MARLOVI

UNIVERSIDAD DEL PACIFICO INTELIGENCIA ARTIFICAL 2019

Taller de Soluciones a Problemas Inteligencia Artificia

1.Acertijo del puente y la antorcha: Un grupo de 5 personas quiere cruzar un viejo y estrecho puente. Es una noche cerrada y se necesita llevar una linterna para cruzar, pero el grupo sólo dispone de una linterna, a la que le quedan 5 minutos de batería. Cada persona tarda en cruzar 15, 30, 60, 80 y 120 segundos, respectivamente. El puente sólo resiste un máximo de 2 personas cruzando a la vez, y cuando cruzan dos personas juntas caminan a la velocidad del más lento. No se puede lanzar la linterna de un extremo a otro del puente, así que cada vez que crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los compañeros que falten, y repetir este proceso hasta que hayan cruzado todos. ¿Cuál sería una solución válida? A=15 B=30 C=60 D=80 E=120

Tiempo Transcurrido 0 minutos 30 segundos

Lado de Partida AB CDE CDE

45 segundos

A CDE

165 segundos

A C

195segundos

AB C

255 segundos

B

270 segundos

AB

300 segundos=5m

Acción

Lado de Llegada

A y B cruzan hacia adelante, toma 30 segundos A regresa, toma 15 segundos D y E cruzan hacia adelante, toma 120 segundos B regresa, toma 30 segundos A y C cruzan hacia adelante, toma 60 segundos A regresa, toma 15 segundos A y B cruzan hacia adelante, toma 30 segundos

AB B BDE DE ACDE CDE ABCDE

2. Problema de las 3 Jarras: Se tienen 3 jarras de 12, 8 y 3 litros de capacidad y un grifo. Las operaciones que se pueden realizar con ellas son: llenar cada una de

las jarras de agua, volcar el contenido de una en cualquier otra (hasta que una de las dos se vacía, o la otra se llena), o bien vaciar su contenido en el suelo. El objetivo es conseguir exactamente 1 litro en alguna de las jarras. MOVIMIENTOS

A:Jarra 12=0; Jarra 8=0; Jarra 3=0 B: Jarra 12=12; Jarra 8=0; Jarra 3=0 C: Jarra 12=1; Jarra 8=8; Jarra 3=3

ACCION Llenar la jarra de 12 litros completamente Vaciar en la jarra de 8 litros su capacidad en litros de la jarra de 12 litros ( para ello, la jarra de 8 litros debe estar completamente vacia) Vaciar en la jarra de 3 litros su capacidad en litros de lo queda la jarra de 12 litros ( para ello, la jarra de 8 litros debe estar completamente vacia) la jarra de 12 litros le queda 1 litro

3. Torres de Hanoi: Se tienen N discos de distinto tamaño apilados sobre una base A de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías B y C. Haciendo uso únicamente de las 3 bases, el objetivo es llevar todos los discos de la base A hasta la base C. Sólo se puede mover un disco a la vez, y cada disco puede descansar solamente en las bases o sobre otro disco de tamaño superior, pero no en el suelo. Resuelva el problema de la torre de Hanoi para N=4.

Partida Mover= A (Dis1,2,3,4), B (Disc:0), C (Disc:0) Mover= A (Dis1,2,), B (Disc:4), C (Disc:3) Mover= A (Dis1), B (Disc:2), C (Disc:3,4) Mover= A (Dis1,4), B (Disc:2), C (Disc:3) Mover= A (Dis 0), B (Disc:2,3,4),C (Disc:1) Mover= A(Dis4), B (Disc:2), C (Disc:1,3) Mover=A (Dis 3), B (Disc:2,4), C (Disc:1) Mover =A (Dis 3,4), B (Disc:0), C (Disc:1,2) Mover =A (Dis 0), B (Disc:4), C (Disc:1,2,3) Mover=A(Dis 0), B (Disc:0), C (Disc:1,2,3,4) 4. Problema de las N reinas: Situar N reinas en un tablero de ajedrez de tamaño N×N sin que se amenacen entre ellas. Una reina amenaza a otra si ambas están en la misma fila, columna o diagonal.

Consultar el número de soluciones al problema de las N Reinas; para N entre 8 y 20 Muestre al menos tres soluciones del problema de las N Reinas; para N entre 8 y 10.

n

distintas

todas las soluciones:

8

12

92

9

46

352

10

92

724

11

341

2,680

12

1,787

14,200

13

9,233

73,712

14

45,752

365,596

15

285,053

2,279,184

16

1,846,955

14,772,512

17

11,977,939

95,815,104

18

83,263,591

666,090,624

19

621,012,754

4,968,057,848

20

4,878,666,808

39,029,188,884

R/ Soluciones del problema de las N Reinas; para N entre 8 y 10. Fila=f Columna=C

Partida N=8 Mover= R1 (F1,Cf), R2 (F2,Ca), R3 (F3,Ce), R4(F4,Cb) Mover= R5 (F5,Ch), R6 (F6,Cc), R7 (Fg,Cg), R8(F8,Cd) Partida N=9 Mover= R1 (F1,Cf), R2 (F2,Ca), R3 (F3,Ce), R4(F4,Cb) Mover= R5 (F5,Ch), R6 (F6,Cc), R7 (Fg,Cg),R8(F8,Cd),R9(F9,CJ) Partida N=10 Mover= R1 (F1,Cf), R2 (F2,Ca), R3 (F3,Ce), R4(F4,Cb) Mover= R6 (F6,Cc), R7 (Fg,Cg),R8(F8,Cd), R9(F9,CJ),R910(F10,Ck)

5. El nomo inteligente. El problema consiste en encontrar un camino que le permita al nomo llegar al sitio g. El paso por cada puente tiene el costo que se muestra en la figura. Muestre el árbol generado de aplicar búsqueda limitada por

profundidad 3 evitando ciclos y usando los operadores en el siguiente orden:  , , , .  , , , . R/ G N e d iI

E

j A

g

j

f

I

k f

e

f a

a

E

f