Introducción a la Inteligencia Artificial

1-Introducción

1.1. Definición de Inteligencia Artificial (IA) y evolución histórica

1.2. Técnicas de resolución de problemas de IA

1.3. Criterios de éxito de la IA

1.4. Resolución de problemas de IA: 

      1.4.1. Definición formal del problema
      1.4.2. Estrategia de control: Métodos de búsqueda
      1.4.3. Análisis del problema

1.1. Definición de Inteligencia Artificial

En la bibliografía del área encontramos diferentes definiciones que pueden darnos una idea de lo que se llama inteligencia artificial: 

    * Una de las áreas de las ciencias computacionales encargadas de la creación de hardware y software con 
      comportamiento inteligentes.
    * El estudio de las computaciones que permiten percibir, razonar y actuar
    * Estudia como lograr que las máquinas realicen tareas que, por el momento,






 son realizadas mejor por los seres humanos.

Desde el punto de vista de los objetivos, la IA puede considerarse como parte de la ingeniería o de la ciencia: 

    * El objetivo ingenieril de la IA es resolver problemas reales, actuando como un armamento de ideas acerca de cómo representar 
      y utilizar el conocimiento, y de como ensamblar sistemas
    * El objetivo científico de la IA es explicar varios tipos de inteligencia. Determinar qué ideas acerca de la representación del 
      conocimiento, del uso que se le da a éste, y del ensamble de sistemas explican distintas clases de inteligencia.

Algunas aplicaciones de la inteligencia artificial: 

    * Tareas de la vida diaria (más dificil para una máquina que las tareas de un experto)
          o Percepción (visión y habla)
          o Lenguaje natural (comprensión, generación, traducción)
          o Sentido común
          o Control de un robot
    * Tareas formales
          o Juegos (ajedrez, backgammon, damas)
          o Matemáticas (geometría, lógica, cálculo, demostración de propiedades)
    * Tareas de los expertos (necesitan un conocimiento menor que el conocimiento necesario en las tareas más comunes)
          o Ingeniería (diseño, detección de fallos, planificación de manufacturación)
          o Análisis científico
          o Diagnosis médica
          o Análisis financiero

Desarrollo histórico de la Inteligencia Artificial según Jackson: 

    * 1950–1965. Periodo “clásico’‘

      - Gestación [McColluck y Pitts, Shannon, Turing]
      - 1956, la I.A. tuvo su boom a partir de la conferencia efectuada en Darmouth College. Estaban presentes importantes 
        científicos como McCarty (le dio el nomre a esta nueva area del conocimiento), Minsky (fundador del laboratorio de IA 
        del MIT), Shannon (laboratorios Bell), Rodhester (IBM), Newell (presidente de la A.A.A.I. Asociación Americana de IA),
        Simmon (premio nobel de Carnegie Mellon University)
      - Redes neuronales, robótica (Shakey)
      - Búsqueda en un espacio de estados, Heurísticas, LISP
      - Resolutor general de problemas (GPS) [Newell, Simon]. Resolución de problemas de sentido común, los cuales incluyen 
        razonamiento de objetos físicos y sus relaciones, como también razonamiento de acciones y sus consecuencias. Solo se 
        resolvieron tareas muy simples, pues no se pudo crear un programa con la cantidad suficiente de conocimiento de un dominio 
        específico
      - Se pone principal énfasis en la implementación de juegos (ajedrez, damas, etc.) así como en la demostración de teoremas matemáticos.
      - Limitaciones de pura búsqueda, explosión combinatoria.
    *   1965–1975. Periodo “romántico’‘

      - Representación “general’‘ del conocimiento.
      - Redes semánticas [Quillian]
      - Prototipos (frames) [Minsky]
      - Perceptrón [Minsky y Papert]
      - Lógica [Kowalski]
      - Mundo de bloques (SHDRLU) [Winograd]
      - Percepción (visión y habla), compresión de lenguaje natural, robótica.
      - Dificultades de representación “general, problemas de “juguete.



    * 1975-actualidad. Periodo “moderno, Inteligencia “especifica vs. “general’‘.

      - Se identifica la necesidad de trabajar en sociedad con profesionales de otras áreas de conocimiento
      - Representación explícita del conocimiento específico del dominio.
      - Sistema experto médico MYCIN (experto en enfermedades infecciosas de la sangre) iniciado en la Universidad de Stanford
      - Sistemas expertos o basados en conocimiento.
      - Regreso de redes neuronales [Hopfield, Rumelhart, Hinton], algoritmos genéticos [Holland, Goldberg]
      - Reconocimiento de voz (HMM), incertidumbre (RB, Lógica difusa), planeación, aprendizaje
      - Aplicaciones “reales’‘ (medicina, finanzas, ingeniería, exploración, etc.).
      - Comercialización de la IA

1.2. Técnicas de resolución de problemas de IA

Uno de los resultados que surgieron de las primeras investigaciones en IA fue que la inteligencia necesita conocimiento. El conocimiento posee algunas propiedades poco deseables como: 

    * Es voluminoso
    * Es difícil caracterizarlo
    * Cambia
    * Se organiza de manera que se corresponde con la forma en que va a se usado

Una técnica de IA es un método que explota el conocimiento representado de manera que se cumpla que: 

    * Representa generalizaciones, es decir, no es necesario representar cada situación individual, sino que las situaciones 
      que comparten propiedades importantes se agrupan.
    * Debe ser entendido por las personas que lo provean.
    * Puede ser modificado para corregir errores y reflejar cambios en el mundo
    * Puede usarse en muchas situaciones aun sin ser totalmente exacto o completo
    * Puede usarse para superar su propio volumen, y disminuir el rango de posibilidades que normalmente deben considerarse

Se pueden caracterizar las técnicas de IA con independencia del problema a tratar.

Para solucionar problemas complicados, los programas que utilizan las técnicas de IA presentan numerosas ventajas con respecto a los que no lo hacen: 

    * son menos frágiles, es decir, que no se despistan frente a una perturbación pequeña de la entrada
    * el conocimiento del programa es comprendido fácilmente por la gente
    * usa generalizaciones
    * tiene facilidad de extensión

Como contraposición, generalmente tienen más complejidad que otras soluciones.

Se analizan brevemente a continuación dos tipos de problemas bien diferenciados, y dentro de cada uno se ejemplifica lo que se entiende por una técnica de IA.

Ejemplo 1: tres en raya

A continuación se plantean tres soluciones diferentes del problema de tres en raya analizando la conveniencia de cada una. Para mejor detalle de las mismas consultar [Rich98]. 

    * Solución 1:

      Una primera solución directa a este juego podría ser la de almacenar en un vector las 19.693 (39) posibilidades de un

tablero de 3 x 3 con tres valores posibles en cada casilla (vacío-X-O), así como las correspondientes jugadas sucesoras. Para realizar una jugada, bastaría con acceder a la posición del tablero actual y la jugada sucesora correspondiente. Las desventajas de este eficiente programa son bastante obvias: necesita gran cantidad de memoria; alguien debe realizar el pesado trabajo de introducir todas las jugadas y sus sucesoras; y el juego no se puede ampliar, por ejemplo a tres dimensiones. 

    * Solución 2:

      El programa posee una estrategia para cada turno de jugador. Analiza el posible triunfo a partir de un estado del tablero

dado. Aunque es menos eficiente que la solución anterior en términos de tiempo, tiene la ventaja que es más eficiente en términos de espacio. Su estrategia es más facil de comprender y realizar cambios, aunque el programador debe comprender la totalidad de la estrategia de antemano. Además, no es posible generalizar parte del conocimiento del programa hacia un dominio distinto, como tres en raya 3D. 

    * Solución 3:

      Una estructura contiene el tablero actual, así como una lista de posiciones del tablero que podrían ser el próximo

movimiento, y una estimación de la probabilidad de que esa jugada lleve a la victoria. Para decidir la siguiente jugada se tienen en cuenta las posiciones de tablero que resultan de cada movimiento posible. Se decide la posición que corresponde a la mejor jugada, considerando si la jugada produce la victoria, y en caso contrario considerando todos los movimientos que el oponente puede realizar asumiendo que éste elegirá el peor para nosotros. El algoritmo 

 inspecciona varias secuencias de movimientos intentando maximizar la probabilidad de victoria. Necesita mucho más

tiempo que los demás, ya que debe realizar una búsqueda en un árbol de posibilidades antes de realizar cada movimiento. Sin embargo, es superior a las demás soluciones pues podría ser ampliado para manipular juegos más complicados. Además, puede aumentarse su potencia usando conocimiento sobre el juego, por ejemplo, en lugar de considerar todos los posibles 

 movimientos considerar solo un subconjunto siguiendo algún criterio razonable. Este programa es un ejemplo del uso de
 una técnica de IA.

Ejemplo 2: respuestas a preguntas

Se quiere realizar un programa que a partir de un texto escrito en español pueda responder a preguntas en español sobre este texto. En este caso, es más difícil que en el ejemplo anterior determinar formalmente y con precisión en qué consiste el problema y en qué consiste una solución correcta para él. Un ejemplo de programa de preguntas y respuestas en inglés es el programa POLITICS (Carbonell, 1980).

A continuación se plantean tres soluciones diferentes analizando la conveniencia de cada una. Para mejor detalle de las mismas consultar [Rich98]. 

    * Solución 1:

      Se tienen conjunto de plantillas (templates) preguntas, por ejemplo “Que x y” asociada con patrones (patterns) respuesta, por

ejemplo “y x z”. Responde a las preguntas usando el texto de entrada de forma literal. Se hace coincidir fragmentos de texto de entrada con el patrón respuesta, y se obtiene la respuesta, por ejemplo “z”. Este algoritmo no puede contestar el tipo de preguntas que la gente puede responder después de una simple lectura del texto. La habilidad para responder depende de la forma exacta de la pregunta, y de las variaciones contempladas en el diseño de plantillas y patrones. El proceso de sustitución de patrones usado es llamado pattern matching. Pese a que lo que se entiende por IA no incluye programas como éste, ésta técnica es la usada en uno de los programas más célebres de IA, ELIZA. 

    * Solución 2:

      Transforma el texto de entrada dándole una estructura interna que intenta capturar el significado de las frases, y también

