1. No category

Ministerio de Educación Superior
Universidad de Guantánamo
Facultad de Informática
Resumen de
Inteligencia Articial
Carrera: Ingeniería en Informática.
Autor: Wily Lobaina Pérez
Año: Tercero
Semestre: II
Guantánamo junio de 2015
“Año del 57 Aniversario del triunfo de la Revolución”
Sumario
1. Métodos de solución a problemas de búsqueda sobre espacios de estado
 Búsqueda no informada( búsqueda a ciegas)
 Búsqueda a lo profundo( depth-first search)
 Qué hacer si cae en un ciclo infinito?
 Búsqueda a lo ancho( breadth-first search)
 Búsqueda informada(heurística)
 Primero al mejor
Heurística admisible
Distancia de Manhattan(Distancia de Taxicab)
2. Formas de representación del conocimiento.
 Lógica(Proposicional, Cálculo de predicados, etc.).
 Redes Semánticas
 Frames(Marcos o armazones)
 Guiones (Scripts)
3. Sistemas de Expertos. Sistemas basados en reglas.
o Motor de inferencia. Encadenamiento de reglas.
Búsqueda primero a lo ancho (breadth first search).
Estrategia FIFO [ First In First Out ] -> (Cola)
Equivalente al recorrido de un árbol por niveles
Se basa en desarrollar completamente cada nivel del árbol antes de pasar a
desarrollar el siguiente.
Una búsqueda primero a lo ancho (breadth-first) genera y explora primero todos
los sucesores del nodo raíz. Si no se encuentra la meta, pasa a los sucesores del
segundo nivel y así sucesivamente por niveles. Suponiendo que el objetivo a
alcanzar es el nodo 7, el recorrido primero a lo ancho del espacio de búsqueda
que se muestra en la figura 1.3, es 1-2-3-4-5-6-7.
Fig. 1.3. Un ejemplo de espacio de búsqueda
Si el número máximo de hijos (o ramas) de un nodo es b y la profundidad de la
solución es d, entonces el número de nodos en el nivel d es
y la cantidad de
tiempo usada en la búsqueda es en el caso peor:
1+b+
+ ... +
, la cual para grandes valores de d, puede ser aproximada por
. Es por esto que la complejidad temporal de este método de búsqueda es
O( ).
Ventajas
- Si existe una solución este método garantiza encontrarla y si hay varias
soluciones siempre encontrará la menos profunda en el árbol de búsqueda.
(Si hay una solución la encuentra. Es más, si hay varias encuentra la óptima.)
- El método es efectivo cuando el factor de ramificación, o sea, el número
promedio de hijos de un nodo, es pequeño, pues entonces la cantidad de nodos
por niveles será pequeña y es mejor explorar un nivel antes de pasar al siguiente.
Desventajas:
- Necesita mucha memoria. Como cada nivel del árbol tiene que ser almacenado
completamente para poder generar el próximo nivel y la cantidad de memoria es
proporcional al número de nodos almacenados, su complejidad espacial es
también O( ).
- Requiere mucho trabajo, especialmente si el camino más corto a la solución es
muy largo, puesto que el número de nodos que necesita examinar se incrementa
exponencialmente con la longitud del camino.
Implementación
Una forma de implementación de este método es usar un conjunto de caminos
candidatos:
- Si el primer camino está encabezado por un nodo objetivo, ésta es la solución del
problema.
- Si no,
a) Remover el primer camino del conjunto de caminos candidatos, generar
el conjunto de todas las posibles extensiones un nivel más de este camino y
añadir las mismas al final del conjunto.
b) Repetir el proceso.
Tomando el ejemplo mostrado en la figura 1.3 este proceso se desarrollaría como
sigue:
a) Conjunto de caminos candidatos (CCC) inicial [[1]]
b) b) Generando las extensiones de [1]
[[2,1] , [3,1]]
c) Al remover el primer camino candidato y generar sus extensiones: [[4,2,1]
,[5,2,1]] se obtiene el nuevo CCC:
[[3,1] , [4,2,1] , [5,2,1]]
d) Removiendo y generando nuevamente las extensiones [[6,3,1] , [7,3,1]] se
obtiene el CCC:
[[4,2,1] , [5,2,1] , [6,3,1] , [7,3,1]]
e) Así sucesivamente son obtenidos los siguientes conjuntos hasta llegar a:
[[7,3,1] , [8,4,2,1] , [9,4,2,1] , [10,5,2,1], [11,6,3,1]]
En este caso el camino inicial tiene como cabeza el nodo objetivo y el
proceso termina en esta solución.
Propiedades de la Búsqueda a lo Ancho
 Completa?
