Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.
-
Upload
maria-del-pilar-san-segundo-gomez -
Category
Documents
-
view
224 -
download
0
Transcript of Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.
![Page 1: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/1.jpg)
Inteligencia Artificial
Profesor: Dr. José Ruiz Pinales
2 Representación de Problemas
![Page 2: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/2.jpg)
Representación de Problemas“Si, para un problema dado, tenemos un medio de verificar una solución propuesta, entonces podemos resolver el problema probando todas las respuestas posibles. Pero esto siempre toma mucho tiempo para ser de uso práctico. Cualquier artificio que pueda reducir esta búsqueda sería valioso.”
Marvin Minsky, Steps Toward Artificial Intelligence
•El tipo de representación es importante• Evitar hacer cálculos inútiles que hacen la solución
más tardada.
• La representación debe tener relación con el problema a resolver
• La representación debe incluir un medio de resolver el problema
2
![Page 3: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/3.jpg)
Representación de Problemas• Representación por espacios de estado
• El problema es representado como estados, cambios de estado y metas.
• Representación por reducción de problema
• Reducir un problema complejo en sub-problemas más pequeños y más fáciles de resolver
3
![Page 4: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/4.jpg)
Representación por Espacio de Estado
• Estados• En ajedrez, un estado puede ser una
configuración dada del juego
• Estado inicial: la configuración inicial
• Estados meta: las configuraciones de gane
• Operadores o acciones• Los diferentes movimientos que puede
tener cada pieza de una configuración dada.
4
![Page 5: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/5.jpg)
Otros conceptos
5
Función sucesor Da estado resultante de aplicar una acción a un estado
Costo de ruta Costo en tiempo, dinero, etc.
Costo individual Costo de una acción en un solo estado
Estado terminal Estado que no tiene estado siguiente
Solución óptima Ruta de costo más bajo
Problema juguete Se usa para ilustrar o probar métodos de solución
Problema del mundo Problema que la gente desea resolverreal
![Page 6: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/6.jpg)
Formulación de Problemas
• Abstracción• Proceso de eliminar detalles de una
representación
• Buena abstracción• Quitar tantos detalles como sea posible
mientras se conserve la validez de la abstracción y las acciones sean fáciles de realizar
6
![Page 7: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/7.jpg)
Rompecabezas de las 8 piezas
7
Estado inicial
Estado meta
Operadores =
Mover cuadro arriba,Mover cuadro abajo,Mover cuadro derecha,Mover cuadro izquierda
Espacio de estados={Estados alcanzables desde estado inicial}
Número de estados alcanzables = 9!/2 = 181440
![Page 8: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/8.jpg)
Solución1 6 2
8 3
7 5 4
8
1 6 2
8 5 3
7 4
arriba
1 6 2
8 3
7 5 4
1 2
8 6 3
7 5 4
1 6 2
8 3
7 5 4
izquierda abajo derecha
1 6 2
8 5 3
7 4
1 6 2
8 5 3
7 4
derecha izquierda
Estado inicial
![Page 9: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/9.jpg)
Solución
9Costo de la solución: 6
![Page 10: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/10.jpg)
Rompecabezas de las N piezas
• N = 15• Tamaño del espacio de estados ≈ 1.3×1012
• N = 24• Tamaño del espacio de estados ≈ 1025
10
El problema es NP completoMuy difícil de resolver
![Page 11: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/11.jpg)
Problema de las 8 reinas
• Colocar 8 reinas en un tablero sin que se amenacen.
11
![Page 12: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/12.jpg)
Representación
• Estados = {cualquier combinación de 0 a 8 reinas}
• Estado inicial = ninguna reina en tablero
• Estados meta = 8 reinas en tablero, ninguna reina es atacada
• Función sucesor = poner una reina en casilla vacía
• Prueba objetivo = estado actual es estado meta
12Hay aproximadamente 3×1014 estados
![Page 13: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/13.jpg)
Otra Representación• Estados = {cualquier combinación de n
reinas, 0≤n≤8, una por columna, desde la primera columna, sin que se ataquen}
• Función sucesor = poner una reina en cualquier casilla de una columna vacía más a la izquierda
13
¡Hay sólo 2057 estados!
![Page 14: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/14.jpg)
Problema del Viajante de Comercio
• Un comerciante desea recorrer un conjunto de ciudades de manera que recorra la mínima distancia.
14
![Page 15: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/15.jpg)
Representación• Espacio de estados = las ciudades ya visitadas
en orden, las ciudades aún sin visitar• Estado inicial = ciudad de partida, demás
ciudades sin visitar• Estado meta: Todas las ciudades visitadas• Costo individual = distancia entre ciudad
siguiente y ciudad anterior visitada• Función sucesor = visitar cualquier ciudad no
visitada• Costo de ruta: suma de distancias recorridas
15Problema NP difícilHay N!/2N recorridos posibles
![Page 16: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/16.jpg)
La Torre de Hanoi• Se tienen n discos y tres postes. Se trata de colocar
todos los discos en el tercer poste uno por uno y sin saltar un poste.
16
![Page 17: Inteligencia Artificial Profesor: Dr. José Ruiz Pinales 2 Representación de Problemas.](https://reader035.fdocumento.com/reader035/viewer/2022062410/5665b4e71a28abb57c94a1b2/html5/thumbnails/17.jpg)
Representación
17
Estado inicial Estado meta
Espacio de estados
Hay 27 estados posibles