ICIF0021 Inteligencia Artificial Primer Semestre, 2011

Practica No. 2 : Tecnicas de BusquedaDocente: Milton Ramırez Klapp Universidad San Sebastian

Problema 1. Describa completamente la estructura que tiene un grafo de estados y como se puede derivara partir de este el arbol de busqueda.

Problema 2. Bosqueje el espacio de estados para el juego del gato. ¿Como elaborarıa ud. una estrategia debusqueda que le permita salir airoso?.

1. Busqueda no Informada

Problema 1. Considere el grafo de estados de la figura 1

Figura 1: Grafo de estados.

Encuentre un camino para llegar del nodo marcado con negro al nodo gris usando tecnicas debusqueda no informada.

Problema 2. Puzzle 8 y Puzzle 4 usando diferentes estados iniciales y finales.

Problema 3. El caballo del ajedrez describe una trayectoria en el tablero con forma de L: puede desplazarsedos casillas en direccion horizontal o vertical y una en direccion perpendicular a la anterior.La idea es encontrar una secuencia de movimientos validos ocupando solo esta pieza para querecorra todas las casillas del tablero, visitando cada una exactamente una vez. Bosqueje unasolucion para un tablero de 4× 3 y otro para el tablero de 8× 8.

Problema 4. Encuentre una solucion para el problema de colocar 4 reinas en un tablero de ajedrez de orden4, de tal manera que no se maten entre sı.

Problema 5. Un mono de tres pies de alto esta en una habitacion en donde los platanos estan suspendidosdel techo de nueve pies de alto. Al mono le gustarıa conseguir los platanos. La habitacioncontiene dos cajas apilables, movibles y escalables de tres pies de alto que estan a la derechadel primate.

1

Problema 6. (a) Encuentre una expresion analıtica que permita resolver

∀n ∈ N :

∫secn θdθ

(b) Use la expresion encontrada en la parte (i) para hallar una solucion con n = 5 empleandotecnicas de busqueda no informadas.

Problema 7. Resuelva el problema de demostrar analıticamente este resultado del calculo integral:∫R

dx

x2 + 1= π

2. Busqueda Informada

Problema 1. Suponga que existen 7 piedras en lınea en un charco, cada una de las cuales solo puede serocupada por un sapo. Inicialmente, en cada una de las 3 piedras de mas a la izquierda hayun sapo verde mirando hacia la derecha. En cada una de las 3 piedras de mas a la derechahay un sapo amarillo mirando hacia la izquierda. En consecuencia, inicialmente solo la piedracentral esta desocupada. Los sapos verdes solo pueden avanzar hacia la derecha y los amarillossolamente hacia la izquierda. Cuando un sapo avanza, solo lo puede hacer a una piedra libreadyacente (con costo 1) o puede saltar un unico sapo y caer en una piedra libre adyacente (concosto 2). El problema consiste en que los sapos amarillos finalicen en las 3 piedras de mas ala izquierda y los sapos verdes en las 3 piedras de mas a la derecha. Considere la siguienteheurıstica: h(n) = cantidad de elementos que no estan en la posicion objetivo.

Problema 2. Tenemos cuatro ciudades interconectadas entre sı, tal como se muestra en la tabla 1:

A B C DA 10 15 20B 12 9C 5D

Tabla 1: Distancia en lınea recta entre dos ciudades

Asumiendo que el costo de ir de una ciudad a otra fuera igual a una constante k ≥ 0, indiquecual es el camino mas corto para ir:

(a) Desde A hasta D.

(b) Desde B hasta D.

(c) Desde C hasta A.

Problema 3. Resolver el juego del 8 y 4-Puzzle asumiendo que los costos de operacion son constantes yconsiderando estas heurısticas:

(a) h1(n) = numero de piezas mal colocadas.

(b) h2(n) = distancia Manhattan total: numero de casillas para llegar a la meta de cadaficha.

2