Sí, mientras b sea finito
 Complejidad temporal?
1+b+
+
+...+
= O( )
 Complejidad espacial?
O( ) (todos los nodos en memoria)
 Óptima?
Sí (con costo unitario por paso), subóptima en general
 FIFO
Recorridos sobre grafos. Búsqueda primero en anchura
Nodo inicial (raíz): s
Nodo final (meta): x
Cola Q={[s]}
Cola Q={[r,s],[w,s]}
Cola Q={[w,s],[v,r,s]}
Cola
Q={[v,r,s],[t,w,s],[x,w,s]}
Solución: S={[x,w,s]}
Búsqueda primero en profundidad (depth-first search).
Estrategia LIFO [ Last In First Out ] -> (Pila)
Equivalente al recorrido en pre-orden de un árbol.
Se basa en elegir un camino en el árbol y seguirlo hasta el final. Si no se
encuentra la solución se procede y se prueba por otro camino.
Nota: Es más eficiente en un árbol con poca ramificación.
Búsqueda primero en profundidad (depth-first) explora, primeramente, el nodo raíz
y luego genera el sucesor de éste ubicado en la rama más a la izquierda. Si este
nodo es el objetivo, entonces hemos encontrado el camino. Si no, se continúa
extendiendo este camino tomando siempre el primer sucesor. Si el nodo no tiene
más sucesores, se pasa al siguiente sucesor de su predecesor, o sea, se
retrocede al nivel anterior para tomar el otro sucesor y así sucesivamente, hasta
alcanzar el objetivo o hasta que se realice un corte a alguna profundidad
determinada.
Ventajas
- Requiere mucha menos memoria (sólo hay que guardar el camino actual).
- Puede encontrar una solución sin examinar mucho el árbol, sobre todo si hay
varios caminos a la solución.
La ventaja de este método está en la eficiencia que se alcanza en el uso de la
memoria. Si la longitud máxima de una rama del árbol es d nodos, como sólo se
necesita almacenar el camino actual, entonces la complejidad espacial del
algoritmo es O(d). En la práctica la búsqueda por este método se limita por el
tiempo y no por el espacio.
Desventaja
La desventaja del método es que si existen ramas infinitas, puede no encontrar la
solución al problema, aun teniéndola. Es por esto que, en ocasiones, se requiere
que se defina un corte a una profundidad arbitraria para evitar, lo más posible,
caer en caminos o lazos infinitos. Si la profundidad de corte seleccionada c es
menor que la profundidad de la solución d, el algoritmo terminará sin encontrar
una solución, mientras que si c > d, se paga un precio alto, O( ), en términos del
tiempo de ejecución, donde b es el número máximo de hijos (o ramas).
Qué hacer si cae en un ciclo infinito? Hacer un corte
-Si existen ciclos no se encuentra la solución, y el programa cae en un ciclo
infinito, para darle solución a esto es necesario programar un corte en caso de
existir ciclos o para prevenir ciclos. Ej: Si se han pasado por 500 estados hacer un
corte.
Propiedades de la Búsqueda en Profundidad





Completa?
No; falla en espacio de infinita profundidad o con lazos
Complejidad temporal?
O( ): terrible si m es mucho mayor que d
Complejidad espacial?
O( ) (i.e., espacio lineal)
Óptima?
No
LIFO
Comparación entre búsqueda en profundidad y búsqueda a lo ancho
La búsqueda primero en profundidad es mejor cuando el nodo objetivo está
situado en la porción inferior izquierda del árbol de búsqueda, mientras que la
búsqueda primero a lo ancho es mejor cuando el nodo objetivo está situado en la
porción superior derecha de dicho árbol.
Recorrer un grafo en PreOrden
void preOrder(PNodo tree) {
if (tree != NULL) {
printf(“%d”,tree->Value);
preOrder(tree->Left);
preOrder(tree->Right);
}
}
Imprimir en PreOrden:
6 2 1 4 3 5 7
6
2
1
3
4
5
7
Recorridos sobre grafos. Búsqueda primero en profundidad
Nodo inicial (raíz): s
Nodo final (meta): x
Pila S={}
Pila S={s}
Pila S={r,s}
Pila S={v,r,s}
Pila S={w,s}
Pila S={t,w,s}
Pila S={u,t,w,s}
Pila S={y,u,t,w,s}
Pila S={x,y,u,t,w,s}
Búsqueda por el mejor nodo(best-first search).
Utiliza dos estructuras auxiliares:
Abiertos : es una cola de prioridad para los nodos no visitados.
Cerrados : es el conjunto de los nodos visitados.
La búsqueda por el mejor nodo es una forma de combinar las ventajas de las
búsquedas en profundidad y de anchura en un único método. En cada paso del
proceso de búsqueda por el mejor nodo, seleccionamos el más prometedor de
aquellos nodos que se han generado hasta el momento. Esto se realiza aplicando
una función heurística apropiada a cada uno de ellos. Entonces expandimos el
nodo elegido usando las reglas para generar a sus sucesores. Si uno de ellos es
una solución podemos terminar. Si no, todos esos nodos se añaden al conjunto de
nodos generados hasta ahora. Se selecciona de nuevo el más prometedor y el
proceso continúa. Lo que sucede usualmente es que se realiza un proceso de
búsqueda en profundidad mientras se explora una rama prometedora. Como
ocasionalmente no se encuentra solución, se explora otra rama previamente
ignorada y que ahora parece más prometedora.
En este método de búsqueda la función heurística que estima los méritos de cada
nodo generado está definida como:
S
g(n)
f(n) = g(n) + h(n),
n
h(n)
Dónde:


