PDF de programación - Apuntes IA

Intel.lig`encia Artificial

Enginyeria en Inform`atica

APUNTS D’INTEL.LIG `ENCIA ARTIFICIAL

Departament de Llenguatges i Sistemes Inform`atics

CURS 2012/2013 1Q

c b e a

This work is licensed under the Creative Commons
Attribution-NonCommercial-ShareAlike License. c b e a

To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.0/ or
send a letter to:

Creative Commons,
559 Nathan Abbott Way, Stanford,
California 94305,
USA.

Índice general

0. Introducción

I Resolución de problemas
1. Resolución de problemas

1.1. ¿Qué es un problema? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. El espacio de estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Algoritmos de búsqueda en el espacio de estados . . . . . . . . . . . . . . . . . . . . .

2. Búsqueda no informada

2.1. Búsqueda independiente del problema . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Búsqueda en anchura prioritaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Búsqueda en profundidad prioritaria . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. Búsqueda en profundidad iterativa . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Búsqueda heurística

3.1. El conocimiento importa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. El óptimo está en el camino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Tú primero y tú después . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. El algoritmo A∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Pero, ¿encontraré el óptimo? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1. Admisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.2. Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.3. Heurístico más informado . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Mi memoria se acaba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1. El algoritmo IDA∗
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2. Otras alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Búsqueda local

4.1. El tamaño importa, a veces
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Tu sí, vosotros no . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Ejemplo: El problema de la mochila . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Un mundo de posibilidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1

3
5
5
6
10

13
13
13
14
17
18

23
23
23
24
25
27
27
28
29
29
30
31

35
35
36
39
42

2

4.4. Demasiado calor, demasiado frío . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1. Ejemplo: El viajante de comercio . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Cada oveja con su pareja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1. Codificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.2. Operadores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.3. Combinación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.4. El algoritmo genético canónico . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.5. Cuando usarlos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.6. Ejemplo: Las N reinas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Búsqueda con adversario

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Tú contra mi o yo contra ti
5.2. Una aproximación trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Seamos un poco más inteligentes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. Seamos aún más inteligentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. Satisfacción de restricciones

6.1. De variables y valores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Buscando de manera diferente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1. Búsqueda con backtracking
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2. Propagación de restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.3. Combinando búsqueda y propagación . . . . . . . . . . . . . . . . . . . . . . .
6.3. Otra vuelta de tuerca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4. Ejemplo: El Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II Representación del conocimiento
7. Introducción a la representación del conocimiento

7.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2. Esquema de representación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3. Propiedades de un esquema de representación . . . . . . . . . . . . . . . . . . . . . .
7.4. Tipos de conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.1. Conocimiento Relacional simple . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.2. Conocimiento Heredable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.3. Conocimiento Inferible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.4. Conocimiento Procedimental . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8. Lógica

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.
8.2. Lógica proposicional
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3. Lógica de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4. Lógica y representación del conocimiento . . . . . . . . . . . . . . . . . . . . . . . . .

9. Sistemas de reglas de producción

9.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.2. Elementos de un sistema de producción . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3. El motor de inferencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3.1. Ciclo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.4. Tipos de razonamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.4.1. Razonamiento guiado por los datos . . . . . . . . . . . . . . . . . . . . . . . .

43
44
46
47
48
49
50
50
51

55
55
56
56
58

63
63
64
65
67
69
71
71

73
75
75
76
78
78
79
79
79
80

81
81
81
83
84

85
85
85
87
88
89
90

9.4.2. Razonamiento guiado por los objetivos . . . . . . . . . . . . . . . . . . . . . .
9.5. Las reglas como lenguaje de programación . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
9.6. Las reglas como parte de aplicaciones generales

10.Representaciones estructuradas

10.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2. Redes semánticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3. Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3.1. Una sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

91
91
93

95
95
95
96
98

11.Ontologías

103
11.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11.2. Necesidad de las ontologías . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
11.3. Desarrollo de una ontología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
11.4. Proyectos de ontologías . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

III Sistemas basados en el conocimiento

113

12.Introducción a los SBC

115
12.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
12.2. Características de los SBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
12.3. Necesidad de los SBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
12.4. Problemas que se pueden resolver mediante SBC . . . . . . . . . . . . . . . . . . . . . 118
12.5. Problemas de los SBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
12.6. Áreas de aplicación de los SBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
12.7. Breve historia de los SBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

13.Arquitectura de los SBC

13.3. Arquitectura de los sistemas basados en casos

123
13.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
13.2. Arquitectura de los sistemas basados en reglas . . . . . . . . . . . . . . . . . . . . . . 124
13.2.1. Almacenamiento del conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . 124
13.2.2. Uso e interpretación del conocimiento . . . . . . . . . . . . . . . . . . . . . . . 125
13.2.3. Almacenamiento del estado del problema . . . . . . . . . . . . . . . . . . . . . 126
13.2.4. Justificación e inspección de las soluciones . . . . . . . . . . . . . . . . . . . . 126
13.2.5. Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
. . . . . . . . . . . . . . . . . . . . . . 127
13.3.1. Almacenamiento del conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . 128
13.3.2. Uso e interpretación del conocimiento . . . . . . . . . . . . . . . . . . . . . . . 129
13.3.3. Almacenamiento del estado del problema . . . . . . . . . . . . . . . . . . . . . 129
13.3.4. Justificación e inspección de las soluciones . . . . . . . . . .