FACULTAD DE INGENIERA EN CIENCIAS DE LA COMPUTACINY TELECOMUNICACIONES

CARRERA DE INGENIERA INFORMTICA

INTELIGENCIA ARTIFICIALGRUPO: 11INTEGRANTES:

Arredondo Rojas BismarckMontao Vargas Vctor HugoSalazar Colque LisbethVaca Rocha Edison Augusto

Das de Retraso: 0

Fecha de Presentacin: Sbado, 14 de Marzo del 2015

UNIVERSIDAD AUTNOMA GABRIEL REN MORENO

ndice1. PROBLEMAS CON REPETICIONES ................................................................................................ 3

1.1. Torre de Hani..................................................................................................................... 31.2. El Lobo, La Oveja y Una Col ................................................................................................. 41.3. La Rana Saltarina ................................................................................................................. 5

2. PROBLEMAS SIN REPETICIONES .................................................................................................. 62.1. El Vendedor Viajero............................................................................................................ 62.2. Laberinto ............................................................................................................................ 72.3. Los Dos Cubos..................................................................................................................... 92.4. El Mundo de la Aspiradora................................................................................................ 102.5. La Guardia......................................................................................................................... 10

1. PROBLEMASCONREPETICIONES

1.1. Torre de HaniLas torres de Hani es un juego matemtico ideado en el siglo XVIII. Este juego consiste en pasar64 discos de dimetro decreciente, de un poste a otro poste, utilizando un tercer poste auxiliarpara los pasos intermedios.Cada vez solo se puede mover un disco, los discos siempre deben estar en algn poste y no sepuede colocar un disco sobre otro de menor tamao.

Un estado puede representarse como una lista con los discos que hay en cada uno de los postes.Cada disco viene representado con un identificador que indica adems su dimetro.

Estado: , , , donde es una lista de valores entre 1 y 64. Estado inicial: [64,63,62,,4,3,2,1] [ ] [ ] Estado final: [ ] [ ] [64,63,62,,4,3,2,1]

Existe un nico operador. Mover( , ) que mueve un disco del poste al poste .

1.2. El Lobo, La Oveja y Una ColUn hombre se encuentra en la orilla izquierda de un ro junto con un lobo, una oveja y una col.Quiere cruzar el ro llevando consigo el lobo, la oveja y la col. En la barca slo hay dos plazas, unade las cuales debe ir ocupada por el hombre. Cada uno de los restantes pasajeros (lobo, oveja, col)ocupa una plaza, de tal modo que slo uno puede acompaar al hombre en cada viaje. Adems,no puede dejar solos en una orilla al lobo con la oveja, ni a la oveja con la col (ni los tres), porquela primera se comera a la segunda en cada paso.Cada estado se describe como un par de conjuntos, indicando quien(es) se encuentran en cadaorilla del ro (c = col; o = oveja; l = lobo; h = hombre). Por tanto, el estado inicial del problema sera({c,o,l,h},{}), y el estado meta ({},{c,o,l,h}).

1.3. La Rana SaltarinaEn una charca viven n ranas y sapos, n/2 ranas verdes y n/2 sapos marrones. Las ranas estn en laparte izquierda del cuadro y van saltando hacia la derecha. Los sapos van saltando hacia laizquierda. El objetivo del juego es poner las ranas a la derecha y los sapos a la izquierda. Solo sepermite saltar a la piedra contigua, o saltar por encima de otro animal de diferente color. Abajo semuestra una posible solucin para n=4.

2. PROBLEMASSINREPETICIONES2.1. El Vendedor ViajeroUn viajero debe visitar cinco ciudades, no debe pasar por una ciudad ms de una vez y retornar ala ciudad de donde parti; existe un tren entre cada par de ciudades y la distancia que se recorrese indica en el grafo. El problema es encontrar la distancia mnima de la ruta para visita todas lasciudades sin pasar por una ms de una vez.

Para exponer este tipo de problema se especifica lo siguiente:Estado Inicial: AEstado Final: A (El vendedor termina su viaje en la ciudad que inici)Las reglas corresponden a las decisiones:

a) Ir a la ciudad prxima Ab) Ir a la ciudad prxima Bc) Ir a la ciudad prxima Cd) Ir a la ciudad prxima De) Ir a la ciudad prxima E

El rbol permite explorara las posibles rutas y as hallar la que tenga menor longitud o costo. Estaestrategia funciona en la prctica para listas con pocas ciudades, pero colapsa rpidamenteconforme aumente el nmero de ciudades. Si existen N ciudades, el nmero de rutas diferentesentre ellas ( 1)!. El tiempo total empleado para completar la bsqueda es porcional a

rbol de Solucin de Rutas

2.2. LaberintoEn el siguiente laberinto, se puede pasar desde una casilla a otra de las posibles adyacentes(arriba, abajo, izquierda, derecha), salvo si existe una barrera entre ellas.

Objetivo: ir de I a FEstados: A, B, C, D, E, I, W, K, M, N, P, Q, R, T y FEstado inicial: IEstado final: FOperadores: arriba, abajo, izquierda, derechaArriba es aplicable a un estado si existe una casilla arriba y no est separada por barrera; elresultado de aplicarlo es la casilla de arriba y su coste es 1.Consideraremos que los sucesores estn ordenados alfabticamente.

Solucin encontrada: I-Q-R-T-K-M-F- No es ptima.

Solucin encontrada: I-W-K-M-F- Optima.

2.3. Los Dos CubosDisponemos de dos cubos inicialmente vacos, uno de 8 litros, y el otro de 6 litros. Ninguno de loscubos tiene marcas ni divisiones. Disponemos tambin de un grifo que puede emplearse parallenar los cubos. Qu tenemos que hacer para llenar el cubo de 8 litros justamente hasta lamitad?Llamaremos A al cubo de 8 litros, y B al cubo de 6 litros.Resolucion de problemas:

2.4. El Mundo de la AspiradoraEl mundo tiene dos posiciones. En las posiciones del mundo puede haber o no suciedad. El agenteest en una u otra posicin. Las acciones que puede realizar el agente son: Left (izquierda), Right(derecha) y Suck (aspirar). El objetivo es limpiar toda la suciedad, que equivale al conjunto deestados {7, 8}.

- Estados: ubicaciones del agente y del polvo = 8 estados posibles.- Estado inicial: cualquier estado puede ser designado como inicial.- Funcin sucesor: genera estados legales al intentar las tres acciones Izquierda, Derecha o

Aspirar.- Test objetivo: comprueba si todos los cuartos estn limpios.- Costo del camino: nmero de pasos que lo componen.

2.5. La GuardiaEl jefe de guardia de un campamento ocupa la tienda central de un cuadrado formado por nuevetiendas de campaas. Las otras ocho son ocupadas por tres guardias en cada una.El jefe de guardia permita que los soldados de unas tiendas pudieran ir a visitar a los de otras. Yno impona sanciones cuando al entrar en las tiendas encontraba en unos ms de tres soldados yen otras, menos.Se limitaba a comprobar el nmero de soldados que haba en cada lado del cuadrado: si en las trestiendas de cada lado haba en total nueve soldados, el jefe de la guardia consideraba que todos lossoldados estaban presentes.Los soldados se dieron cuenta de esto y encontraron el modo de burlarse del jefe.

Una noche se marcharon cuatro soldados de la guardia y los restantes se redistribuyeron de modoque la ausencia de los cuatro que se marcharon no fue notada.Cmo se redistribuyeron los 20 guardias que quedaron?Estado inicial: 0 guardias

Estado final: 20 guardias