t
g(n) es una medida del costo del camino desde el nodo inicial al nodo
actual n
h(n) es un estimado del costo adicional de llegar desde el nodo n al nodo
meta.
g(n) no es, necesariamente, el costo del camino óptimo desde el nodo inicial al
nodo actual, pues puede haber caminos mejores no recorridos todavía. g(n)
simplemente se calcula como la suma de los costos de los arcos del camino
actual. La función h(n), sin embargo, es típicamente heurística y explota el
conocimiento sobre el domino del problema, ya que el “mundo” entre el nodo n y el
meta no ha sido explorado. Por supuesto, no existe un método general para
construir h(n), sino que depende del problema particular.
Al algoritmo de búsqueda que utiliza la función f(n) se le llama algoritmo A. Este
algoritmo no garantiza encontrar el camino óptimo a la solución, pues éste sólo
calcula un estimado del costo para alcanzar el nodo objetivo.
La figura 3.12 muestra el principio de un procedimiento de búsqueda por el mejor
nodo. Los números que aparecen al lado de los nodos son los valores de f(n).
Note cómo en cada paso se selecciona el nodo de menor valor de f(n), generando
sus sucesores.
Para implementar este algoritmo hay que mantener, además de la lista de nodos
visitados, una lista de nodos generados pero no visitados. Esta lista permite al
algoritmo retomar un camino que fue abandonado temporalmente por otro que
parecía más promisorio. Este método de búsqueda consiste en: el mejor nodo de
la lista de nodos generados y no visitados (inicialmente el nodo raíz) se expande
generando sus sucesores y se colocan en la lista de nodos visitados; la función de
evaluación heurística se aplica a todos los sucesores y ellos son insertados en la
lista de nodos no visitados en orden de su costo.
Por ejemplo, para el problema del rompecabezas de 8 piezas puede tomarse h*(n)
como el número de piezas que no están en su posición final. Otra variante, que
contiene más información heurística pero requiere más cálculos, es la suma de las
distancias desde la posición actual de cada pieza a su posición correcta.
Ventajas/Desventajas de Primero al mejor
Ventajas
 Algoritmo completo(encuentra la solución)
 Algoritmo optimo(encuentra la mejor solución)
Desventajas
 Explora en todas direcciones(no tiene en cuenta cual es nuestro objetivo)
• positivo: ahorra esfuerzo de búsqueda
• negativo: coste de cálculo de la heurística en cada nodo
Definición (Heurística)
Heurística
Una heurística será una función que utilizaremos para estimar cómo de cerca
estamos de la solución.
Heurística: función que asigna a cada estado una estimación del coste óptimo a
la solución.
Heurística:
Las heurísticas son criterios, métodos o principios para decidir cuál de entre varias
acciones promete ser la mejor para alcanzar una determinada meta.
Definición (Heurística admisible)
Heurística admisible
Se dice que una heurística es admisible si nunca sobreestima el costo de
alcanzar el objetivo, o sea, que en el punto actual la estimación del costo de
alcanzar el objetivo nunca es mayor que el menor costo posible.
Heurística admisible
es menor o igual que la distancia real mínima a la meta.
Heurística admisible
Una heurística es admisible si h(n) ≤ h*(n) donde h*(n) es el coste verdadero de la
solución desde n.
Nota: h representa el estado previo y h* el estado sucesor
Heurístico admisible:
Estimación del coste del nodo al objetivo que no supera el coste real
Cuando h(n) es admisible, asegura que la solución encontrada es la óptima.
El valor de la H puede ser estimado de diferentes maneras; dentro de las más
comunes se encuentra la heurística euclidiana, la heurística Manhattan
(distancia de ciudad, distancia Manhattan, distancia taxi, o longitud Manhattan) y la
heurística en diagonal.
Funciones heurísticas


Distancia de Hamming: el número de fichas que no están en su lugar.
Distancia Manhattan: la suma de las distancias desde la posición actual de
cada ficha hasta su posición original.
Queda claro que la Distancia de Hamming es admisible, dado que el número
total de movimientos para ordenar las fichas correctamente es al menos el número
de fichas que no están en su lugar (si cada ficha no está en su posición original
deberá ser movida al menos una vez). La Distancia Manhattan también será una
heurística admisible porque cada ficha será movida el menos la cantidad de pasos
entre ella misma y su posición original. Considere el siguiente rompecabezas:
4
7
15
2
6
12
13
10
3 8
9 14
1 5
11
La distribución de las distancias Manhattan para cada ficha quedaría así:
3 1 0 1
2 3 3 4
3 2 4 4
4 1 1
La distancia total de Manhattan para el puzle quedaría:
Funciones heurísticas
Ejemplos de heurísticos admisibles para el puzzle de las 8 piezas:
h1(n) = número de piezas en posición incorrecta
h2(n) = suma de las distancias de las piezas a sus posiciones finales, usando la
distancia de Manhattan de la pieza: suma de las distancias horizontal y vertical a
la posición final.
5
4
6
1
8
7
3
2
Estado inicial
1
8
7
2
3
4
6
5
Estado final
h1(Start) =?? 7
h2(Start) =?? 2+3+3+2+4+2+0+2 = 18
Ejemplos de funciones heuristicas
a) La basada en la distancia Manhattan (o distancia taxi). Se asocia a cada
casilla un número que es la suma de las distancias horizontal y vertical a su
posición en el tablero objetivo (esto es, la suma de diferencias de sus
coordenadas x e y). La función heurística es la suma de las distancias de cada
una de las casillas (excluyendo la que se encuentra vacía).
b) Otra heurística, mucho más simple, consiste en contar el número de casillas
que están fuera de su sitio (respecto al tablero objetivo). Es una heurística más
pobre que la anterior, puesto que no usa la información relativa al esfuerzo
(número de movimientos) necesario para llevar una pieza a su lugar.
c) Otra función heurística consiste en asignar a cada estado un valor que es la
distancia aérea (en línea recta) con el estado objetivo. Dicha distancia es la
distancia euclídea entre las coordenadas de dos ciudades.


Distancia euclídea
Distancia de Manhattan
Pasos para resolver un problema de búsqueda sobre espacios de estado
1. Formalizar el problema
Que es lo que tengo, que tipo de estructura voy a utilizar (listas, estructuras,
arreglos)
Estado Inicial, Estado Final.
2. Movimientos Legales
3. Hacer un grafo, describir el algoritmo a utilizar(búsqueda a lo profundo,
búsqueda a lo ancho, primero al mejor)
El espacio de estado del problema es el conjunto de todos los estados
alcanzables a partir del estado inicial mediante una secuencia de acciones
cualquiera.
Conceptos básicos (espacio del problema)
• Estado: una posible configuración de un problema
• Espacio de estados: todas las configuraciones
• Operadores:
• acciones legales
• generan estados sucesores de un estado
• Estados inicial y objetivo
• Solución:
• secuencia operadores de inicial a objetivo: path-finding, games
El juego del 8 Puzzle
1. Formalización del problema
• Estado inicial / objetivo:
El objetivo es llegar de un estado inicial cualquiera al estado final:
5
4
6
1
8
7
3
2
Estado inicial
1
8
7
2
3
4
6
5
Estado final
Estructura a utilizar: Lista
Estado inicial: [5,4,0,6,1,8,7,3,2]
Estado final:
[1,2,3,8,0,4,7,6,5]
Nota: otra forma de representar pudiera ser: Matriz
Representación de estados:
A(1; 1) = 5
A(2; 1) = 6
A(3; 1) = 7
A(1; 2) = 4
A(2; 2) = 1
A(3; 2) = 3
A(1; 3) = 0
A(2; 3) = 8
A(3; 3) = 2
2. Movimientos Legales
Para pasar de un estado a otro solo tenemos que desplazar una pieza a la celda
vacía.
– 4 movimientos posibles a partir de cualquier estado:
arriba, abajo, a la izquierda, a la derecha.
• Operadores:
• arriba: ^
• abajo: v
• derecha: >
• izquierda: <
Para ello solo se podrán mover las fichas contiguas al espacio vacio:
2
4
7
2
7
1
4
5
6
8
3
2
4
7
1
5
1
6
8
3
5
2
4
7
6
8
3
1
8
5
6
3
2
4
7
1
5
6
8
3
Sucesores
3. Hacer un grafo
• Espacio de estados: posibles configuraciones
• Solución: secuencia mínima de movimientos para llegar al estado objetivo
Estado inicial
1
8
7
1
8
7
2
6
5
3
4
1
8
7
2
5
1
8
7
2
6
5
1
8
2
6
7
3
6
4
3
4
3
4
5
2
3
6
4
5
1
7
2
8
5
3
6
4
1
8
7
2
6
5
3
4
1
8
7
2
6
3
4
5
1
8
7
2
3
4
5
6
Estado objetivo
1
8
7
2
5
3
6
4
Formas de representación del conocimiento. Importancia. Saber
cuándo usar cada una.




