miércoles, 6 de agosto de 2014

PRESENTACIÓN

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DE MANABÍ MANUEL FÉLIX LÓPEZ


CARRERA: INGENIERÍA INFORMÁTICA


SEMESTRE SÉPTIMO                             PERÍODO ABR-AGO/2014


INTELIGENCIA ARTIFICIAL


TEMA:

ESTRATEGIAS DE BÚSQUEDA NO INFORMADA:

BÚSQUEDA PRIMERO EN ANCHURA
BÚSQUEDA PRIMERO EN PROFUNDIDAD

AUTORA:
SÁNCHEZ MACÍAS CINTHIA MABEL

CATEDRÁTICO:
ING. HIRAIDA SANTANA


MISIÓN
Formación de profesionales íntegros que conjuguen ciencia, tecnología y valores en su accionar, comprometidos con la sociedad en el manejo adecuado de programas y herramientas computacionales de última generación.

VISIÓN
Ser referente en la formación de profesionales de prestigio en el desarrollo de aplicaciones informáticas y soluciones de hardware.


CALCETA, MAYO 2014


BÚSQUEDA LOCAL

Fecha de clases: jueves, 24 de julio de 2014

BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS Y BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS


INTRODUCCIÓN.
El objetivo de esta clase es entender como un agente inteligente hace una búsqueda en espacios continuos o búsqueda online por lo que esta búsqueda solo se basa en lo que está pasando en ese estado para tomar de nuevo otra acción.


BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS.
Un modo de evitar problemas continuos es discretizar la vecindad de cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud.
Los métodos locales de búsqueda sufren de máximos locales, crestas, y mesetas tanto en espacios de estados continuos como en espacios discretos. Se pueden utilizar el reinicio aleatorio y el temple simulado y son a menudo provechosos. Los espacios continuos dimensionalmente altos son, sin embargo, lugares grandes en los que es fácil perderse.
Un problema de optimización está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable. La dificultad de los problemas de optimización con restricciones depende de la naturaleza de las restricciones y la función objetivo. La categoría más conocida es la de los problemas de programación lineal en los cuales las restricciones deben ser desigualdades lineales formando una región convexa y la función objetiva es también lineal. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. También se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo (programación cuadrática, programación
cónica de segundo orden, etcetera).

AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS
Un agente de búsqueda en línea (online) funciona intercalando el cálculo y la acción: primero toma una acción, entonces observa el entorno y calcula la siguiente acción. La búsqueda online es una buena idea en dominios dinámicos o semidinamicos (dominios donde hay una penalización por holgazanear y por utilizar demasiado tiempo para calcular). La búsqueda online es una idea incluso mejor para dominios estocásticos. En general, una búsqueda offline debería presentar un plan de contingencia exponencialmente grande que considere todos los acontecimientos posibles, mientras que una búsqueda online necesita solo considerar lo que realmente pasa.
La búsqueda online es una idea necesaria para un problema de exploración, donde los estados y las acciones son desconocidos por el agente; un agente en este estado de ignorancia debe usar sus acciones como experimentos para determinar que hacer después, y a partir de ahí debe intercalar el cálculo y la acción.



CONCLUSIÓN.

Estas búsquedas solo consideran lo que realmente pasa en ese estado y después toman nuevas acciones ya que en otras búsquedas necesitan tener una visión general del problema para así poder realizar una acción.


Los agentes efectúan búsquedas para encontrar una solución, en este caso tiene la difícil tarea de realizar una búsqueda online; el agente se mueve en un entorno desconocido en la que hacer una exhausta observación  para luego pasar a realizar el respectivo calculo y en base a esto realizar una acción y en la mayoría de los casos se encuentra una solución óptima.

BIBLIOGRAFÍA
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.



DECISIONES ÓPTIMAS EN JUEGO


Fecha de clases: 15 de julio/2014


INTRODUCCIÓN

En los entornos multiagente (cooperativos o competitivos), cualquier agente tiene que considerar las acciones de otros agentes. La imprevisibilidad de estos otros agentes puede introducir muchas contingencias en el proceso de resolución de problemas. Los entornos competitivos, en los cuales los objetivos de los agentes están en conflicto, dan ocasión a problemas de búsqueda entre adversarios, a menudo conocidos como juegos.


JUEGOS.

