INGENIERIA EN DESARROLLO DE

SOFTWARE.

ALUMNO: JORGE ALBERTO

HERNANDEZ TERÁN.

PROFESOR: UZZIEL QUIROZ

CASTAÑEDA.

TEMA: RESUMEN DEL TEMA 3 Y 4.

 TEMA 3 RESOLVER PROBLEMAS MEDIANTE BUSQUEDA

En este Resumen se describirá una clase de agente basado en objetivos

llamado agente resolvente de problemas, estos agentes deciden que hacer
para encontrar secuencias de acciones que conduzcan a estados deseables.
Comenzaremos definiendo los elementos que constituyen el problema y su
solución. Además, estudiaremos algunos métodos de búsqueda ya que cuando
se esté ante un problema la mejor opción sería aplicar alguno de estos
métodos.

AGENTES RESOLVENTES DE PROBLEMAS

Estos agentes están constituidos por dos elementos que son: una solución y un
problema, estos agentes deben seguir un objetivo, el cual es el encargado de
organizar el comportamiento del agente, según el problema.
 Formulación del problema
 Formulación del objetivo
 Fase de búsqueda
 Ejecuta

PROBLEMAS Y SOLUCIONES BIEN DEFINIDOS

El problema tiene cuatro componentes principales que son:
Estado Inicial: Es el lugar donde comienza el agente. Ejemplo si una agente
está en un lugar A y quiere llegar a un lugar B, su estado inicial será A.
Test Objetivo: Es donde se determina si un estado es objetivo, es un conjunto
de posibles estados objetivos en si lo que hace es comprobar si el estado
pertenece a ellos. Ejemplo si una agente está en un lugar A y quiere ir a un
lugar B, el test objetivo es llegar a B.
Función Sucesor: son las posibles acciones que un agente realiza y con estas
obtener como resultado un estado. Ejemplo si una agente está en un lugar A y
quiere ir a un lugar B, la función sucesora sería ir a B, estar en B.
Función Costo: Es el valor de la ruta al cual se le asigna un costo. Con la
función costo se puede reflejar las medidas de rendimiento de un agente
resolventes-problemas.

ESTARTEGIAS DE BUSQUEDA NO INFORMADA

La búsqueda no informada como su no nombre lo dice es cuando existen
escases o no hay ninguna información adicional sobre los estados que están
más allá de lo que específica el problema, y esto conlleva a generar varias
acciones y estados sucesores
BUSQUEDA PRIMERO EN ANCHURA
La búsqueda primero en anchura es una estrategia sencilla en la que se
expande primero el nodo raíz, a continuación, se expanden todos los sucesores
del nodo

raíz, después sus sucesores, etc. En general, se expanden todos los nodos a
una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del
próximo nivel. Esta técnica utiliza el método FIFO; primero en entrar y primero
en salir. Este método es óptimo cuando el costo de todos los nodos es igual.

BUSQUEDA DE COSTO UNIFORME

La búsqueda de costo uniforme expande el nodo n con el camino de costo más
pequeño. Notemos que, si todos los costos son iguales, es idéntico a la
búsqueda primero en anchura. La búsqueda de costo uniforme no se preocupa
por el número de pasos que tiene un camino, pero si sobre su coste total. Por
lo tanto, este se meterá en un bucle infinito si expande un nodo que tiene una
acción de coste cero que conduzca de nuevo al mismo estado.
BUSQUEDA PRIMERO EN PROFUNDIDAD
Esta búsqueda expande siempre el nodo más profundo en la frontera del árbol,
si la solución no fue encontrada por la rama expandida, entonces la búsqueda
retrocede y expande último nodo no expandido, se podría implementar con la
búsqueda de árbol con una cola que utiliza el método LIFO último en entrar y
primero en salir.

BUSQUEDA DE PROFUNDIDAD LIMITADA

Su procedimiento consiste en visitar todos los nodos de forma ordenada pero
no uniforme en un camino concreto, dejando caminos sin visitar en su proceso,
imponiendo un límite máximo de profundidad de búsqueda.
La búsqueda en profundidad limitada encontrará una solución si esta se
encuentra dentro del límite de profundidad.
BUSQUEDA PRIMERO CON PROFUNDIDAD ITERATIVA
Es una estrategia general, usada a menudo en combinación con la búsqueda
primero en profundidad, la cual encuentra el mejor límite de profundidad. Esto
se hace aumentando gradualmente el límite (primero 0, después 1, después 2,
etcétera) hasta que encontramos un objetivo. Esto ocurrirá cuando el límite de
profundidad alcanza d, profundidad del nodo objetivo.

