LENGUAJE DE PROGRAMACIÓN PROLOG

INTRODUCCIÓN

En esta parte del blog se les mostrara la introducción a prolog, sus elementos, su sintaxis, sus reglas y hechos y ademas como consultar en prolog.

OBJETIVO

La siguiente clase tiene como objetivo aprender a utilizar el lenguaje de programación prolog.

CONOCIMIENTO

La parte fundamental de cualquier sistema que utiliza Inteligencia Artificial es el Conocimiento.

Los sistemas con Inteligencia Artificial adquieren el conocimiento a partir de la Educación o de la experiencia. La computadora obtiene el conocimiento, de forma general, a partir de uno o varios expertos humanos en determinada rama del saber

PROLOG

PROLOG es un lenguaje de programación declarativo. Los lenguajes declarativos se diferencian de los lenguajes imperativos o procedurales en que están basados en formalismos abstractos (PROLOG está basado en la lógica de predicados de primer orden y LISP, otro lenguaje de programación declarativa, en lambda calculo), y por tanto su semántica no depende de la máquina en la que se ejecutan. Las sentencias en estos lenguajes se entienden sin necesidad de hacer referencia al nivel máquina para explicar los efectos colaterales. Por tanto, un programa escrito en un lenguaje declarativo puede usarse como una especificación o una descripción formal de un problema. Otra ventaja de los programas escritos en lenguajes declarativos es que se pueden desarrollar y comprobar poco a poco, y pueden ser sintetizados o transformados sistemáticamente.

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

HECHOS EN PROLOG

Expresan relaciones entre objetos.  Supongamos que queremos expresar el hecho de que "un coche tiene ruedas".  Este hecho, consta de dos objetos, "coche" y "ruedas", y de una relación llamada "tiene".  La forma de representarlo en PROLOG es:

        tiene(coche,ruedas).

• Los nombres de objetos y relaciones deben comenzar con una letra minúscula.
• Primero se escribe la relación, y luego los objetos separados por comas y encerrados entre paréntesis.
• Al final de un hecho debe ir un punto (el carácter ".").

El orden de los objetos dentro de la relación es arbitrario, pero debemos ser coherentes a lo largo de la base de hechos. 

VARIABLES EN PROLOG

Representan objetos que el mismo PROLOG determinará.  Una variable puede estar instanciada ó no instanciada.  Estará instanciada cuando existe un objeto determinado representado por la variable.  De este modo, cuando preguntamos "¿Un coche tiene X?", PROLOG busca en los hechos cosas que tiene un coche y respondería:

        X = ruedas.
instanciando la variable X con el objeto ruedas.

• Los nombres de variables comienzan siempre por una letra mayúscula.

Un caso particular es la variable anónima, representada por el carácter subrayado ("_").  Es una especie de comodín que utilizaremos en aquellos lugares que debería aparecer una variable, pero no nos interesa darle un nombre concreto ya que no vamos a utilizarla posteriormente.


REGLAS EN PROLOG

Las reglas se utilizan en PROLOG para significar que un hecho depende de uno ó mas hechos.  Son la representación de las implicaciones lógicas del tipo p ---> q (p implica q). 

• Una regla consiste en una cabeza y un cuerpo, unidos por el signo ":-".
• La cabeza está formada por un único hecho.
• El cuerpo puede ser uno ó mas hechos (conjunción de hechos), separados por una coma (","), que actúa como el "y" lógico.
• Las reglas finalizan con un punto (".").

La cabeza en una regla PROLOG corresponde al consecuente de una implicación lógica, y el cuerpo al antecedente.  Este hecho puede conducir a errores de representación.  Supongamos el siguiente razonamiento lógico:

        tiempo(lluvioso) ----> suelo(mojado) 

        suelo(mojado)

Que el suelo esté mojado, es una condición suficiente de que el tiempo sea lluvioso, pero no necesaria.  Por lo tanto, a partir de ese hecho, no podemos deducir mediante la implicación, que esté lloviendo (pueden haber regado las calles).  La representación correcta en PROLOG, sería:

        suelo(mojado) :- tiempo(lluvioso). 

        suelo(mojado).

