2. SISTEMAS DE PRODUCCION

2.1 INTRODUCCION

2.2 ÁRBOLES DE BUSQUEDA

2.3 ESTRATEGIAS DE CONTROL

2.4 SISTEMAS DE PRODUCCION DIRIGIDOS POR DATOS Y POR OBJETIVOS

2. SISTEMAS DE PRODUCCION

2.1 INTRODUCCION

Los sistemas expertos forman parte de un firme y verdadero avance en inteligencia artificial. Los sistemas expertos pueden incorporar miles de reglas. Para una persona seria una experiencia casi "traumática" el realizar una búsqueda de reglas posibles al completado de un problema y concordar estas con las posibles consecuencias, mientras que se sigue en un papel los trazos de un árbol de búsqueda. Los sistemas expertos realizan amablemente esta tarea; mientras que la persona responde a las preguntas formuladas por el sistema experto, esta busca recorriendo las ramas más interesantes del árbol, hasta dar con la respuesta a fin al problema, o en su falta, la más parecida a esta.

2.2 ÁRBOLES DE BUSQUEDA

Un árbol es una estructura no lineal acıclica utilizada para organizar información de forma eficiente.

La definición es recursiva:

Un árbol es una colección de valores fv1; v2; : : : vng tales que

Si n = 0 el árbol se dice vacío.

En otro caso, existe un valor destacado que se denomina raíz (p.e.

v1), y los demás elementos forman parte de colecciones disjuntas que a su vez son arboles. Estos arboles se llaman subárboles de raíz.

·         Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como arboles genealógicos, tablas, etc.

·         La terminología de los arboles se realiza con las típicas notaciones de las relaciones familiares en los arboles genealógicos: padre, hijo, hermano, ascendente, descendente, etc.

Algunas definiciones

o   Nodo, son los elementos del árbol.

o   Raíz del árbol: todos los arboles que no están vacios tienen un único

o   nodo raíz. Todos los demás elementos o nodos se derivan o descienden de el.

o   Nodo hoja es aquel nodo que no contiene ningún subárbol.

o   Tamaño de un árbol es su número de nodos.

o    A cada nodo que no es hoja se le asocia uno o varios subarboles llamados descendientes o hijos.

o   De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.

o   Todos los nodos tienen un solo padre excepto el raíz que no tiene padre.

o   Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico.

o   La altura o profundidad de un árbol es el nivel mas profundo mas uno.

Arboles Binarios

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho.

Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.

Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Arbol binario de búsqueda.

Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este árbol es un árbol binario de búsqueda.

Ejemplo:

Operaciones básicas

Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.

Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.

Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.

Recorrido de un Arbol Binario

Recorrido en amplitud

Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:

12 - 8,17 - 5,9,15

Recorrido en profundidad

Recorre el árbol por subárboles.

Hay tres Preorden, orden central y postorden.

Hay tres formas: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

1. Inorden

·         Recorrer el subarbol izquierdo en inorden.

·         Examinar la raíz.

·         Recorrer el subarbol derecho en inorden.

  Preorden

·         Examinar la raíz.

·         Recorrer el subarbol izquierdo en preorden.

·         recorrer el subarbol derecho en preorden.

  Postorden

·         Recorrer el subarbol izquierdo en postorden.

·         Recorrer el subarbol derecho en postorden.

·         Examinar la raíz.

·        

A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.

Inorden: GDBHEIACJKF

Preorden: ABDGEHICFJK

Postorden: GDHIEBKJFCA

Clasificación de Arboles Binarios

Existen cuatro tipos de árbol binario:.

·         Arbol Binario Distinto.

·         Arbol Binario Similares.

·         Arbol Binario Equivalentes.

·         Arbol Binario Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Arbol Binario Distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

Ejemplo:

Arbol Binario Similar

Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

Ejemplo:

Arbol Binario Equivalente

Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

Arbol Binario Completo

Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.

Terminología

La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente:

·         Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

·         Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

·         Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

·         Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

·         Nodo anterior: Es un nodo que no es raíz ni terminal.

·         Grado: Es el número de descendientes directos de un determinado nodo.

·         Grado de un árbol: Es el máximo grado de todos los nodos del árbol.

·         Nivel: Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

·         Altura: Es el máximo número de niveles de todos los nodos del árbol.

·         Peso: Es el número de nodos del árbol sin contar la raíz.

·         Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

2.3 ESTRATEGIAS DE CONTROL

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 encuentran se denominan admisibles.

Los métodos que encuentran la mejor solución se denominan optímales.

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.      

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

o    Backtraking

Procedimiento

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

a.      No quedan reglas apicables

b.      Se repiten bases en la rama jerárquica

c.       Se supera un nivel de profundidad

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

2.4 SISTEMAS DE PRODUCCION DIRIGIDOS POR DATOS Y POR OBJETIVOS

Los sistemas expertos, que reproducen el comportamiento humano en un estrecho ámbito del conocimiento, son programas tan variados como los que diagnostican infecciones en la sangre e indican un tratamiento, los que interpretan datos sismológicos en exploración geológica y los que configuran complejos equipos de alta tecnología.

Tales tareas reducen costos, reducen riesgos en la manipulación humana en áreas peligrosas, mejoran el desempeño del personal inexperto, y mejoran el control de calidad sobre todo en el ámbito comercial.

Diferentes teorías:

1.       Construir réplicas de la compleja red neuronal del cerebro humano (bottom-up).

2.      Intentar imitar el comportamiento del cerebro humano con un computador (top-down).

Diferentes metodologías:

1.       La lógica difusa: permite tomar decisiones bajo condiciones de incerteza.

2.      Redes neuronales: esta tecnología es poderosa en ciertas tareas como la clasificación y el reconocimiento de patrones. Está basada en el concepto de "aprender" por agregación de un gran número de muy simples elementos.

En un sistema dirigido por los datos, el filtrado consiste en retener todas las reglas cuyas premisas son verdaderas teniendo en cuenta los hechos (verdaderos) presentes en la base de datos. Este sistema funciona en encadenamiento hacia delante. Si el sistema es a la vez dirigido por los datos y por los objetivos, se denomina mixto. La restricción también puede estar especificada explícitamente por el experto para utilizar reglas dentro de las reglas, es decir, meta reglas. Indica qué grupo de reglas debe ser retenido, por prioridad, o definir un orden en los subconjuntos de las reglas.

 El conocimiento puede organizarse en forma de red como en las redes semánticas utilizadas en el análisis sintáctico del lenguaje. Su posición dentro de la red dirige las restricciones utilizando heurísticas. Esta formulación es particularmente eficiente si se establece válidamente una organización jerárquica del conocimiento, en este caso existiría una taxonomía de los hechos.

Otro modo de gobernar las restricciones es organizar las reglas en paquetes o esquemas, lo que genera una estructura de árbol en reglas, lo que es una ventaja.

Todos estos modos dependen de la forma en que está representado el conocimiento.