transforma las preguntas de igual manera. Las respuestas se encuentran emparejando unas con otras formas estructuradas. Este enfoque está más basado en conocimiento que el primero, y también es más efectivo. Puede responder a la mayoría de las preguntas cuyas respuestas se encuentran en el texto, y es menos quebradizo con respecto a las formulaciones exactas 

 de preguntas y respuestas. Algunas preguntas necesitan conocimiento adicional sobre el mundo con el que trate el texto,
 que esta solución no posee.

    * Solución 3:

      Al igual que la solución anterior se transforma el texto en forma estructurada, pero a diferencia del anterior,

se combina esta forma con otras formas estructuradas que describen conocimiento previo sobre los objetos y situaciones que aparecen en el texto. Este programa es más potente que los otros dos, debido a que responde a preguntas usando esta estructura de conocimiento aumentada. Se utiliza lo que se denomina técnica de IA, pues está basado en el conocimiento y en uso computacional eficaz de ese conocimiento.

Estos ejemplos ponen de manifiesto tres importantes técnicas de IA: 

    * Búsqueda: proporciona una forma de resolver problemas en los que no se dispone de un método directo
    * Uso del conocimiento: proporciona una forma de resolver problemas complejos explotando las estructuras existentes

entre los objetos involucrados 

    * Abstracción: proporciona una forma de separar aspectos y variaciones importantes de aquellos otros sin importancia,

y que en caso contrario podrían colapsar el proceso.

1.3. Criterios de éxito de la IA

Para determinar el éxito de un programa de IA, se deben realizar las siguientes preguntas: 

    * ¿Está definida con claridad la tarea?
    * ¿Existe un proceso instrumentado que efectúa la tarea?
    * ¿Existe un conjunto de restricciones identificables a partir de las cuales el procedimiento implantado tiene poder?
    * ¿Resuelve un problema real?
    * ¿Crea una nueva oportunidad?

Test de Turing

En 1950, Alan Turing propuso el siguiente método para determinar si una máquina es capaz de pensar. Una persona es un entrevistador y se halla en una habitación separado de otra persona y un ordenador a evaluar. El entrevistador hace preguntas a ambos de forma escrita. Si luego de un cierto número de preguntas y respuestas, el interrogador no puede identificar quién es el computador y quién es la persona, entonces podemos decir que el computador piensa.

¿Se puede calibrar el éxito de la IA en dominios más restringidos? Por ejemplo, 

      - el éxito de un programa que juega al ajedrez se puede evaluar según los jugadores que pueda derrotar;
      - el éxito de otros programas puede medirse comparando el tiempo que tarda un ordenador en llevar a cabo una tarea con el

que tarda una persona en hacer lo mismo. Por ej. programas usados en empresas informáticas para configurar sistemas particulares a las necesidades del cliente; 

      - en tareas de cada día es más difícil, por ej. parafrasear un artículo del periódico, la mejor forma de evaluarlo es ver

si el programa responde de la misma forma que haría una persona.

Cuando se quiere diseñar un programa de IA, se debe intentar especificar tan bien como sea posible el criterio de éxito para el funcionamiento del programa en su dominio particular.

1.4. Resolución de problemas de IA

Para construir un sistema que resuelva un sistema específico, es necesario:

1- Definir el problema formalmente con precisión. 2- Analizar el problema. 3- Representar el conocimiento necesario para resolver el problema. 4- Elegir la mejor técnica que resuelva el problema y aplicarla.

‘’‘ 1.4.1. Definición formal del problema’‘’

El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.

Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc. ). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.

Para producir una especificación formal de un problema se deben definir: 

    * espacio de estados válidos;
    * estado inicial del problema;
    * estado objetivo o final;
    * reglas que se pueden aplicar para pasar de un estado a otro.

Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los estado válidos, sino que es posible definirlo de manera más general.

El estado inicial consiste en uno o varios estados en los que puede comenzar el problema. El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.

Las reglas describen las acciones u operadores que posibilitan un pasaje de estados. Una regla tiene una parte izquierda y una parte derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como obtener el estado sucesor.

Por ejemplo, en el problema de jugar al ajedrez: 

      - el espacio de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;
      - el estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo de acuerdo a las piezas situadas;
      - el objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento

legal y su rey esté amenzado; 

      - las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual
 de tablero y otra parte que describe el cambio que debe producirse en el tablero.

Dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones de tablero), las reglas deben escribirse de la manera más general posible.

La representación como espacio de estados forma parte de la mayoría de los métodos de IA. Su estructura se corresponde con la resolución de problemas porque: 

    * permite definir formalmente el problema, mediante la necesidad de convertir una situación dada en una situación deseada mediante un

conjunto de operaciones permitidas; 

    * permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general

de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).

Ejercicio 1: Problema de las jarras de agua

Se tienen dos jarras de agua, una de 4l y otra de 3l sin escala de medición. Se desea tener 2l de agua en la jarra de 4l. Las siguientes operaciones son válidas: llenar las jarras, tirar agua de las jarras, pasar agua de una jarra a otra.

Solución: 

    * El espacio de estados se define como