La Teoría de Juegos estudia de manera formal y abstracta las decisiones óptimas que deben tomar diversos adversarios en conflicto, pudiendo definirse como el estudio de modelos matemáticos que describen el conflicto y la cooperación entre entes inteligentes que toman decisiones. Tales decisiones se consideran estratégicas, es decir, que los entes que participan en el juego actúan teniendo en cuanta las acciones que tomarían los demás.

La teoría de juegos es capaz de ofrecer cuestiones de interés para estudiantes de todas las ramas de las Ciencias Sociales y la Biología, así como técnicas para tomar decisiones prácticas.

Los juegos son interesantes porque son demasiado difíciles de resolver. El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35 y los juegos van a menudo a 50 movimientos por cada jugador:

Grafo de búsqueda: aproximadamente 1040 nodos distintos árbol de búsqueda: 35100 o 10154. Los juegos, como el mundo real, requieren la capacidad de tomar alguna decisión (la jugada) cuando es infactible calcular la decisión óptima.


DECISIONES ÓPTIMAS EN JUEGO.

Un juego puede definirse formalmente como una clase de problemas de búsqueda con los componentes siguientes:


El estado inicial
Una función sucesor, que devuelve una lista de pares (movimiento, estado)

Un test terminal, que determina cuándo termina el juego (por estructura o propiedades o función utilidad)


EL PROCEDIMIENTO MINIMAX.

Calcula la decisión minimax del estado actual.

Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor.

La recursión avanza hacia las hojas del árbol.

Los valores minimax retroceden por el árbol cuando la recursión se va deshaciendo.

Realiza una exploración primero en profundidad completa del árbol de juegos.

Si la profundidad máxima del árbol es m, y hay b movimientos legales en cada punto, entonces la complejidad:

En tiempo es O (bm);

En espacio es O (bm) si se generan todos los sucesores a la vez;

O (m) si se generan los sucesores uno por uno.
Juegos reales: los costos de tiempo son inaceptables, pero este algoritmo sirve como base para el primer análisis matemático y para algoritmos más prácticos. 

Las estrategias maximin y minimax conducen a los dos jugadores del juego a situaciones en las que ningún jugador tiene razón o incentivo alguno para cambiar su posición. Así mismo, se dice que un jugador posee una estrategia dominante si una estrategia particular es preferida a cualquier otra estrategia a disposición de él.


CONCLUSIÓN

Se han visto estrategias en las que un solo agente busca la solución a un problema. Existen otro tipo de problemas en los que dos agentes compiten por un mismo objetivo. Las búsquedas con adversarios son parte de la teoría matemática de juegos, y para la I.A. se centran en los de un tipo determinado.

Algunas teorías buscan encontrar las estrategias racionales, que se utilizan en situaciones donde el resultado depende no solamente de las estrategias propias y las condiciones del entorno, sino también en las estrategias utilizadas por otros jugadores con objetivos distintos.


BIBLIOGRAFÍAS

Ceccaroni, L. 2007. Inteligencia Artificial: Búsqueda entre adversarios.

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España.

Fernando Fernández Rodríguez. 2005. Teoría de juegos: análisis matemático de conflictos. Curso Interuniversitario “Sociedad, Ciencia, Tecnología y Matemáticas”



   

Lenguaje de Programación PROLOG


Fecha: 17 de julio/2014


INTRODUCCIÓN

El objetivo de esta clase es investigar sobre PROLOG para utilizarlo en ejercicios de Inteligencia Artificial. La resolución de ejercicios en este programa consiste en crear un archivo que contendrá información suficiente para que se tomen correctas decisiones y se arrojen respuestas correctas llamado “base del conocimiento” y otro que llevará las reglas, que validaran las solicitudes para dar las respuestas.



PROGRAMACIÓN LÓGICA

El lenguaje de programación PROLOG (“PROgrammation en LOGique”) fue creado por Alain Colmerauer y sus colaboradores alrededor de 1970 en la Universidad de Marseille-Aix.  Se pretendía usar la lógica formal como base para un lenguaje de programación, es decir, era un primer intento de diseñar un lenguaje de programación que posibilitara al programador especificar sus problemas en lógica. Lo que lo diferencia de los demás es el énfasis sobre la especificación del problema.

Es un lenguaje para el procesamiento de información simbólica. PROLOG es una realización aproximada del modelo de computación de Programación Lógica sobre una máquina secuencial. Desde luego, no es la única realización posible, pero sí es la mejor elección práctica, ya que equilibra por un lado la preservación de las propiedades del modelo abstracto de Programación Lógica y por el otro lado consigue que la implementación sea eficiente.


