Inteligencia Artificial
` Enginyeria en Informatica
` APUNTS D’INTEL.LIGENCIA ARTIFICIAL
` Departament de Llenguatges i Sistemes Informatics
CURS 2009/2010 1Q
\
BY:
$
C
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.
\
$
CThis work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. BY:
Índice general
0. Introducción
1
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 . . . . .
3
5 5 6 9 13 13 13 14 16 17 23 23 2324 24 27 27 28 29 29 29 30 35 35 36 38 40 41 41 42 43 43
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
.. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . .. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
4. Búsqueda local 4.1. El tamaño importa, a veces . . . . . .4.2. Tu sí, vosotros no . . . . . . . . . . . . 4.3. Demasiado calor, demasiado frío . . . . 4.4. Cada oveja con su pareja . . . . . . . . 4.4.1. Codificación . . . . . . . . . . . 4.4.2. Operadores . . . . . . . . . . . 4.4.3. Combinación de individuos . . . 4.4.4. El algoritmo genético canónico . 4.4.5. Cuando usarlos . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
5. Búsqueda con adversario 45 5.1. Tú contra mi o yo contra ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2. Una aproximación trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1
2
Índice general 5.3. Seamos un poco más inteligentes . . . . . . ....
Regístrate para leer el documento completo.