{ (X,Y)/ X son los litros en la jarra de 4l con 0<=X<=4 AND Y son los litros de la jarra de 3l con 0<=Y<=3 } 

    * El estado inicial es (0,0)

    * El estado final es (2,0). El estado final podría ser (2,N) en caso de que no importen los litros de la segunda jarra.

    * Las reglas que se pueden aplicar son:

1. Llenar la jarra de 4l: Si (X,Y) AND X<4 => (4,Y)

2. Llenar la jarra de 3l: Si (X,Y) AND Y<3 => (X,3)

3. Vaciar la jarra de 4l: Si (X,Y) AND X>0 => (0, Y)

4. Vaciar la jarra de 3l: Si (X,Y) AND Y>0 => (X, 0)

5. Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla: Si (X,Y) AND X>0 AND X+Y>=3 => (X-(3-Y),3)

6. Pasar agua de la jarra de 3l a la jarra de 4l hasta llenarla: Si (X,Y) AND Y>0 AND X+Y>=4 => (4, Y-(4-X))

7. Pasar toda el agua de la jarra de 4l a la jarra de 3l: Si (X,Y) AND X>0 AND X+Y<3 => (0,X+Y)

8. Pasar toda el agua de la jarra de 3l a la jarra de 4l: Si (X,Y) AND Y>0 AND X+Y<4 => (X+Y,0)

El programa debería encontrar un pasaje de estados para ir del estado (0,0) al estado (2,0). Puede existir más de un pasaje de estados hacia la solución, por ejemplo:

(0,0) => (0,3) => (3,0) => (3,3) => (4,2) => (0,2) => (2,0)

en la cual, a partir del estado inicial, se aplicaron las reglas 2, 8, 2, 6, 3 y 8, hasta conseguir el estado objetivo.

Otro pasaje de estados hacia la solución es la siguiente

(0,0) => (4,0) => (1,3) => (1,0) => (0,1) => (4,1) => (2,3) => (2,0)

en la cual se aplicaron las reglas 1, 5, 4, 7, 1, 5 y 4

Con respecto a las reglas se puede concluir que: 

    * Las condiciones que se establecen en la parte izquierda a veces no son altamente necesarias pero restringen la aplicación de la

regla a estados más adecuados. Esto incrementa la eficiencia del programa que utiliza las reglas. En el ejemplo anterior, la regla 

      1. Llenar la jarra de 4l: Si (X,Y) AND X<4  => (4,Y)
      contiene la condición (X<4), especificando que la jarra no se encuentra llena. Si esta condición no se incluye, se puede aplicar la

regla aún cuando la jarra está llena. Dado que en este caso el estado del problema no cambia la aplicación de la regla se considera inútil 

    *   Las reglas no sólo deben describir el problema sino también algún tipo de conocimiento sobre su solución. Si en el ejemplo anterior

se considera la siguiente nueva regla: 

      Vaciar “un poco” la jarra de 4l: Si (X,Y) AND X>0  => (X-Q, Y)
      es decir, tirar agua sin cuantificar, intuitivamente se concluye que la aplicación de esta regla nunca nos acercará a la solución

del problema. 

    *   A veces, cuando se alcanzan algunos estados resulta obvio cómo se debe continuar hacia la solución. Es posible agregar reglas de

propósito especial que capturen el conocimiento sobre casos especiales que conducen a la resolución del problema. En el ejemplo anterior, se pueden agregar las siguientes reglas de propósito especial: 

      Si (X,2) => (2,0)
      Si (2,Y) AND Y>0 => (2,0)
      Estas reglas no añaden más potencia al sistema ya que las operaciones que describen las proporcionan otras reglas más generales.

En el ejemplo, la primera regla agregada es equivalente a la aplicación de las reglas generales 3 y 8; y la segunda regla agregada es equivalente a la aplicación de la regla general 4. Dependiendo de la estrategia de control que se utilice para seleccionar reglas durante la resolución del problema se puede mejorar el rendimiento si se les da preferencia a las reglas de casos especiales.

Ejercicio 2: Problema de los Caníbales y Monjes 

 ‘’‘

1.4.2. Estrategia de control: Métodos de búsqueda’‘’

El problema puede resolverse con el uso de reglas en combinación con una estrategia de control para trasladarse a través del espacio de estados hasta encontrar un camino desde el estado inicial hasta el estado final. Se elige una regla entre aquellas cuya parte izquierda concuerda con el estado actual. Se aplica la regla elegida realizando el cambio de estado tal como se describe en la parte derecha de la regla. Si el nuevo estado es estado objetivo o final se ha encontrado la solución. En caso contrario se continúa con la aplicación de reglas al nuevo estado.

Una estrategia de control especifica el orden en el que se deben aplicar las reglas, así como también la forma de resolver conflictos cuando es posible aplicar más de una regla. Para que una estrategia de control sea válida debe cumplir con dos requisitos: 

    * Causar cambios:

    * las estrategias de control que no causan cambios de estado nunca alcanzan la solución. Un ejemplo de estrategia de control que no

causa cambios es seleccionar siempre la primera regla aplicable de la lista de reglas definidas. En el ejemplo de las jarras de agua, se continuaría indefinidamente aplicando las reglas 1 y 3 sin posibilidad de arribar a la solución. Ser sistemática: 

      las estrategias de control que no son sistemáticas pueden utilizar secuencias de operaciones no apropiadas varias veces hasta

alcanzar la solución. Un ejemplo de estrategia de control no sistemática es seleccionar la regla a aplicar al azar. Esta estrategia puede encontrar la solución eventualmente, pero luego de haber realizado varios pasos innecesarios e incluso haber vuelto varias veces al mismo estado.

En caso de no contar con una aproximación directa al problema, el proceso de búsqueda resulta fundamental en la resolución del mismo. Los algoritmos de búsqueda detallados a continuación son ejemplos de estrategias de control sistemáticas. Todos se basan en considerar un árbol de estados cuya raíz es el estado inicial, y en cada nivel se hallan los estados sucesores correspondientes. 

    * Búsqueda Breadth-First Search (primero en ancho)

Este algoritmo de búsqueda visita cada nodo del árbol por niveles, es decir, visita todos los nodos de un nivel antes de visitar los del siguiente. A continuación se detalla un pseudo-código de este algoritmo:

Lista_nodos = [estado_inicial]; Mientras Not Vacia(lista_nodos) 

      estado_actual = lista_nodos.primero;
      Si Estado Final?(estado_actual) entonces
            Terminar; Sino
            lista_reglas = Reglas Aplicables? (estado_actual);
            Mientras NOT Vacia(lista_reglas)
                  estado_sucesor = Aplicar Regla? (lista_reglas);
                  lista_nodos = lista_nodos + [estado_sucesor]; Fin Mientras; Fin Sino;

Fin Mientras;

Este algoritmo básico debería modificarse para detectar el caso en que se vuelva a alcanzar un estado que ya ha sido visitado con anterioridad. En este caso, debería realizarse una “poda” de la rama del árbol, ya que en caso contrario se volvería a generar un subárbol ya generado.

Con la búsqueda a lo ancho se asegura que una vez alcanzada una solución no existe otra ruta hacia la solución que tenga menor cantidad de pasos. Una desventaja de este algoritmo es que para alcanzar una solución de n pasos, debe haber explorado todo el espacio de estados hasta ese nivel.

Ejercicio: Realizar el árbol de búsqueda a lo ancho para encontrar la solución del problema de las jarras de agua. 

    * Búsqueda Depth-First Search (primero en profundidad)

Este algoritmo de búsqueda continúa por una rama del árbol hasta encontrar la solución o decidir terminar la búsqueda por esa dirección (por llegar al estado final, por tener un largo de ruta que supera una cota máxima determina, por haber llega a un estado ya visitado, etc.). 

 Al fracasar una ruta, se realiza un backtracking o vuelta atrás, continuando la exploración en el paso inmediatamente anterior.

A continuación se detalla un pseudo-código de este algoritmo recursivo que incialmente es llamado con el estado_inicial:

Función Buscar (estado_actual) devuelve Boolean Comienzo 

      Si Estado Final(estado_actual) entonces
            Devolver TRUE; Sino
            exito = FALSE;
            lista_reglas = Reglas Aplicables (estado_actual);
            Mientras NOT exito AND NOT Vacia(lista_reglas)
                  estado_sucesor = Aplicar Regla (lista_reglas);
                  exito = Buscar (estado_sucesor); Fin Mientras;
            Devolver exito; Fin Sino;

Fin Buscar;

Este algoritmo básico debería modificarse para terminar la búsqueda en una rama que se alcanza un estado que ya visitado.

Con la búsqueda en profundidad no es necesario tener almacenado todo el espacio de estados, sino sólo el camino que se está explorando. Puede encontrar la solución sin tener que explorar gran parte del espacio de estados. Como desventajas de este algoritmo se señala que puede seguir una ruta infructuosa durante muchos pasos, y además la primera solución que encuentra puede distar mucho de ser la solución de mínima cantidad de pasos. 

    * Búsqueda Heurística

Existen algunos problemas en los que resulta imposible explorar el árbol del espacio de estados pues resulta en una explosión combinatoria. 

 Por ej. en el problema del viajante, se debe encontrar la ruta mínima entre N ciudades a visitar. Si se aplica cualquiera de los dos
 algoritmos de búsqueda anteriores, nos encontramos ante un costo computacional no polinomial O(N!).

Una heurística es una técnica que aumenta la eficiencia de un proceso de búsqueda. El objetivo es guiar al proceso de búsqueda en la dirección más provechosa sugiriendo el camino a seguir cuando hay más de una opción.

Las heurísticas pueden ser: 

    * generales: son adecuadas para una amplia variedad de dominios. Por ej. la heurística del vecino más próximo (nearest neighbor)

se aplica a muchos problemas combinatorios. En el ejemplo del problema del viajante, se comienza por una ciudad arbitraria continuando en cada paso por la ciudad más cercana no visitada. Esto resulta en una reducción del costo computacional a O(N2). 

    * de propósito especial: explotan el conocimiento específico de un dominio para resolver problemas particulares.

Las heurísticas pueden sacrificar la completitud, es decir, pueden pasar por alto una buena solución. Sin embargo, existen varios argumentos a favor de usarlas: 

    * Sin el uso de heurísticas se puede tener una explosión combinatoria.
    * En muchos casos no se necesita la solución óptima sino una buena aproximación. Según Simon (1981), las personas resuelven

problemas “satisfaciendo” y no “optimizando”. 

    * Las aproximaciones que se logran con heurísticas pueden ser malas para los peores casos de un problema, pero éstos raramente

sedan en el mundo real. 

    * El esfuerzo de intentar comprender por qué funciona o no una heurística sirve para profundizar en la comprensión del problema.

Las heurísticas se pueden incorporar a un proceso de búsqueda basado en reglas de dos maneras: 

    * Dentro de las mismas reglas. Por ej. en el ajedrez, las reglas pueden describir, además de los movimientos legales, también las

buenas jugadas. 

    * Como una función que evalúa estados determinando su grado de “deseable”. Esta función evalúa aspectos del problema dando pesos a

aspectos individuales, de manera que el valor que devuelve es una estimación de que el nodo pertenece a la ruta que conduce a la mejor solución. Por ej. en el ajedrez se puede tener una función a maximizar la cual devuelve el número de piezas de ventaja; en el problema del viajante se puede tener una función a minimizar la cual devuelve la suma de distancias recorridas; en el tres en raya se puede tener una función que compute un punto por cada ficha en cada fila, columna o diagonal que se pueda ganar.

En conclusión, las heurísticas representan el conocimiento general y específico del mundo, que hace que sea abordable solucionar problemas complejos.

‘’‘ 1.4.3. Análisis del problema’‘’

Luego de definir el problema formalmente, el segundo paso en la resolución del problema es el análisis del mismo. A fin de poder elegir el método más apropiado para resolver un problema particular, es necesario analizar distintas cuestiones que afectan a al definición del mismo y a las características de la solución deseada. Existen varias preguntas a responder acerca del problema:

1. ¿Puede descomponerse el problema en subproblemas más pequeños? 2. ¿Pueden deshacerse pasos inadecuados hacia la solución? 3. ¿Es predecible el universo del problema? 4. ¿Una solución es buena de manera absoluta o relativa? 5. ¿La solución deseada es un estado o la ruta hacia un estado? 6. ¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución? 7. El programa que soluciona el problema ¿busca la solución solo o necesita interactuar con una persona?

1. ¿Puede descomponerse el problema en subproblemas más pequeños?

Algunos problemas pueden descomponerse en subproblemas independientes, de manera que encontrar una solución global es la composición de soluciones particulares. Por ej. en la resolución de integrales, una integral puede descomponerse por partes, y resolver las partes simples directamente o descomponerlas recursivamente.

Por otra partes, existen otros problemas que no pueden descomponerse y componer la solución a partir de las soluciones parciales de sus partes. Por el contrario, una solución necesita considerar globalmente el problema. Por ej. el problema del mundo de los bloques.

2. ¿Pueden deshacerse pasos inadecuados hacia la solución?

Algunos problemas permiten deshacer uno o varios pasos hacia una solución una vez realizados. En este aspecto, existen tres categorías en las que puede dividirse un problema: 

    * Recuperables:

    * en un punto dado es posible deshacer todos los pasos inadecuados hacia la solución. Por ej. en el juego 8-puzzle. La estructura

de control se implementa con una pila push-down en la que se almacenan las decisiones para poder volver atrás. No recuperables: 

    * en un punto dado no es posible deshacer ningún paso realizado. Por ej. en una partida de ajedrez no se puede volver atrás una vez

movidas las piezas. En estos problemas el sistema debe esforzarse en la toma de decisiones pues éstas son irrevocables. Algunos usan una 

 planificación en la que se analiza por adelantado una secuencia de pasos antes de realizar el primer paso para descubrir a donde conduce. Ignorables:

      en un punto dado es posible ignorar los pasos realizados hasta el momento y comenzar de nuevo con una nueva solución. Por ej. un

demostrador de teoremas puede abandonar una demostración basada en un lema dado y comenzar nuevamente. Estos problemas se resuelven con estrategias de control sencillas que nunca vuelven hacia atrás.

‘’‘ 3. ¿Es predecible el universo del problema?’‘’

Los problemas pueden se de: 

    * Consecuencia cierta:

    * es posible planificar una secuencia de movimientos estando seguros del resultado a obtener. Se puede realizar una planificación

para generar operadores que garanticen llegar a la solución. Consecuencia incierta: 

      no es posible planificar con certeza pues no se sabe que ocurrirá luego del siguiente movimiento. Sin embargo, se puede realizar

una planificación para generar operadores que tengan una buena probabilidad de llegar a la solución.

Los problemas más difíciles de resolver son los no recuperables de consecuencia incierta. Por ej. el control del brazo de un robot: es de consecuencia incierta pues alguien puede interponer un objeto en la ruta del brazo, se puede atascar, etc.

4. ¿Una solución es buena de manera absoluta o relativa?

La solución de un problema puede consistir en encontrar: 

    * Algún camino:

    * sólo importa encontrar una solución sin importar si existen otros caminos que conducen a la solución. Generalmente se resuelven

con heurísticas. Por ej. programa de respuestas a preguntas. El mejor camino: 

      importa encontrar la ruta más corta hacia la solución. Son problemas más complicados de computar. Algunos requieren una búsqueda