BUSQUEDA BIDIRECCIONAL
Esta inicia dos búsquedas al mismo tiempo una desde el nodo raíz y otra desde
el objetivo, por lo menos una de las búsquedas debe ser en anchura para que
en algún momento se encuentren.
  

Para resolver problemas de búsqueda se deberían de ponen en práctica

los diversos tipos de búsqueda ya que si no se los usan es posible caer
en bucles infinitos o quizás llegar al resultado, pero de una manera poco
eficiente, además la aplicación de estas técnicas ayuda a mejorar el
rendimiento acortando distancias y reduciendo costos ya sea de caminos
o recursos.

TEMA 4 BÚSQUEDA INFORMADA Y EXPLORADA

Las estrategias de búsqueda informada también llamada búsqueda heurística

cuentan con información adicional del problema que busca resolver el agente,
es por esto que puede encontrar las soluciones de una manera más eficiente;
al contrario de las no informadas que, aunque implementen métodos de
búsqueda bidireccionales o con limitación en los niveles, existe la probabilidad
de que el agente nunca encuentre el objetivo y entre en un ciclo infinito.
Dentro de las búsquedas informadas se define el estado inicial en el que se
puede encontrar el agente, la función sucesora que define el conjunto de
estados posibles que pueden darse a partir del estado inicial, el costo del
camino y la función heurística que brinda la información adicional para llegar a
la solución del problema.

A continuación, se definen las diferentes búsquedas informadas expuestas en

el libro Inteligencia Artificial un enfoque moderno, sus características y como
permiten llegar a la solución de una mejor manera que las búsquedas son .
¿QUÉ ES UNA FUNCIÓN HEURÍSTICA?

La palabra heurística, se deriva del verbo griego heuriskein, que significa

“encontrar” o “descubrir”. El término técnico “heurística” ha adoptado diversas

connotaciones a lo largo de la historia de la IA. Actualmente, el término

heurística se utiliza más bien como adjetivo, para referirse a cualquier técnica
que permita mejorar el desempeño de caso promedio en una tarea de
resolución de problemas, aunque no necesariamente permita mejorar el
desempeño del peor de los casos. Específicamente, en el área de los
algoritmos de búsqueda, se refiere a una función mediante la cual se obtiene
un estimado del costo de una solución.
BÚSQUEDAS INFORMADA
La búsqueda informada utiliza el conocimiento específico del problema más allá
de la definición del problema en sí mismo, puede encontrar soluciones de una
manera más eficiente que una estrategia no informada.

A continuación, se muestras tres búsquedas informadas que utilizan una

función heurística para mejorar su desempeño.
Figura 1: Estrategias de Búsqueda Informada

BÚSQUEDA VORAZ PRIMERO 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: f(n)=h(n).
Ejemplo:
Un sistema puede encontrarse en un conjunto de estados {S0, …, S8}. Su
estado inicial es S0y los estados meta, S7y S8. Considérense los siguientes
operadores y costes asociados a cada operador:
OP1: S3→S8(coste 5) OP2: S2→S3(coste 25) OP3: S5→S3(coste 20)
OP4: S1→S2(coste 100) OP5: S4→S2(coste 80) OP6: S6→S7(coste 100)
OP7: S0→S1(coste 10) OP8: S0→S4(coste 10) OP9: S0→S5(coste 20)
OP10: S0→S6(coste 20)
Considérense también los siguientes valores de la función heurística h, que
estima el menor coste desde cada nodo a un nodo meta:
h(S0) = 40 h(S3) = 10 h(S6) = 110
h(S1) = 20 h(S4) = 40 h(S7) = 0
h(S2) = 20 h(S5) = 100 h(S8) = 0
En este caso la característica deseable para expandir los nodos se basa en
encontrar aquel que tenga el menor valor para la función h(s).

Figura 2: Ejemplo búsqueda voraz primero

Se puede observar en la tabla que el nodo S7 también tiene un valor de 0 para

la función h(s). Sin embargo, el algoritmo de búsqueda primero el mejor tiene
como objetivo encontrar la mejor ruta o solución basado en el los valores dados

por una función heurística que se aplica a cada nodo del recorrido y en este
caso esa respuesta está dada por el camino que lleva hacia el nodo S8.

 BÚSQUEDA A*: MINIMIZAR EL COSTO ESTIMADO TOTAL DE LA