Adviértase que la regla esta "al revés".  Esto es así por el mecanismo de deducción hacia atrás que emplea PROLOG.  Si cometiéramos el error de representarla como:

        tiempo(lluvioso) :- suelo(mojado). 

        suelo(mojado).

PROLOG, partiendo del hecho de que el suelo esta  mojado, deduciría incorrectamente que el tiempo es lluvioso.

Para generalizar una relación entre objetos mediante una regla, utilizaremos variables.  Por ejemplo:

    Representación lógica     |   Representación PROLOG 

 -----------------------------+------------------------------- 

 es_un_coche(X) ---->         |tiene(X,ruedas) :- 

 tiene(X,ruedas)           |es_un_coche(X).

Con esta regla generalizamos el hecho de que cualquier objeto que sea un coche, tendrá ruedas.  Al igual que antes, el hecho de que un objeto tenga ruedas, no es una condición suficiente de que sea un coche.  Por lo tanto la representación inversa sería incorrecta. 

El ámbito de las variables.

Cuando en una regla aparece una variable, el ámbito de esa variable es únicamente esa regla.  Supongamos las siguientes reglas:

(1)  hermana_de(X,Y) :- hembra(X), padres(X,M,P), padres(Y,M,P). 

(2)  puede_robar(X,P) :- ladron(X), le_gusta_a(X,P), valioso(P).

Aunque en ambas aparece la variable X (y la variable P), no tiene nada que ver la X de la regla (1) con la de la regla (2), y por lo tanto, la instanciación de la X en (1) no implica la instanciacion en (2).  Sin embargo todas las X de una misma regla sí que se instanciar n con el mismo valor. 

OPERADORES EN PROLOG

Son predicados predefinidos en PROLOG para las operaciones matemáticas básicas.  Su sintaxis depende de la posición que ocupen, pudiendo ser infijos ó prefijos. Por ejemplo el operador suma ("+"), podemos encontrarlo en forma prefija '+(2,5)' ó bien infija, '2 + 5'. También disponemos de predicados de igualdad y desigualdad.

                X = Y         igual
                X \= Y        distinto
                X < Y         menor
                X > Y         mayor
                X =< Y        menor ó igual
                X >= Y        mayor ó igual

Al igual que en otros lenguajes de programación es necesario tener en  cuenta la precedencia y la asociatividad de los operadores antes de trabajar con ellos.
En cuanto a precedencia, es la típica.  Por ejemplo, 3+2*6 se evalúa como 3+(2*6).  En lo referente a la asociatividad, PROLOG es asociativo por la izquierda.  Así, 8/4/4 se interpreta como (8/4)/4.  De igual forma, 5+8/2/2 significa 5+((8/2)/2).

El operador 'is'.

Es un operador infijo, que en su parte derecha lleva un término que se interpreta como una expresión aritmética, contrastándose con el término de su izquierda.

Por ejemplo, la expresión '6 is 4+3.' es falsa.  Por otra parte, si la expresión es 'X is 4+3.', el resultado será la instanciación de X:
        X = 7

Una regla PROLOG puede ser esta:
        densidad(X,Y) :- poblacion(X,P), area(X,A), Y is P/A.


COMANDOS BÁSICOS EN PROLOG

• consult.

El predicado consult está pensado para leer y compilar un programa PROLOG ó bien para las situaciones en las que se precise añadir las clausulas existentes en un determinado fichero a las que ya están almacenadas y compiladas en la base de datos.  Su sintaxis puede ser una de las siguientes:consult(fichero).
consult('fichero.ext').
consult('c:\ia\prolog\fichero').

• recon.

El predicado recon es muy parecido a consult, con la salvedad de que las claúsulas existentes en el fichero consultado, reemplazan a las existentes en la base de hechos.  Puede ser útil para sustituir una única claúsula sin consultar todas las demás, situando esa claúsula en un fichero.  Su sintaxis es la misma que la de consult.
[NOTA: El predicado recon puede encontrarse como reconsult en otras implementaciones de PROLOG, tal como se indica en Clocksin & Mellish.]

• forget.

Tiene como fin eliminar de la base de datos actual aquellos hechos consultados de un fichero determinado.  Su sintaxis es:
forget(fichero).

• exitsys.