más exhaustiva que usando heurísticas. Por ej. en el problema del viajante importa encontrar la ruta más corta entre las ciudades a visitar.

5. ¿La solución deseada es un estado o la ruta hacia un estado?

La solución de un problema puede consistir en encontrar: 

    * un estado final:

    * no es necesario el registro del proceso seguido, sólo importa arribar a la solución final. Por ej. interpretar texto. una ruta

hacia un estado final: 

      se necesita dar el camino seguido desde el estado inicial al estado final. Por ej. problema de las jarras de agua.

6. ¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución?

El conocimiento puede emplearse para: 

    * Reconocer la solución:

    * se necesita gran cantidad de conocimiento acerca del problema para poder encontrar una solución. Por ej. comprensión de texto.

Acotar la búsqueda: 

      la solución básica puede encontrarse con poco conocimiento, pero para restringir el árbol de búsqueda y encontrar la solución de

manera más eficiente es necesario contar más conocimiento. Por ej. en el ajedrez se necesita básicamente poco conocimiento para conocer los movimientos legales y un mecanismo sencillo de búsqueda. Pero dado que para aumentar la eficiencia de la búsqueda ésta debe restringirse, se necesita conocimiento de heurísticas de buenas estrategias y tácticas para jugar.

7. El programa que soluciona el problema ¿busca la solución solo o necesita interactuar con una persona?

Con respecto a la relación programa-usuario, existen dos tipos de programas que solucionan el problema: 

    * Solitarios:

    * reciben como entrada el problema y dan como salida la solución. No importa el razonamiento que haya seguido la máquina para

encontrar la solución. Por ej. problema de las jarras de agua. Conversacionales: 

      existe una comunicación hombre-máquina de manera que el usuario puede ayudar a la máquina o la máquina puede informar al usuario

durante la búsqueda de la solución. Para que esta comunicación sea posible debe existir una correspondencia entre el razonamiento 

 seguido por la máquina y la forma de razonamiento humano. Por ej. en un sistema experto de diagnóstico médico, el usuario no

aceptaría el veredicto de una máquina si no puede comprender el razonamiento que la llevó a él.

Ejercicio: Torres de Hanoi

Definir formalmente y analizar los 7 puntos anteriores en el siguiente problema:

Se hallan N discos de distinto tamaño apilados sobre una base A de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías B y C. El objetivo es llevar todos los discos de la base A hasta la base C, para lo cual puede usarse la base B. Considerar que se puede mover sólo un disco a la vez, y cada disco puede descansar solamente en las bases y no en el suelo. Recordar que los discos deben situarse siempre sobre uno de mayor radio.

Competencias Digitales (Tic’s Basicas) a practicar con este TEMA:

  • Usar (click en )www.Google.com para buscar y localizar UN material academico apropiado y que se pueda

recomendar para el tema, ver VIDEO BUSQUEDAS abajo en esta pagina.

  • En el post ( o tema ) apropiado en el Libro de Blogger, pegar el material localizado y que se recomienda

para este tema, ver VIDEO BLOGGER abajo en esta pagina.

pd: Recordar incluir la fuente del tema usando el formato de citacion apropiado, ver VIDEO WIKIPEDIA abajo en esta pagina.

  • En el editor de Blogger usar colores para destacar los parrafos mas importantes y usar subrayados para las citas 
 mas relevantes.
  • En el post ( o tema ) apropiado en el libro en Blogger, para incluir ecuaciones o notacion matematica se

debera usar el icono del editor de Blogger IMAGE y construir esta notacion matematica con imagenes Latex, ver VIDEO LATEX ABAJO.

  • Construir al final y despues de la fuente del material, un breve resumen ( no mas de 2–3 parrafos) explicando

palabras propias el contenido del tema.

pd: Se pueden usar alguna de las citas que encontradas dentro del tema, solo recordar encerrarla entre comillas.

pd: Se pueden usar tambien cambios en fonts para darle mas visibilidad, consistencia y relevancia al resumen del tema.

  • PUNTOS EXTRAS Si se usa una segunda fuente valiosa de informacion y recordar encadenar los dos materiales

mediante uno o dos parrafos apropiados.

  • Enviar a el maestro o compañeros un correo electronico que incluya la liga a el tema en blogger para revision,

recomendacion, sugerencias y evaluacion, ver VIDEO LIGAS GMAIL abajo.

usuario que se construyo en Gmail y Blogger ver VIDEO GOOGLE DOCS abajo en esta pagina.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

pd: Google Docs es el equivalente a OFFICE pero con la caracteristica que todos sus componentes ( procesador de palabras, presentacion electronica y hoja de calculo) estan completamente en internet, es decir todos los archivos o material estaran en linea, seguros y siempre disponibles, ademas de que se pueden trabajarlos desde cualquier pc, ya sea la personal, la del laboratorio de la escuela o la de un lugar publico como la biblioteca o un cafe internet.

  • Construir una Presentacion Electronica ( usando muy pocos slides) del tema en GOOGLE DOCS e ‘’‘incrustrarla en el

tema de bloger’‘’ ver VIDEO GOOGLE DOCS en esta pagina abajo.

