ii unidad - rvazquez.orgrvazquez.org/misitio/ia2010_files/unidad2ia.pdf · resolver estos problemas...

$: II Unidad - rvazquez.orgrvazquez.org/Misitio/ia2010_files/unidad2ia.pdf · resolver estos problemas de manera fácil, a un algoritmo ... Dominios={Rojo,Verde,Azul,Amarillo} Restricci$
Inteligencia ArtificialII UnidadPlan 2010-Ingeniería en Sistemas Computacionales

Rafael Vázquez Pérez

lunes 17 de marzo de 14

Unidad II:Técnicas de Búsqueda.

2.1. Solución de problemas con búsqueda.

2.2. Espacios de estados.

2.3. Métodos de búsqueda.

2.3.1. Primero en anchura (breadth- first).

2.3.2. Primero en profundidad (depth- first).

2.3.3. Primero el Mejor (best-first).

2.4. Satisfacción de restricciones.

2.5. Teoría de juegos.


“También les aseguro: pidan y se les dará, busquen y encontrarán, llamen y se les abrirá.

Porque el que pide, recibe; el que busca, encuentra; y al que llama, se le abre. “

San Lucas 11,1-13.


Solución de problemas con búsqueda.

• La resolución de problemas es fundamental para la mayoría de las aplicaciones de Inteligencia Artificial (IA).

• De hecho, la capacidad de resolver problemas suele usarse como una medida de la inteligencia tanto para el ser humano como para la computadora.



• Hay principalmente dos clases de problemas.

• Una primera clase puede ser resuelta usando algún tipo de procedimiento determinista cuyo éxito esté garantizado.

• A este procedimiento se le llama de computación.

• La resolución por computación normalmente sólo se aplica a aquellos tipos de problemas para los que existan tales procedimientos, como en matemáticas.

• Se puede con frecuencia traducir los métodos usados para resolver estos problemas de manera fácil, a un algoritmo que pueda ser ejecutado por una computadora.



• No obstante, a pesar de que pocos problemas reales se prestan a soluciones computacionales, deben ser situados en la segunda categoría, que consiste en problemas que se resuelven con la búsqueda de una solución.

• Este es el método de resolución de problemas del que se preocupa la IA.


Espacio de Estados• Un estado es la representación de un problema en un instante

dado.

• Para definir el espacio de estados o espacio de búsqueda (El conjunto de todos los nodos) no es necesario hacer una exhaustiva enumeración de todos los estado válidos, sino que es posible definirlo de manera más general. Esto se lleva a cabo mediante la representación formal del problema.

• La representación espacio estado se caracteriza por: ◦ Estado Inicial◦ Estado Final◦ Reglas de Producción (transición de estados u operadores )


Espacio de Estados

• El estado inicial consiste en el estado que comienza el problema.

Estado InicialAjedrez

Estado InicialSudoku 4


Espacio de Estados

• El estado final o estado meta consiste en uno o varios estados finales que se consideran solución aceptable.

Estados Finales Estado Final


Espacio de Estados• Las reglas de producción describen las acciones u

operadores que posibilitan un transito entre estados.

• Podríamos decir que una regla tiene una parte izquierda y una derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla.

• La parte derecha describe la operación que se lleva a cabo si se aplica la regla(acción).


Espacio de Estados  Reglas de Produccion

◦  Son los operadores o reglas de transicion de un estado a otro.

patron de match operación por aplicar

Parte Izquierda Parte Derecha


Espacio de Estados

• Ejemplo de reglas

• Gato

• Si el tablero esta vacío y turno = X → pon X en tablero[2,2]

• Ajedrez

• Si el péon llego a la octava casilla → coronarlo como una reina


Estado Inicial

Estado Final Estado Final


Ejemplo 1• Se tienen 2 jarras, una de 4 litros y otra de

3. Ninguna de ella tiene marcas de medición. ¿ Como lograr poner exactamente 2 litros de agua en el jarro de 3 ?


  Estado Inicial ◦  Es Posible representarlo con un par ordenado de

enteros ( x, y ) donde

◦  x = 0,1,2,3,4

◦  y = 0,1,2,3

◦  (0,0)


• Estado Final

• Ya que el problema no especifica cuantos litros deben de haber en el jarro de 4 es:

• (n,2)


  Reglas de Produccion ◦  1 (x,y) si x < 4 → (4,y) Llenar el jarro de 4 Lts ◦  2 (x,y) si y < 3 → (x,3) Llenar el jarro de 3 Lts ◦  3 (x,y) si x>0 → (0,y) Vaciar la jarra de 4 en el suelo ◦  4 (x,y) si y>0 → (x,0) Vaciar la jarra de 3 en el suelo ◦  5 (x,y) si x+y ≥ 4 ∧ y>0 → (4,y-(4-x)) Vaciar agua del ◦  jarro de 3 en el de 4 hasta que este lleno ◦  6 (x,y) si x+y ≥ 3 ∧ x>0 → (x-(3-y),3) Vaciar agua del ◦  jarro de 4 en el de 3 hasta que este lleno ◦  7 (x,y) si x+y ≤ 4 ∧ y>0 → (x+y,0) Vaciar todo el agua ◦  del jarro de 3 en el 4 ◦  8 (x,y) si x+y ≤ 3 ∧ x>0 → (0,x+y) Vaciar todo el agua ◦  del jarro de 4 en el 3