SOLUCIÓN
A la forma más ampliamente conocida de la búsqueda primero el mejor se le
llama búsqueda A* (pronunciada “búsqueda A-estrella”). Evalúa los nodos
combinando g(n), el coste para alcanzar el nodo, y h(n), el coste de ir al nodo
objetivo.
f(n)=g(n)+h(n)
Ya que la g(n) nos da el coste del camino desde el nodo inicial al nodo n, y la
h(n) el coste estimado del camino más barato desde n al objetivo, tenemos:

f(n)= coste más barato estimado de la solución a través de n

Así, tratamos de encontrar la solución más barata, es razonable intentar
primero el nodo con el valor más bajo de g(n). Resulta que esta estrategia es
más que razonable: con tal de que la función heurística h(n) satisfaga ciertas
condiciones, la búsqueda A* es tanto compleja como optima.
La optimalidad de A* es sencilla de analizar si se usa con la BUSQUEDA-
ARBOLES. En este caso, A* es óptima si h(n) es una heurística admisible, es
decir, con tal de que la h(n) nunca subestime el coste de alcanzar el objetivo.
Las heurísticas admisibles son por naturaleza optimistas, porque piensan que
el coste de resolver el problema es menor que el que es en realidad. Ya
que g(n) es el coste exacto para alcanzar n, tenemos como consecuencia
inmediata que la f(n) nunca sobrestima el coste verdadero de una solución a
través de n.
Ejemplo:
Aplicar el algoritmo A* para hallar el camino que une las ciudades 1 y 8.
Las distancias pro carretera entre las distancias ciudades vienen
especificadas por la siguiente tabla:
 

Además, se dispone de la distancia acerca en línea recta que existe entre

todas las ciudades con la ciudad de destino.

Solución:
DE 1 A 2: 800 + 200 = 1000

DE 2 A 3: 650 + 150 = 800

DE 3 A 6: 500 + 225 = 725

DE 6 A 7: 375 + 450 = 825

DE 7 A 8: 125 + 125 = 250

Total, costo:   1000+800+725+450+125=3600 
Figura 3: Solución Búsqueda A*

BÚSQUEDA HEURÍSTICA CON MEMORIA ACOTADA

La forma más simple de reducir la exigencia de memoria para A* es adaptar la
idea de profundizar iterativamente al contexto de búsqueda heurística,
resultando así el algoritmo A* de profundidad iterativa (A*PI). La diferencia
principal entre A*PI y la profundidad iterativa estándar es que el corte utilizado
es el f-coste (g+h) más que la profundidad; en cada iteración, el valor del coste
es el f-coste más pequeño de cualquier nodo que excedió el corte de la
iteración anterior. A*PI es práctico para muchos problemas con costos unidad y
evita el trabajo asociado con el mantenimiento de una cola ordenada de nodos.
APRENDE A BUSCAR MEJOR
Hemos presentado varias estrategias fijas (primero en anchura, primero la
mejor avara, etcétera) diseñadas por informáticos. ¿Podría un agente aprender
a buscar mejor? La respuesta es sí, y el método se apoya sobre un concepto
importante llamado el espacio de estados meta nivel.

Para problemas más difíciles habrá muchos más errores, y un algoritmo de

aprendizaje meta nivel puede aprender de estas experiencias para evitar
explorar arboles no prometedores. El objetivo del aprendizaje es reducir al
mínimo el coste total de resolver el problema, compensar el costo
computacional y el coste del camino.

La heurística en los algoritmos es la que permite obtener un costo menor

en el camino a la solución de un problema. Las búsquedas informadas
utilizan una función heurística y el costo del camino para encontrar la
solución, es decir expanden el nodo en el árbol donde el costo sea el
menor.

La búsqueda voraz primero o primero el mejor expande el nodo donde el

costo sea menor, la búsqueda A* expande los nodos donde la suma del
costo y la heurística sea menor para tener mejor precisión en la búsqueda
de la solución.

La búsqueda heurística con memoria acotada reduce el uso de memoria

que utiliza la búsqueda A*. pero es importante recordar que para
problemas más difíciles habrá errores más grandes un algoritmo de
búsqueda podría no encontrar la solución, aunque cuente con
información parcial y quedarse en un ciclo repetitivo, esto se busca
mejorar a través de los algoritmos de meta nivel que pueden aprender de
las experiencias para no explorar arboles no prometedores.