pd: Recordar que una presentacion electronica, es solamente un resumen muy condensado del tema ( o mapa o guia mental ), que ayuda a recordar los elementos y conceptos mas basicos del tema, cuando se estan exponiendo frente a un grupo.

pd: No olvidar incluir un primer slide con el titulo de la presentacion electronica, un segundo slide con un indice de la presentacion electronica y un ultimo slide con dos o tres parrafos de conclusiones y bibliografia.

apropiadas al tema actual,

  • Para los casos de Photobucket y Flicker, ambos sitios proporcionan ligas a sus imagenes y tambien objetos (los recuerdan??),

que se pueden incluir en el tema del libro apropiado en Blogger.

pd: para estos sitios deberan obtener una cuenta usando el correo de gmail y de preferencia obtener el mismo usario que se ha venido manejando a lo largo del curso.

pd: Tratar de usar resoluciones y tamaños de imagenes chicos o medianos, recordar que todo este material termina en el post del tema 

 en Blogger y esa pagina no tiene mucho espacio para desplegar fotos o imagenes.

pd: El formato apropiado para fotos o imagenes es JPG, tratar de no usar otros formatos.

pd: Se puede construir y conseguir esta coleccion o galeria de imagenes con:

1) Usando Google Imagenes, recordar conseguir solo imagenes que tengan permiso de publicacion abierto, no usar imagenes o fotos que tengan derechos reservados.

pd: Estas fotos almacenarlas en un folder en el desktop o escritorio de su computadora y subirlas a el post en blogger usando el icono IMAGE del editor de Blogger.

2) Flickr y Photo Bucket tambien tienen una gran cantidad de imagenes que se pueden usar o mejor dicho enlazar a el tema o post en Blogger.

3) Tambien se puede usar la camaras digitales o las camaras de sus telefonos celulares.

4) Tambien se puede usar el programa o aplicacion llamado Srip32.exe( solo buscar srip32 en google) bajarlo e instalarlo, este programa 

 permite capturar una pantalla de la pc, es decir si se encuentra un sitio con imagenes o incluso texto apropiado o relevante al tema,

capturar la pantalla con srip32 y ya se tendra la imagen, ver VIDEO Srip32 abajo.

  • Incluir al menos una imagen de cada uno de los dos sitios (flickr y Photobucket) en el tema o post que se esta

construyendo en Blogger.

  • PUNTOS EXTRAS Si se incluyen una galeria completa de imagenes apropiadas desde cualquiera de estos sitios de FLICKR

o Photobucket.

  • Sacar una cuenta (click en)www.DivShare.com, usando el correo de Gmail y tratar de conseguir el mismo usuario

que se consiguio en Gmail y Blogger y Flickr ver VIDEO DIVSHARE abajo en esta pagina.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

pd: Usar Divshare para almacenar material en audio (MP3) apropiado a el tema ( no usarlo para almacenar material comercial o les suspenden la cuenta)

pd: El material en Audio, con formato MP3 se debera producir usando un microfono en la pc y programas de aplicacion apropiados, llamados editores de audio, un ejemplo de ellos es el SOUND RECORDER que ya viene en Windows, pero se recomienda usar mejor AUDACITY ( solo buscar en google AUDACITY) bajarlo e instalarlo, ver VIDEO AUDACITY abajo.

  • Crear al menos dos archivos de audio mp3:

1) El primero de ellos sera la lectura completa de este tema en voz apropiada. ( o aprender a editar con audacity la voz)

2) El segundo de ellos sera un resumen del tema. ( buena voz o editarla con audacity)

3) Ambos archivos subirlos a Div Share (recordor que tienen que ser MP3) y el reproductor que proporciona gratis Div Share, ver VIDEO DIVSHARE abajo e insertarlo en el lugar apropiado del tema que se esta construyendo en Blogger.

4) Ejemplo del reproductor incrustado en una pagina:

  • Sacar una cuenta (click en)www.YouTube.com, usando el correo de Gmail y tratar de conseguir el mismo

usuario que se consiguio en Gmail y Blogger y Flickr.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

  • Para producir video se pueden usar tres fuentes:

1) Localizar Videos apropiados en Youtube.

2) Usar nuestras camaras digitales o nuestros telefonos celulares para producir video.

3) Producir un video de la propia pantalla de la computadora ( muy similar a lo que se hizo con Srip32) pero usando un programa especializado en video, tal como CAMSTUDIO (click en www.CamStudio.org) bajar e instalar ( no olvidar bajar e instalar el CODEC que esta abajo en el mismo sitio.

3.1) para Usar Camstudio solo recordar que es muy similar a Srip32 Solo que el resultado final es un archivo de video AVI.

  • Producir un video de resumen del tema (usar camstudio con el fondo de la pagina con el tema e irlo comentando

en voz apropiada)

  • Producir un video en vivo con la exposicion del tema ( pueden usar la presentacion electronica de fondo o

cualquier otro material, pizarron, filminas, rotafolios, etc.)

  • Subir los videos a su cuenta en Youtube e incluirlos o ligarlos en la pagina en Blogger, tambien los pueden

subir directamente a BLOGGER ver VIDEO BLOGGER VIDEO abajo.

Saludos y suerte prof Lauro Soto, Ensenada, BC, Mexico.