Métodos de Búsqueda

Métodos deBúsqueda

Métodos de Búsqueda no informada o a

ciegas

Anchura

Profundidad

Métodos deBúsqueda

Métodos de Búsqueda informada

Primero el Mejor

A*


Métodos de Búsqueda a Ciegas

• Los métodos a ciegas son procedimiento sistemáticos de búsqueda del estado meta en el árbol de estado.

• Son llamados de métodos a ciegas, porque usan estrategias de búsqueda que solo consideran la relación de precedencia entre estados.

• La información sobre el beneficio, utilidad, lucro de pasar de un estado para otro estado no es considerado.


Algoritmo Best First(básico)

1. Iniciar con la variable OPEN, asignándole el estado inicial.2. Hasta que una meta sea encontrada o no haya nodos dejados en OPEN hacer: 1. Tomar el mejor nodo en OPEN. 2. Generar sus sucesores 3. Para cada sucesor hacer: 1. Si no ha sido generado antes, evaluarlo, adicionarlo a OPEN y registrar su padre.


Búsqueda A*• Es una clase especial de búsqueda primero el mejor

con fines de minimizar el costo estimado total de la solución del problema• Para realizar esto simplemente implementamos una

función heurística mas poderosa

• f(n)=g(n)+h(n) f(n) función heurística

• g(n) el costo para alcanzar el nodo n desde el inicio• h(n) el costo para alcanzar una meta a partir de n

viernes 11 de octubre de 13lunes 17 de marzo de 14

A

B

FE

DC

G IH

J K

f(B)=g(B)+h(B)

g(B)

h(B)

Estimando que F es una meta

f(H)=g(H)+h(H)

g(H)

Estimando que J es una meta

h(H)

viernes 11 de octubre de 13


Satisfacción de restricciones

Satisfacción de restricciones Introducción

Satisfacción de Restricciones

Componentes del estado:VariablesDominios (valores posibles para las variables)Restricciones binarias entre las variables

Objetivo: Encontrar un estado que satisface las restricciones(Asignación de valores a las variables, que satisfaga las restricciones)Ejemplos:

Colorear mapas, crucigramas, 8-reinas, sudoku, ...Asignación/distribución/ubicación de recursos (distribución de tareasde fabricación, ubicación de gasolineras, antenas de telefonía, ...)

cbea (LSI-FIB-UPC) Inteligencia Artificial Curso 2011/2012 1 / 17lunes 17 de marzo de 14

Satisfacción de restriccionesSatisfacción de restricciones Introducción

RepresentaciónEstado = Grafo de restricciones

Variables = etiquetas de nodosDominios = contenido de nodosRestricciones = arcos dirigidos y etiquetados entre nodos

Ejemplo: colorear un mapa

123

4 5 6

7 8 9

Dominios={Rojo,Verde,Azul,Amarillo}

Restricción := Desigualdad

cbea (LSI-FIB-UPC) Inteligencia Artificial Curso 2011/2012 2 / 17lunes 17 de marzo de 14

Teoría de JuegosEstrategias de Búsqueda con adversarios

• La modificación necesaria de las estrategias de búsqueda ya vistas, es simplemente incluir un ambiente competitivo

• Esto da pie a problemas de búsqueda entre adversarios conocidos como juegos


Teoría de JuegosEstrategias de Búsqueda con adversarios

• Característica de un problema de juego

• 2 jugadores ( Max, Min)

• Turnos alternados (puede cualquiera de los 2 pasar en cualquier momento)

• Debe haber un estado inicial

• Reglas bien definidas

• Debe haber un ganador o empate

• No funciona en juegos de azar


x x xx x x

x x x

Estado Inicial

primerajugada

Turno

Max

x x x x x x x xo oo

oooo o

Min

x x x x xo oooo oox xxx x x x x x

Max

segundajugada

tercerajugada

Construcción del árbol de minimax



Árbol de Minimax

• El árbol se construye hasta llegar a los nodos terminales.

• Una vez en los nodos terminales, se evalúan con una función heurística.

• Y se prosigue a la propagación de las heurísticas para encontrar la jugada ganadora y el camino para ganar.



Árbol de Minimax

• La propagación de las heurísticas se realiza en base al siguiente algoritmo:

• Para ir de Min a Max se selecciona la menor

• Para ir de Max a Min se selecciona la mayor



A

FE

DCB

IHG J

Max

Min

6 3 0 -2 5 1



A

FE

DCB

IHG J

Max

Min

6 3 0 -2 5 1

3 -2 1



A

FE

DCB

IHG J

Max

Min

6 3 0 -2 5 1

3 -2 1

3Jugada Ganadora



ii unidad - rvazquez.orgrvazquez.org/misitio/ia2010_files/unidad2ia.pdf · resolver estos problemas...

Documents