Este predicado nos devuelve al sistema operativo.

CONCLUSIÓN

Según el presente informe, se puede establecer que el lenguaje Prolog está orientado a la Inteligencia Artificial, usando la programación lógica. Gracias a su facilidad de programar y su sencilla sintaxis gramatical y numérica, se pueden escribir rápidamente y con pocos errores programas claramente lejibles, además cualquier usuario puede acceder a él si lo desea y sin problemas de entendimiento.

Por otra parte en este lenguaje al igual que otros, hay que tener en cuenta la asociatividad de los operadores antes de trabajar con él.

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

Alfedro A 2010. Prolog.  (En línea). EC. Consultado, 4 de Diciembre. 2014. Formato HTML. Disponible en: http://people.cis.ksu.edu/~schmidt/301s09/Lectures/prologS.html

Juan E 2011. Prolog.  (En línea). EC. Consultado, 4 de Diciembre. 2014. Formato HTML. Disponible en: http://www.nachocabanes.com/tutors/IntroProlog.html

Vicente O. 2004 Prolog.  (En línea). EC. Consultado, 4 de Diciembre. 2014. Formato PDF. Disponible en: http://mural.uv.es/mijuanlo/PracticasPROLOG.pdf

Wilfrido V. 2009 Prolog.  (En línea). EC. Consultado, 4 de Diciembre. 2014. Formato HTML. Disponible en: http://dis.unal.edu.co/~fgonza/courses/2006-I/AI/taller3-PROLOG.html

Franck L. 2011. Prolog.  (En línea). EC. Consultado, 4 de Diciembre. 2014. Formato PDF. Disponible en: http://www.itnuevolaredo.edu.mx/takeyas/apuntes/Inteligencia%20Artificial/Apuntes/IA/Prolog.pdf

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

INTRODUCCIÓN

Esta fue un a exposición grupal para explicar la diferencia entre entornos directos y continuos, señalando que la mayor parte de los entornos del mundo real son continuos, la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados. Esta clase proporciona una breve introducción a técnicas de búsqueda local para encontrar soluciones óptimas en espacios continuos. Al igual daremos una idea delo que es una búsqueda online y ambientes desconocidos.

OBJETIVO

La siguiente exposición tiene como objetivos:

•  Comprender la búsqueda local en espacios continuos.
•  Entender la búsqueda online y ambientes desconocidos.

BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS

La mayor parte de los entornos del mundo real son continuos. Aún ninguno de los algoritmos descritos puede manejar espacios de estados continuos, £la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados! Esta sección proporciona una muy breve introducción a técnicas de búsqueda local para encontrar soluciones óptimas en espacios continuos. La literatura sobre este tema es enorme; muchas de las técnicas básicas se originaron en el siglo xvn, después del desarrollo de cálculo Newton y Leibniz. Encontraremos usos para estas técnicas en varios lugares del libro, incluso en los capítulos sobre aprendizaje, visión y robótica. En resumen, cualquier cosa que trata con el mundo real.

La búsqueda del gradiente empírico es la misma que la ascensión de colinas con subida mas escarpada en una versión discreteada del espacio de estados, para muchos problemas el algoritmo mas eficaz es el venerable método de Newton-Raphson, es una técnica general para encontrar raíces de funciones, es decir la solución a la ecuación.

Por ejemplo, queremos ubicar un espacio para la construcción perfecta de un edificio en una terreno o una parte de la ciudad, aquí deberiamos utilizar la búsqueda en espacios continuos para poder llegar al mejor resultado.

AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

Hasta ahora nos hemos centrado en agentes que usan algoritmos de búsqueda offline. Ellos calculan una solución completa antes de poner un pie en el mundo .Y luego ejecutan la solución sin recurrir a sus percepciones. En contraste, un agente de búsqueda online es una buena idea en dominios dinámicos o semidinámicos. 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 sólo considere lo que realmente pasa. Por ejemplo, a un agente que juega al ajedrez se le aconseja que haga su primer movimiento mucho antes de que se haya resuelto el curso completo del juego.

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

·        AGENTE DE BÚSQUEDA EN LÍNEA (ONLINE)

Después de cada acción, un agente online recibe una percepción al decirle que estado ha alcanzado; de esta información, puede aumentar su mapa del entorno. El mapa actual se usa para decidir dónde ir después. Esta intercalación de planificación y acción significa que los algoritmos  de búsqueda online son bastantes diferentes de los algoritmos de búsqueda offline.

Un algoritmo online, por otra parte puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar atravez de todo el árbol para expandir el siguiente nodo, parece mejor expandir los nodos en un orden local. La búsqueda primero en profundidad tiene exactamente esta propiedad, porque el siguiente nodo a expandir es hijo del nodo anteriormente expandido.

OBJETIVO DEL AGENTE

Alcanzar el estado objetivo minimizando costos

TIPO DE BUSCADORES

Directorios

Meta buscadores

Agentes de Búsqueda

Buscadores Personalizados

Buscadores Especializados y Temáticos

DIFERENCIA ENTRE OFF-LINE Y ON-LINE

Búsqueda off-line:

– Calcula una solución completa antes de poner un pie en el mundo real.

– Después ejecutan la solución sin recurrir a las percepciones.

Búsqueda on-line: Intercala el calcula y la acción.

– Toma una acción

– Observa el entorno

– Calcula la siguiente acción.

Usos de la búsqueda on-line:

– Problemas de exploración, donde el agente desconoce los estados y acciones.

Problemas  de búsqueda en línea (online)

Un problema de búsqueda online puede resolverse solamente por un agente que ejecute acciones, más que por un proceso puramente computacional. Asumiremos que el agente sabe lo siguiente:

·         Acciones (). Que devuelve una lista de acciones permitidas en el estado s;

·         Funciones de coste individual c(s, a, s’). hay que tener en cuenta que no pude usarse hasta que el agente sepa que s’ es el resultado; y

·         Test-Objetivo(s)

CONCLUSIÓN

Podemos decir que la función sucesor devuelve infinitos estados ademas esta búsquedas solo consideran lo que realmente pasa en ese estado y después tomar nuevas acciones.

Después de haber analizado todas esas búsquedas podemos notar que esta búsqueda simplemente lo que hace es analizar lo que realmente sucede a su entorno y así poder calcular la siguiente acción.

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

José A 2006. Búsqueda local en espacios continuos.  (En línea). EC. Consultado, 27 de Noviembre. 2014. Formato PDF. Disponible en: https://prezi.com/mkmgqd1z5xzx/untitled-prezi/

Melania Z 2012. Búsqueda online.  (En línea). EC. Consultado, 27 de Noviembre. 2014. Formato PDF. Disponible en: http://www.sanchezcrespo.org/Docencia/IA/IA%20-%20Tema%203B%20-%20Busquedas%20v1.3.pdf

ALGORITMO DE BÚSQUEDA LOCAL Y PROBLEMAS DE OPTIMIZACIÓN

INTRODUCCIÓN

La clase impartida en este día ayudo a despejar muchas dudas ya que notamos que los algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas esta se consigue manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto

OBJETIVO

La siguiente clase tiene como objetivo entender los algoritmos de búsqueda locales.

ALGORITMO DE BÚSQUEDA LOCAL Y PROBLEMAS DE OPTIMIZACIÓN

Los algoritmos de búsqueda que hemos visto hasta ahora se diseñan para explorar sistemáticamente espacios de búsqueda. Esta forma sistemática se alcanza manteniendo uno o más caminos en memoria y registrando qué alternativas se han explorado en cada punto a lo largo del camino y cuáles no. Cuando se encuentra un objetivo, el camino a ese objetivo también constituye una solución al problema. En muchos problemas, sin embargo, el camino al objetivo es irrelevante. Por ejemplo, en el problema de las 8 -reinas, lo que importa es la configuración final de las reinas, no el orden en las cuales se añaden. Esta clase de problemas incluyen muchas aplicaciones importantes como diseño de circuitos integrados, disposición del suelo de una fábrica, programación del trabajo en tiendas, programación automática, optimización de redes de telecomunicaciones, dirigir un vehículo, y la gestión de carteras.

Si no importa el camino al objetivo, podemos considerar una clase diferente de algoritmos que no se preocupen en absoluto de los caminos. Los algoritmos de búsqueda local funcionan con un solo estado actual (más que múltiples caminos) y generalmente se mueve sólo a los vecinos del estado. Típicamente, los caminos seguidos por la búsqueda no se retienen. Aunque los algoritmos de búsqueda local no son sistemáticos, tienen dos ventajas claves: 

(1) Usan muy poca memoria (por lo general una cantidad constante)

(2) Pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

ALGORITMO DE BÚSQUEDA DE ASCENSIÓN DE COLINAS

• Bucles que continuamente se mueve en dirección del valor creciente (hacia arriba)
• Termina cuando alcanza "un pico" donde ningún vecino tiene un valor más alto.

Características: 

• Es un algoritmo voraz, que no mantiene un árbol de búsqueda, sino sólo la representación del estado actual y el valor de su función objetivo. Mantiene una estructura de datos del nodo actual que necesita sólo el registro del estado y su valor de función objetivo.
• No se mira más allá de los vecinos inmediatos del estado actual.
• Escoge el vecino que tiene un mejor valor de la función objetivo.
• Finaliza cuando alcanza un "extremo" (máximo o mínimo, depende del pateamiento)

CONCLUSIÓN

Después de haber analizado esta temática concluimos que estos algoritmos de búsqueda son simplemente algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas que se continúan manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

Macías, J 2013. ALGORITMO DE BÚSQUEDA DE ASCENSIÓN DE COLINAS. (En línea). EC. Consultado, 20 de Noviembre. 2014. Formato PDF. Disponible en: https://prezi.com/z135qjn4tnya/algoritmos-de-busqueda-local-y-problemas-de-optimizacion/

Muñoz, A.  2010. Búsqueda Local. (En línea). EC. Consultado, 20 de Noviembre. 2014. Formato PDF. Disponible en: http://sci2s.ugr.es/docencia/metah/pdf/Tema02-BusquedaLocal-13-14.pdf

FUNCIONES HEURÍSTICAS

INTRODUCCIÓN

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas. Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.

OBJETIVO

La siguiente clase tiene como objetivo entender que son las funciones heurísticas.

FUNCIONES HEURÍSTICAS

El coste medio de la solución para los casos generados al azar del 8-puzle son aproxi­madamente 22 pasos. El factor de ramificación es aproximadamente tres. (Cuando la ficha vacía está en el medio, hay cuatro movimientos posibles; cuando está en una es­ quina hay dos; y cuando está a lo largo de un borde hay tres.) Esto significa que una búsqueda exhaustiva a profundidad 22 miraría sobre 3^33 = 3,1 X 10^10 estados. Mante­niendo la pista de los estados repetidos, podríamos reducirlo a un factor de aproxima­damente 170.000, porque hay sólo 9 !/2 = 181.440 estados distintos que son alcanzables.

• h1 = número de piezas mal colocadas, las 8 piezas están fuera de su posición, así que el estado inicial tiene h1 = 8. h1 es una heurística admisi­ble, porque está claro que cualquier pieza que está fuera de su lugar debe mover­ se por lo menos una vez. 

• h2 = suma de las distancias de las piezas a sus posiciones en el objetivo. Como las piezas no pueden moverse en diagonal, la distancia que contaremos será la suma de las distancias horizontales y verticales. Esto se llama a veces la distancia en la ciudad o Distancia de Manhatta h2 es también admisible, porque cualquier movimiento que se puede hacer es mover una pieza un paso más cerca del objeti­vo. Las piezas 1 a 8 en el estado inicial nos dan una distancia de Manhattan de h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18 

Como era de esperar, ninguna sobrestima el coste solución verdadero, que es 26.

El efecto de la precisión heurística en el rendimiento

Inventar funciones heurísticas admisibles 

A un problema con menos restricciones en las acciones se le llama problema relajado 

Una ficha puede moverse del cuadrado A al cuadrado B si A es horizontalmente o verticalmente adyacente a B y B es la vacía. 

Podemos generar tres problemas relajados quitando una o ambas condiciones: 

(a) Una ficha puede moverse del cuadrado A al cuadrado B si A es adyacente a B. 

h2 

(b) Una ficha puede moverse del cuadrado A al cuadrado B si B es el vacío. 

h2

(c) Una ficha puede moverse del cuadrado A al cuadrado B. 

h1 

CONCLUSIÓN

Las funciones heurísticas son funciones que busque el mejor camino para llegar a un resultado y podemos inventar a partir de las que tenemos definidas.

BIBLIOGRAFÍA

Zambrano, R. 2010. Funciones Heuristicas. (En línea). Disponible en: https://www.cs.us.es/cursos/ia1/temas/tema-04.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

ESTRATEGIAS DE BÚSQUEDA INFORMADA

INTRODUCCIÓN

Las estrategias de búsqueda no informada resuelven problemas mediante generación sistemática de estados, pero son muy ineficientes

Vamos a ver cómo las estrategias de búsqueda informada o heurística, usando conocimiento específico del problema, pueden resolver problemas más eficientemente

OBJETIVO

La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda informada.

Búsqueda voraz primero el mejor

La búsqueda voraz priman el mejor trata de expandir el nodo más cercano al objetivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: ñn) = h(n). Veamos cómo trabaja para los problemas de encontrar una ruta en Rumania utilizando la heurística «Bstanriaoi linea recta que llamaremos hDUt Si el objetivo es Bucarest, tendremos que conocer las distancias en línea recta a Bucarest, que se muestran en la. Por ejemplo, h[xJyEn(Arad)) = 366. Notemos que los valores de hDLRno pueden calcularse de la descripción de problema en sí mismo. Además, debemos tener una cierta cantidad de experiencia para saber que hnK está correlacionada con las distancias reales del camino y es, por lo tanto, una heurística útil.

BÚSQUEDA A*

Características Principales

Como todo algoritmo de búsqueda en anchura, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella. Si para todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.

Para garantizar la optimalidad del algoritmo, la función h(n) debe ser admisible, o sea que no sobrestime el coste real de alcanzar el nodo objetivo.

De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor. La complejidad computacional está relacionada con la calidad de laheurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena h'(n), el algoritmo se ejecutará en tiempo lineal.

El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, como pueden ser RTA*, IDA* o SMA*.

El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística.

BÚSQUEDA CON MEMORIA ACOTADA

Problema del algoritmo A* => Altos requerimientos de memoria.
Algoritmo A*PI: Los requerimientos de memoria se pueden solucionar aplicando el algoritmo de PI
(Profundidad Iterativa) al A*:
– Función de corte: f-coste (g+h)
– En cada iteración el valor del corte es f-coste más pequeño de cualquier nodo que excedió el coste de la iteración anterior.
Algoritmos con memoria acotada:
– BRPM: Búsqueda recursiva primero el mejor.
– A*M: Algoritmo A* con memoria acotada.
– A*MS: Algoritmo A* con memoria simplificada.

CONCLUSIÓN

Búsqueda voraz primero el mejor.- Expande el nodo más cercano al objetivo, asumiendo que probablemente conduzca más rápidamente a la solución.  La función de evaluación f(n) es la función heurística  h(n)=f(n) = h(n) donde h(n) = costo estimado del camino más barato desde el nodo n hasta el objetivo

Búsqueda A*.- Minimizar el costo estimado total de la solución
Evalúa los nodos combinando g(n) y h(n)
 g(n): costo de haber alcanzado n
 h(n): costo para llegar desde n hasta el objetivo
 f(n) = g(n) + h(n) -> costo más barato estimado de la f(n) = g(n) + h(n) -> costo más barato estimado de la solución a través de n En cada paso se expande el nodo con el valor más bajo de f(n), ó sea, de g(n)+h(n)

La búsqueda A* es óptima siempre y cuando la función heurística h(n) sea una heurística admisible,
nunca sobreestime el costo de alcanzar el objetivo, son funciones optimistas.

BIBLIOGRAFÍA

Cesar S 2008. Búsqueda Informada.  (En línea). EC. Consultado, 13 de Noviembre. 2014. Formato HTML. Disponible en: http://www.ecured.cu/index.php/Algoritmo_de_B%C3%BAsqueda_Heur%C3%ADstica_A*
Ruiz, j. 2012. Búsqueda Informada. (En línea). Disponible en: http://www.cs.us.es/cursos/ia1/temas/tema-06.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.