El lenguaje PROLOG juega un importante papel dentro de la Inteligencia Artificial, y se propuso como el lenguaje nativo de las máquinas de la quinta generación ("Fifth Generation Kernel Language", FGKL) que quería que fueran Sistemas de Procesamiento de Conocimiento. La expansión y el uso de este lenguaje propició la aparición de la normalización del lenguaje Prolog con la norma ISO (propuesta de junio de 1993).

PROLOG es un lenguaje de programación para ordenadores que se basa en el enguaje de la Lógica de Primer Orden y que se utiliza para resolver problemas en los que entran en juego objetos y relaciones entre ellos. Por ejemplo, cuando decimos "Jorge tiene una moto", estamos expresando una relación entre un objeto (Jorge) y otro objeto en particular (una moto). Más aún, estas relaciones tienen un orden específico (Jorge posee la moto y no al contrario). Por otra parte, cuando realizamos una pregunta (¿Tiene Jorge una moto?) lo que estamos haciendo es indagando acerca de una relación.

Además,  usar reglas para describir relaciones: "dos personas son hermanas si ambas son hembras y tienen los mismos padres".

Una de las ventajas de la programación lógica es que se especifica qué se tiene que hacer (programación declarativa), y no cómo se debe hacer (programación imperativa). A pesar de esto, Prolog incluye algunos predicados predefinidos metalógicos, ajenos al ámbito de la Lógica de Primer Orden, (var, nonvar, ==, ...), otros extra-lógicos, que tienen un efecto lateral, (write, get, ...) y un tercer grupo que nos sirven para expresar información de control de como realizar alguna tarea ( el corte, ... ). Por tanto, Prolog ofrece un sistema de programación práctico que tiene algunas de las ventajas de claridad y declaratividad que ofrecería un lenguaje de programación lógica y, al mismo tiempo, nos permite un cierto control y operatividad.

PROLOG es un lenguaje de programación muy útil para resolver problemas que implican objetos y relaciones entre objetos. Está basado en los siguientes mecanismos básicos:

ü  Unificación
ü  Estructuras de datos basadas en árboles
ü  Backtracking automático

La sintaxis del lenguaje consiste en lo siguiente:

ü  Declarar hechos sobre objetos y sus relaciones
ü  Hacer preguntas sobre objetos y sus relaciones
ü  Definir reglas sobre objetos y sus relaciones



Bibliografía:

Teresa Escrig; Julio Pacheco y Francisco Toledo. 2001. El Lenguaje de Programación PROLOG.

Faraón Llorens Largo y Mª Jesús Castel de Haro. 2001. LÓGICA DE PRIMER ORDEN, LÓGICA COMPUTACIONAL y AMPLIACIÓN DE LÓGICA.


PRÁCTICA EN PROLOG

Fecha de clases: 22 de julio/2014


INTRODUCCIÓN 


El propósito es realizar un ejercicio en PROLOG que identifique el parentesco que tienen los integrantes de una familia y quienes tienen posibilidad de procrear. Para esto debe construir un árbol genealógico:


(haga clic en la imagen para agrandarla)


Base del conocimiento:


hijo(angel,hector).
hijo(victoria,hector).
hijo(jose,hector).
hijo(feliciano,hector).
hijo(salvador,hector).
hijo(miguel,angel).
hijo(angelica,angel).
hijo(nathaly,victoria).
hijo(erik,jose).
hijo(cinthia,jose).
hijo(dora,jose).
hijo(wellintong,feliciano).
hijo(andres,feliciano).
hijo(hirene,feliciano).
hijo(liana,leyo).
hijo(marisol,leyo).
hijo(robin,leyo).
hijo(frecia,leyo).
hijo(alejandro,liana).
hijo(cristhiam,liana).
hijo(diana,marisol).
hijo(kerly,robin).
hijo(adriana,robin).
hijo(erik,frecia).
hijo(cinthia,frecia).
hijo(dora,frecia).
hombre(hector).
hombre(angel).
hombre(jose).
hombre(feliciano).
hombre(salvador).
hombre(leyo).
hombre(robin).
mujer(victoria).
mujer(liana).
mujer(marisol).
mujer(frecia).


Reglas:


hermano(X,Y):-hijo(X,Z),hijo(Y,Z).
primo(X,Y):-hijo(X,Z),hijo(Y,W),hermano(Z,W).
primopaterno(X,Y):-hijo(X,Z),hijo(Y,W),hermano(Z,W),(hombre(W)).
primomaterno(X,Y):-hijo(X,Z),hijo(Y,W),hermano(Z,W),(mujer(W)).
tio(X,Y):-hijo(Y,Z),hermano(Z,X).
puedeprocrear(X,Y):-not(hermano(X,Y)),not(hijo(X,Y)),not(hijo(Y,X)),not(primo(X,Y)),not(tio(X,Y)),not(tio(Y,X)),not((hombre(X),hombre(Y));(mujer(X),mujer(Y))).



Pruebas:

Para esto, dentro del mismo PROLOG hacemos clic en File/Consult y seleccionamos ambos archivos (Base del Conocimiento  y Reglas) una a la vez y escribimos:






Conclusión:

Todo depende de la correcta declaración de las reglas. El objetivo es que el programa sea eficaz en sus respuestas, para esto la base del conocimiento debe estar llena de datos específicos (esenciales); es decir, sólo los necesarios, y establecer buenas reglas para que esa base de conocimiento abastezca y genere las respuestas solicitadas. 

PAPER SOBRE LA LA MANO BIÓNICA


Fecha: 26 de julio / 2014



Introducción:


El presente trabajo se realizó con la finalidad de investigar los avances de la inteligencia artificial en los últimos años. Escogí este tema porque considero muy importante que se aplique en la salud humana y con el fin de mejorar el estilo de vida de personas que han sufrido alguna amputación.  

Haga clic en el siguiente vínculo para abrir el documento:

Prótesis superior con Control Mioeléctrico







miércoles, 4 de junio de 2014

ESTRATEGIAS DE BÚSQUEDA

Fecha de clase: 20/mayo/2014

INTRODUCCIÓN
Problemas en el mundo real existen (y muchos), así mismo existen soluciones para estos, pero no todas nos llevan a esta esperada solución con la misma eficiencia. Es por esto que se hace necesario conocer las técnicas de resolución, abstraer sus características más significativas para poder decidir cuál es la adecuada frente a cada problema.  
En este caso se desea dar solución a problemas de búsqueda en inteligencia artificial, para esto existen técnicas heurísticas (cuando se dispone de información) y técnicas a ciegas (o no informadas, cuando apenas se tiene la descripción del problema).
Los temas propuestos y la explicación de la docente se orientan a que el estudiante comprenda el funcionamiento básico de las técnicas de búsqueda para luego tener la capacidad de aplicarlos en problemas del mundo real, identificando el método de búsqueda adecuado para la resolución de problemas, dependiendo si se tiene o no información.  
MARCO TEÓRICO
Un problema de búsqueda en Inteligencia Artificial tiene algoritmos que trabajan con estructuras de datos llamadas nodos que contienen en particular información sobre un estado. Un problema de búsqueda consta de:

-          Un espacio de estados, que es el conjunto de estados factibles para un problema junto a la estructura de adyacencia definida implícitamente por los operadores o reglas. (Rubio et al. 1998)
-          Un conjunto de operadores (acciones, con costes). La finalidad de una secuencia de operadores es transformar el estado inicial en el estado objetivo.
-          Un estado inicial (punto de partida de la búsqueda).
-          Una función objetivo (comprueba si el estado actual corresponde a una solución del problema). La solución consiste en una secuencia de operadores que transforman el estado inicial en el estado objetivo. (Rubio et al. 1998)

La búsqueda la realiza un programa (o agente). El espacio de búsqueda será un grafo dirigido en el que cada nodo representa un posible estado del sistema. Dependiendo del problema, cada nodo incluirá una descripción completa del sistema, o bien sólo las modificaciones necesarias para pasar de un nodo padre a su hijo. (Berzal, F. s.f.)

Debido a que la búsqueda es el núcleo de muchos procesos inteligentes, es necesario escoger la estructura de control apropiada con el fin de que el proceso de búsqueda sea eficiente. La inteligencia artificial proporciona varias técnicas de búsqueda que tienen una formulación matemática, la cual hace posible su implementación computacional bajo el esquema de programación estructurada. (Molina et al. 2008)

Rubio et al (1998) indican las restricciones sobre las secuencias solución:

-          Encontrar la secuencia más corta.
-          Encontrar la secuencia menos costosa (en este caso se supondrá que los disparos de las reglas tienen asociado un coste o, equivalentemente, que el espacio de estados tiene pesos en las aristas).
-          Encontrar cualquier secuencia lo más rápido posible.

Al evaluar una estrategia habrá que tener en cuenta lo siguiente:

Tiempo de cálculo <==> Calidad de la solución.

Un punto muy importante que señalan estos autores es que todos los problemas de búsqueda requieren no sólo que se encuentre un camino solución, sino todos los que existan (probablemente para poder aplicar estrategias, por ejemplo en un juego de ajedrez).

Existen diversos métodos de realizar búsquedas, a continuación se muestran dos grandes grupos que son búsqueda informada o heurística y la búsqueda a ciegas o no informada.

HEURÍSTICAS
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. (Berzal, F. s.f.)

Es el tipo de estrategia que sabe si un estado no objetivo es más prometedor que otro, permitiendo reducir la búsqueda (Russell y Norvig. 2004); es decir, como disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, se pueden explorar en primer lugar los caminos más prometedores. (Rubio et al. 1998)

Según Rubio et al (1998), los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.

BÚSQUEDA NO INFORMADA O BÚSQUEDA A CIEGAS
Engloba las estrategias de búsqueda que no cuentan con información adicional sobre los estados, aparte de la definición del problema. Estas sólo pueden generar los sucesores y distinguir entre un estado objetivo de un estado no objetivo. Las estrategias que saben que un estado no objetivo es más prometedor que otros se llaman por lo contrario búsqueda informada o búsqueda heurística. Sin embargo, todas las estrategias se distinguen por el orden de expansión de los nodos (Russell y Norvig. 2004).

A continuación se muestran dos métodos de búsqueda no informada:

- Búsqueda Primero en Anchura 
- Búsqueda Primero en Profundidad

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

Berzal, F. s.f. Búsqueda en Inteligencia Artificial. DECSAI (Departamento de Ciencias de la Computación e I.A.). Universidad de Granada. Formato (PDF). Disponible en: http://elvex.ugr.es/decsai/iaio/slides/A3%20Search.pdf

Molina, J.; Torres, C. y Restrepo, C. 2008. TÉCNICAS DE INTELIGENCIA ARTIFICIAL PARA LA SOLUCIÓN DE LABERINTOS DE ESTRUCTURA DESCONOCIDA. Scientia et Technica Año XIV, No 39. Universidad Tecnológica de Pereira. ISSN 0122-1701. Formato (PDF). Disponible en: http://revistas.utp.edu.co/index.php/revistaciencia/article/viewFile/3171/1933

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf

martes, 3 de junio de 2014

BUSQUEDA PRIMERO EN ANCHURA

Fecha de clase: 27/mayo/2014
BÚSQUEDA PRIMERO EN ANCHURA
Se convierte en una cola (o fila de espera) que expande primero el nodo raíz, posteriormente todos los sucesores del nodo raíz, después sus sucesores, etc., expandiendo todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel (Russell y Norvig. 2004).

Los nodos de igual profundidad se ordenan arbitrariamente. Ese orden arbitrario es directamente heredado del que exista entre los operadores del sistema de producción. Mediante esta estrategia, el árbol de búsqueda se va generando por niveles de profundidad. Hasta que todos los nodos de un nivel no han sido revisados no se revisa ninguno del siguiente nivel (Rubio et al. 1998); es decir, cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)  

Las búsquedas a ciegas aplican los operadores (modelos de los efectos de las acciones, que al aplicarlos crean nodos sucesores) sin conocer bien el problema. La búsqueda por anchura es el método más simple de búsquedas a ciegas.  Este procedimiento actúa de forma uniforme construyendo un grafo de estados explícito desde el nodo inicial a cada uno de los predecesores con la propiedad de que una vez encontrado el nodo objetivo, se habrá encontrado el camino más corto, pero para esto tiene que almacenar el árbol completo y esto es un inconveniente puesto que el tamaño crece de manera exponencial respecto a la profundidad del nodo objetivo (menos profundo) (Nils, J. 2001)

Russell y Norvig (2004) puntualiza el siguiente punto que se debe considerar antes de elegir un método de búsqueda:

