unidadiii ia

Curso:
Inteligencia Artificial
Unidad III:
Solución de problemas por búsqueda
M. en I.A. Daniel Alejandro García López

19 de enero de 2009

Resumen
La resolución de problemas se describe a menudo como una búsqueda en un enorme laberinto de posibilidades, un laberinto que describe el entorno. Para resolver existosamente un problema se requiere explorar
el laberinto de forma selectiva y con elloreducirlo a proporciones manejables. Las máquinas aún no pueden
reducir automáticamente los problemas a proporciones manejables, es por ello que los seres humanos tienen
que formular los problemas y proponer estrategias para encontrar su solución.
En esta unidad se tratará temas relacionados con la búsqueda en el espacio de estados(que es como
el laberinto de posibilidades). En algunos tipos deproblemas lo importante es encontrar una solución,
aunque esta no sea la mejor debe ser una solución aceptable, en otros casos es necesario encontrar el
camino que nos lleva a esa solución. De manera general, cualquiera de las estrategias de búsqueda que se
tratan en esta unidad pueden resolver ambos requisitos, sólo se requieren pequeños ajustes en sus métodos
generales.
La mayoría de lasestrategias de búsqueda que son tratadas en esta unidad son enfocadas a ejemplos
para maximizar la comprensión de las técnicas y de esta manera pueda ser llevarlo rápidamente a la
implementación.
Las estrategias de búsqueda clásicas que se abordarán son: búsqueda en profundidad, búsqueda en
amplitud, búsqueda con retroceso, búsqueda primero el mejor y A*, además de Minimax.

Índice general
Índice deTablas

II

Índice de Figuras

III

1. Introducción

1

2. Formulación y resolución de problemas.
2.1. Definición formal del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Análisis del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
5

3. Problemas de juego y problemas reales.
3.1. Problemas de juguete . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Problemas del mundo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
8
9

4. Búsqueda en profundidad
4.1. Evaluación de una búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. La técnica de búsqueda primero en profundidad . . . . . . . . . . . . . . . . . . . . . . . .

11
11
125. Búsqueda en amplitud
5.1. La técnica de búsqueda primero en amplitud . . . . . . . . . . . . . . . . . . . . . . . . .

16
16

6. Búsqueda con retroceso(Backtracking)
6.1. La técnica de búsqueda con retroceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18
18

7. Búsqueda primero el mejor
7.1. La técnica de búsqueda primero el mejor . . . . . . . . . . . . . . . . . . . . . . . .. . . .

20
20

8. Búsqueda A*
8.1. La técnica de búsqueda A-Estrella(A*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23
23

9. Búsqueda Minimax
9.1. La técnica de búsqueda Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25
25

Conclusión

27

Apéndices

29

i

Índice de Tablas
4.1. Distancias aproximadas entre terminales de la línea ADO-GL R . . . . . . .. . . . . . . .

12

9.1. Tabla comparativa de estrategias de búsqueda en espacios de estados . . . . . . . . . . . .
9.2. Tabla de las posibles combinaciones de tres objetos . . . . . . . . . . . . . . . . . . . . . .

27
31

ii

Índice de figuras
1.1. Plano de casa del problema de las llaves perdidas . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Grafo del camino solución paraencontrar las llaves perdidas . . . . . . . . . . . . . . . . . . .
4.1.
4.2.
4.3.
4.4.

1
2

Rutas de la línea de autobuses ADO-GL R . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Árbol parcial de rutas de ADO-GL R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Representación de la estructura de pila del problema del agente de viajes . . . . . . . . . . . . .
Representación de...