Redes Semánticas.(Representa el conocimiento a través de la tripleta
OAV) -> una ayuda grafica para visualizar una base de conocimiento.
Sistema basado en Reglas(Sistema de Expertos basado en Reglas)
Lógica Descriptiva(Modelar conocimiento)
Ontología(Para Web)
Nota: En Prolog se describe el conocimiento con lógica de 1er Orden.
En la ontología para la Web se describe el conocimiento con lógica Descriptiva.
Clasificación de las formas de representación del conocimiento.
Las F.R.C. pueden clasificarse en:
- Lógica (Proposicional, Cálculo de predicados, No Monotónica, etc.).
- Redes semánticas (Semantic Networks).
- Marcos o armazones (Frames).
- Guiones (Scripts).
Redes semánticas.
Planteamiento de un problema.
En la práctica, nos encontramos con problemas donde es necesario representar el
conocimiento a través de los conceptos, sus rasgos y las relaciones que pueden
establecerse entre ellos. Por ejemplo, ¿cómo representar todo el conocimiento
acerca del concepto de silla?.
Definición.
Una red semántica consiste de puntos llamados nodos, conectados por enlaces
llamados arcos que describen las relaciones entre los nodos. Los nodos
representan objetos, conceptos, eventos, acciones o atributos. Los arcos pueden
definirse de varias formas, dependiendo de la clase de conocimiento
representado, por ejemplo, arcos comunes usados para representar jerarquías son
esun y partede. La forma de representar una red semántica es un grafo orientado
cuyos arcos son etiqueteados con los nombres de las relaciones.
Veamos en la figura 2.3 la red semántica que describe el problema inicial.
Fig. 2.3. Red semántica que describe el concepto de silla.
Analicemos otro ejemplo. Supongamos que tenemos el siguiente conocimiento
expresado a través de los siguientes hechos:
1) Víctor es un pingüino.
2) Todos los pingüinos son pájaros.
3) Todos los pájaros son animales.
4) Todos los mamíferos son animales.
5) Todos los perros son mamíferos.
6) Sultán es un sato.
7) Todos los satos son perros.
8) Una raza de perro es el pastor.
9) A Víctor le agrada Sultán y a Sultán le agrada Víctor.
10) Un pájaro puede volar.
11) Un perro puede correr.
Como podemos ver los hechos 2, 3, 4, 5, 7 y 8 encierran relaciones del tipo esun.
Los hechos 10 y 11 son relaciones de propiedad. El 1 y el 6 reflejan instancias de
un concepto y el hecho 9 encierra relaciones entre individuos. Vea la red
semántica que representa este conocimiento en la figura 2.4.
Criterios sobre el dominio de aplicación.
En sus inicios (finales de los años 50 e inicios de los 60), las redes semánticas
fueron utilizadas en sistemas de traducción automática. El primero de ellos, se
desarrolló en la Universidad de Cambridge donde se definió un diccionario
conceptual de 15000 entradas a partir de 100 tipos de conceptos primitivos.
Las redes semánticas han sido utilizadas además, en:

En el procesamiento (comprensión) del lenguaje natural.
Las redes semánticas son útiles para representar los contenidos de una oración
declarativa típica. Ej: Jonh le dio el libro a Mary.



La programación y aprendizaje automáticos.
Para sintetizar respuestas.
Memoria asociativa
Por sus características, las redes semánticas han sido propuestas como un
mecanismo para simular algunas de las propiedades asociativas de la memoria
humana.