Paradigmas de Inteligencia
Artificial o Heurísticas Generales
- Prueba y Error
- Dividir y conquistar
Sistemas de Producción
- Situaciones: Foto del problema en un momento
dado - Movidas: Cambios entre Situaciones
- Sistemas de Control
- Punto de Partida (BDGi)
- Conjunto de Reglas (Movidas)
- Condición de Terminación
- Estrategia de Control
Base de Datos Global
(BDG): Son los datos que representan una
situación
Estrategia de Control: El caso a estudiar es
Backtraking
Reglas: Reglas de Producción
Son definidas mediante: IF condición
THEN acción
Donde la condición es una
expresión booleana de la BDG sindo verdadera cuando la
movida es permitida y la acción es una
actualización de la BDG que actualiza los resultados en
la BDG.
Relación:
Situación Þ
Datos Þ BDG
Movidas Þ Código
Þ Reglas de
Producción
Estrategias de Control
Las estrategias de
control son métodos
para encontrar caminos, que se traducen como métodos de
búsqueda por prueba y error en forma de
heurísticas básicas.
Los métodos que habiendo solución la
encuetran se denominan admisibles.
Los métodos que encuentran la mejor
solución se denominan optimales.
En estos casos una vez realizada la movida no se
puede volver atrás, ya que no guardan una copia de la
base inicial, por ejemplo el método de Hill Climbing.- Métodos irrevocables
- Métodos Tentativos
En estos procedimientos
se guarda una copia de la Base inicial, permitiendo el paso
atrás, por ejemplo Backtraking y la Búsqueda en
Grafo (Informado o Desinformado)
Desarrollo de los Métodos
- Hill Climbing
Siendo f la función de evaluación en el nodo
ni
¦ : Estado
® R
El valor
máximo de la función evaluación se
encuentra en el nodo final
¦ (nf)
= Máximo
Procedimiento
- Se toma la BDGi. Si cumple con la
condición de terminación, se detiene, sino
aplico todas las reglas que sean aplicables y obtengo
nuevas bases - Se evalúa la función de
evaluación de cada base y tomo la regla y la base
con la cual obtengo el mayor valorCondiciones de la función de
evaluación- Que no tenga máximos ni mínimos
locales - Que no tenga mesetas
- Que no presente puntos de
ensilladura
- Que no tenga máximos ni mínimos
- Vuelvo a aplicar el punto 1 para la nueva
base
- Backtraking
Procedimiento
- Se toma la BDGi.Si cumple con la condición
de terminación se detiene sino se aplica la
primera regla de las reglas y se obtiene una nueva
baseNo se puede profundizar
cuando:- No quedan reglas
apicables - Se repiten bases en la
rama jerárquica - Se supera un nivel de
profundidad
- No quedan reglas
- Se toma la primera base y se repite, cuando no
se puede profundizar más, vuelve a la base
anterior y elige la regla siguiente.
- Desinformado o de Fuerza
Bruta o Búsqueda a Ciegas
- Se toma la BDGi. Si cumple con la
- Búsqueda en Grafo
1.1. Deep First (Primero en Profundidad)
- Si BDGi cumple con la condición de
terminación termina sino aplica todas las reglas y
guarda en memoria la
lista de bases abiertas - Se elige una de las bases más profundas, por
convención, la de la izquirda y repito - Se continúa hasta que no se pueda
profundizar más y se continúa con la más
profunda
1.2. Wide First (Primero en Ancho)
Es un método admisible
- Si la BDGi verifica la condición de
terminación termina sino aplico todas las reglas
aplicables y la BDGi se destruye - Se forma una nueva lista de bases y se elige la
menos profunda
- Informado o Focalizafo
El Método A*
A* es un método admisible y optimal
Se le asignan a las movidas un Costo
Ci siendo Ci > x >0 siendo x
costos
possitivos no infinitésimos.
El costo de la movida esta asociado al costo de las
reglas y estas al costo del arco.
La solución de menor cantidad demovidas se
plantea como la suma de los costos de las movidas con valor
unitario.
La búsqueda focalizada implica una
función heurística ¦ (nodo) que devuelve como
resultado el costo estimado del mejor camino que pasa por el
nodo y va desde el nodo inicial al nodo
final.
Siendo ¦
(nodo) = g(nodo) + h(nodo)
La función g(nodo) que devuelve el costo
estimado del mejor camino que va desde el nodo inicial al
nodo sumando el costo de las reglas.
La función h(nodo) es el costo estimado
del mejor camino que va desde el nodo hasta el nodo
final. Es la función hurística propiamente dicha,
ya que ayuda dada al sistema.
Para todo nodo:
g(nodo) ³
g*(nodo)
h(nodo) £
h*(nodo)
Siendo g* el costo real del camino del nodo
inicial al nodo y h* el costo real de la ruta del
nodo al nodo final
Admisibilidad del Algoritmo
A*
Para garantizar que el algoritmo A* encuentre siempre
el camino de mínimo coste, tanto el grafo como la
función h* deben satisfacer ciertas
condiciones:
- Cada nodo del grafo tiene un número finito
de sucesores - El coste de cada arco del grafo es mayor que una
cierta cantidad positiva x - La función h(nodo) debe satisfacer la
siguiente condición: en todos los nodos del grafo de
búsqueda se tiene que cumplir que h(nodo)
£ h*(nodo), es decir, la
función h(nodo) nunca sobreestimará el
valor real, que viene dado por la función
h*(nodo)
Complejidad Computacional en el Tiempo y en el
Espacio
Siendo
Tiempo = ¦
1(s)
Espacio = ¦
2(s)
Estudios Asintóticos
T = lim s®
¥ ¦ 1(s)
M = lim s®
¥ ¦ 2(s)
L = Es el nivel que lleva encontrar la
solución
Teorema de la Aceleración (Speed Up)
Dado un T decodificando la entrada se puede conseguir
T/K, depreciando los términos por el teorema de menor
orden y por Speed Up, los factores que multiplican los de mayor
orden
Complejidades de los distintos
métodos
Hill Climbing :
El tiempo es proporcional a la lista y estas
proporcionales a las reglas aplicables. El factor de
ramificación (Brenching Factor) es b * L, b (cantidad de
bases abiertas o reglas aplicadas) y L el nivel.
T = ¶ (b*L), s = b*L que
crece linealmente
M = ¶ (b), s = b que se
mantiene constante, no utilizando más memoria con la
profundidad alcanzada
Backtraking
s = 1+ b + b2 + … + bL
Þ bs = b + b2 +
… + bL+1 Þ
(b-1)s = bL+1 –1 Þ s = bL+1 –1 / (b-1) =
bL
T = ¶ (bL)
que es de carácter exponencial , no
factible
M = ¶ (L) es de
crecimiento lineal
Profundidad Primero
T = ¶ (bL) es
exponencial por lo tanto, no factible
M = ¶ (bL) es
exponencial
Ancho Primero
T = ¶ (bL) es
exponencial, no factible
M = ¶ (bL) es
exponencial, no factible
i
s = S b i => s
= bL+1 –1 / (b-1) =
bL
0
Método A*
T depende de h(nodo) ¶
(b*L) £ T £ ¶
(bL)
M depende de h(nodo) ¶
(b) £ M £ ¶
(bL)
Resumen :
Cuadro Comparativo
Método | Riesgo Rama Infinita | Nivel de Profundidad | Admisible | Optimal | Necesidad de | Complejidad en Tiempo | Complejidad en |
Hill Climbing | NO | NO | SI | SI | SI | ¶ | ¶ (b) |
BackTraking | SI | SI | NO | NO | NO | ¶ | £ ¶ (L) |
Deep First | SI | SI | NO | NO | NO | ¶ | ¶ |
Wide First | NO | NO | SI | SI | NO | ¶ | ¶ |
A* | NO | NO | SI | SI | NO | ¶ (b*L) | ¶ (b) |
Ejemplos:
Los Misioneros
A la orilla de un río encontrabasé un
grupo de tres
misioneros y otro de tres caníbales los cuales
querían cruzar a la otra orilla del río, para ello
diponían de una balsa la cual podía llevar solo a
dos personas. Si el número de caníbales no puede
sobrepasar el número de misioneros sino estos
serían deborados ¿ Cómo hicieron los
misioneros y los caníbales para cruzar?.
Sistema de Producción
1. Base de Datos
Global:
Una variable M [0,1,2,3] que indique la cantidad
de misioneros a la derecha
Una variable C [0,1,2,3] entera que indique la
cantidad de caníbales a la derecha
Una variable B [0,1] que indique si el bote se
encuentra a la derecha
2. Conjunto de Reglas (Movidas):
pasa Misionero : IF M>0 AND B=0
AND M>C THEN M=M-1; B=1
vuelve Misionero : IF M>0 AND B=1
AND M<C THEN M=M-1; B=0
pasa Canibal y Misionero: IF M>0 AND
B=0 AND C>0 THEN M=M-1;
C=C-1;B=1
pasa Canibal : IF M>0 AND B=1
AND M>C THEN M=M-1; B=0
vuelve Canibal : IF M>0 AND B=1
AND C>0 THEN M=M-1;
C=C-1;B=0
3.
- BDGi : M=3,C=3,B=0
- Condición de Terminación: M=0
AND C=0 - Estrategia de Control:
Hill Climbing
Backtraking
DeepFirst
Wide First
A*
El Ascensor
Un ascensor sube con dos ó tres personas y baja
con sólo una persona.
Hay siete personas en planta baja y seis deben subir
mientras que sólo una debe quedar de guardia .
Sistema de Producción
1. Base de Datos Global:
Una variable P [0,1,2,3,4,5,6,7] que indique la
cantidad de gente en Planta Baja.
Una variable A [0,1] que indique si el asensor se
encuentra en Planta Baja.
2. Conjunto de Reglas (Movidas):
Suben 2: IF P>=2 AND A=0 THEN
P=P-2 ; A=1
Suben 3: IF P>=3 AND A=0 THEN
P=P-3 ; A=1
Baja1: IF P<=6 AND A=1 THEN
P=P+1; A=0
3.
- BDGi: P=7,A=0
- Condición Terminación:
P=1 - Estrategia de Control:
Hill Climbing
Backtraking
DeepFirst
Wide First
A*
Gabriel Pineda
Página anterior | Volver al principio del trabajo | Página siguiente |