-          La cantidad de tiempo y memoria que utiliza para completar una búsqueda.
-          Son un problema más grande los requisitos de memoria para realizar una búsqueda por anchura que el tiempo de ejecución. Pero existen otras estrategias que requieren menos memoria.
-          Los problemas de búsqueda de complejidad exponencial no pueden resolverse por métodos a ciegas (sin información) salvo los casos pequeños.

A continuación se expresa el método de búsqueda primero en anchura utilizando un puzzle de 8 piezas, en el que se muestra el nodo inicial y el nodo objetivo, así mismo el orden como se genera un árbol de búsqueda mediante el uso de los operadores (mover la celda vacía a la izquierda, arriba, a la derecha y abajo) y la solución óptima para llegar al objetivo.   

Figura 1. Búsqueda primero en anchura para un puzzle de ocho piezas
Autor: Nils, J. (2001)

Si un estado objetivo es alcanzable, la búsqueda en anchura lo encuentra. La demostración es sencilla: el estado objetivo aparecerá en un cierto nivel de profundidad y, en un número finito de pasos (suponiendo un número finito de operadores y un número finito de posibles aplicaciones de un operador sobre un estado), llegará a ese nivel. Este mismo razonamiento muestra que la búsqueda en anchura siempre encuentra la secuencia solución más corta (una de las que tienen el mínimo número de aristas). Pero esto no significa en absoluto que realice un número pequeño de operaciones. Se trata de una propiedad de la secuencia solución encontrada, no del proceso por el que ha sido construida; de hecho, la búsqueda en anchura puede llegar a ser extremadamente ineficaz. (Rubio et al. 1998)

BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf

BÚSQUEDA PRIMERO EN PROFUNDIDAD

Fecha de clase: 03/junio/2014
BÚSQUEDA PRIMERO EN PROFUNDIDAD O BÚSQUEDA CON VUELTA ATRÁS

Esta estrategia intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible.

El principal problema de este algoritmo es que no acaba si existe la posibilidad de que hayan caminos infinitos. Una variante de este algoritmo que evita este problema es el algoritmo de profundidad limitada (Búsqueda en profundidad prioritaria), éste impone un límite máximo de profundidad que determina la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza encontrar la solución, ya que ésta puede estar a mayor profundidad que el límite impuesto. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)

Este método sólo genera un sucesor del nodo en cada paso y cada nodo llevará  una marca que indique qué operadores se pueden utilizar especificando el orden de aplicación, hasta llegar a una profundidad límite. Lo que se busca con esta profundidad límite es no realizar una búsqueda innecesaria; es decir desecha los las partes del grafo donde el nodo objetivo este muy lejano al nodo inicial.

Los nodos están ordenados según su profundidad, en orden creciente: los más profundos al principio, los menos profundos al final, conviertiendose en una PILA: los datos que primero entran son los últimos en salir. (Rubio et al. 1998)

Al igual que sucedía en la búsqueda en anchura, los nodos de igual profundidad se ordenan arbitrariamente, según el orden de las reglas u operadores.


Entonces este método también se lo conoce como vuelta atrás (cronológica) porque se establece la profundidad y al llegar al nodo límite sin alcanzar el nodo objetivo habría que regresar al nodo inmediatamente superior (el nodo límite ya revisado se lo debe desechar porque es obvio que no se pueden crear más sucesiones de él) y volver a realizar una búsqueda en este nodo y como este vendría a ser el nodo límite-1 podemos desprender otro nodo (último) y si en ésta parte del grafo tampoco se encuentra se realiza el mismo procedimiento anteriormente mencionado.


Figura 2. Generación de los primeros nodos en la búsqueda  primero en profundidad Autor: Nils, J. (2001)

La Búsqueda en profundidad iterativa lo que se hace es repetir sucesivamente el algoritmo de profundidad limitada, aumentando a cada iteración la profundidad máxima a la que le permitimos llegar. Este algoritmo obtendría el mismo efecto que el recorrido en anchura en cada iteración, ya que a cada paso recorremos un nivel más del espacio de búsqueda. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)

La ventaja de este proceso (Búsqueda en profundidad) es que el coste en memoria crece de forma lineal. La contraparte de esta estrategia es que el ir del límite hacia el inicio no asegura que la solución encontrada sea la óptima (más cercana o de menor profundidad) o el hecho de revisar varias partes del grafo que se encuentren lejanas, pudiendo estar cerca la solución.


BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Bibliografía Complementaria

UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf