Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Inteligencia Artificial (página 2)




Enviado por Gabriel Pineda



Partes: 1, 2

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
  1. Punto de Partida (BDGi)
  2. Conjunto de Reglas (Movidas)
  3. Condición de Terminación
  4. 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.

  1. 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.

  2. Métodos irrevocables
  3. 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

    1. 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
    2. 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 valor

      Condiciones 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
    3. Vuelvo a aplicar el punto 1 para la nueva
      base
    • Backtraking

    Procedimiento

    1. 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
      base

      No se puede profundizar
      cuando:

      1. No quedan reglas
        apicables
      2. Se repiten bases en la
        rama jerárquica
      3. Se supera un nivel de
        profundidad
    2. 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.
    1. Desinformado o de Fuerza
      Bruta o Búsqueda a Ciegas
  1. Búsqueda en Grafo

1.1. Deep First (Primero en Profundidad)

  1. 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
  2. Se elige una de las bases más profundas, por
    convención, la de la izquirda y repito
  3. 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

  1. Si la BDGi verifica la condición de
    terminación termina sino aplico todas las reglas
    aplicables y la BDGi se destruye
  2. Se forma una nueva lista de bases y se elige la
    menos profunda

  1. 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:

  1. Cada nodo del grafo tiene un número finito
    de sucesores
  2. El coste de cada arco del grafo es mayor que una
    cierta cantidad positiva x
  3. 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
Función

Complejidad en Tiempo

Complejidad en
Espacio

Hill Climbing

NO

NO

SI

SI

SI


(b*L)

¶ (b)

BackTraking

SI

SI

NO

NO

NO


(bL)

£ ¶ (L)

Deep First

SI

SI

NO

NO

NO


(bL)


(bL)

Wide First

NO

NO

SI

SI

NO


(bL)


(bL)

A*

NO

NO

SI

SI

NO

¶ (b*L)
£ T £ ¶
(bL)

¶ (b)
£ M £ ¶
(bL)

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.

  1. BDGi : M=3,C=3,B=0
  2. Condición de Terminación: M=0
    AND C=0
  3. 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.

  1. BDGi: P=7,A=0
  2. Condición Terminación:
    P=1
  3. Estrategia de Control:

Hill Climbing

Backtraking

DeepFirst

Wide First

A*

Gabriel Pineda

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter