lunes, 10 de noviembre de 2014

Búsqueda primero en profundidad

Primero se expande el nodo más profundo del árbol de búsqueda. No es un método completamente óptimo; su complejidad temporal O(bm) y su complejidad espacial es O(bm), en donde m es la profundidad máxima. Los árboles de búsqueda cuya profundidad es muy grande o infinita, invalidan la utilidad de este método.
Sólo si la búsqueda conduce a un callejón sin salida (un nodo sin meta que no tiene expansión), se revierte la búsqueda y se expanden los nodos de niveles menos profundos.
http://uniandesia.wikispaces.com/file/view/BUSQUEDA1.jpg/239065037/BUSQUEDA1.jpg

Búsquedas Bidireccionales

Ayuda a reducir notablemente la complejidad temporal, aunque no siempre pueda utilizársele.
La cantidad de memoria que necesita puede hacerla poco práctica.
Es básicamente, una búsqueda simultánea que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio.
http://inventariacomunicacionsocial.files.wordpress.com/2013/11/comunicacic3b3n_interna.jpg

Búsqueda: Primero en profundidad con iteraciones

Se emplea la búsqueda con límite de profundidad, pero los límites van aumentando hasta encontrar una meta. Es completa y óptima; su complejidad temporal es O(bd) y su complejidad espacial es O(bd).
https://nelsonsilva13.files.wordpress.com/2014/06/g8.png

Búsqueda de profundidad limitada

Se pone un límite a la búsqueda preferente por profundidad. Si el límite fuera igual a la profundidad del estado meta más superficial, se reduce al mínimo la complejidad espaciotemporal.
http://dmi.uib.es/~abasolo/intart/2-figura1.JPG

Búsqueda de costo uniforme

Primero se expande el nodo hoja de menor costo. Es un método completo y, a diferencia de la
búsqueda preferente por amplitud, es óptimo incluso si el costo de cada uno de los operadores
es distinto. Su complejidad espacio-temporal es la misma que la de la búsqueda preferente por
amplitud.
Siempre se tiene un costo o unidades. Los costos deben ser positivos, caso contrario no se
aplica esta búsqueda.
http://users.dcc.uchile.cl/~bebustos/apuntes/cc3001/Diccionario/abbopt1.png

Búsqueda primero en anchura

Búsqueda preferente por amplitud(anchura)
Primero se expande el nodo más superficial del árbol de búsqueda. Es un método completo,
óptimo para operadores de costo unitario. Su complejidad espacio-temporal es O(bd). En
muchos casos, la complejidad espacial impide que sea práctico.
Debo expandir la profundidad (d) antes de expandir la profundidad siguiente (d+1) empezando
por la izquierda. d = profundidad nodo raíz = estado inicial.
http://www.monografias.com/trabajos76/tecnicas-inteligencia-artificial-software-educativo/image014.jpg

Estrategias de búsqueda no informada

Buena parte de los esfuerzos invertidos en el área de la búsqueda han quedado en la
determinación de la estrategia de búsqueda adecuada para un problema. Se utiliza para
hallar una solución "sin información".
o Búsqueda preferente por amplitud(anchura)
o Búsqueda de costo uniforme
o Búsqueda preferente por profundidad
o Búsqueda limitada por profundidad
o Búsqueda por profundización iterativa
o Búsqueda birideccional

jueves, 9 de octubre de 2014

Agentes que planifican búsquedas


Un agente inteligente, debe maximizar sus medidas de rendimiento lo más posible, esto siempre y cuándo el agente pueda elegir objetivos y a su vez, satisfacerlo.
Un sencillo agente que resuelve problemas, primeramente formúla un objetivo y un problema, realiza una secuencia de acciones que deberían de resolver dicho problema, ejecutándo entonces las acciones, una por vez. Siempre y cuándo termine un objetivo, se completa un ciclo y posteriormente formúla otro objetivo. Suponiendo entonces que la solución encontrada estará trabajando bién.
FORMULAR LOS PROBLEMAS
 El proceso de eliminar detalles de un represantación se lo define cómo: abstracción, por ejemplo: Una acción de conducir tiene muchísimos efectos. Además del cambio de lugar de conductor, vehículo y sus ocupantes, pasa el tiempo, consume hidrocarburos, genera polución, y el agente cambia.

http://applicacion.com/wp-content/uploads/2012/12/aprovechar-busqueda-imagenes-google.jpg
La resolución de problemas es fundamental para la mayoría de las aplicaciones de Inteligencia Artificial (IA). De hecho, la capacidad de resolver problemas suele usarse como una medida de la inteligencia tanto para el ser humano como para la computadora. Hay principalmente dos clases de problemas. Una primera clase puede ser resuelta usando algún tipo de procedimiento determinista cuyo éxito esté garantizado. A este procedimiento se le llama de computación. La resolución por computación normalmente sólo se aplica a aquellos tipos de problemas para los que existan tales procedimientos, como en matemáticas.
Se puede con frecuencia traducir los métodos usados para resolver estos problemas de manera fácil, a un algoritmo que pueda ser ejecutado por una computadora. No obstante, a pesar de que pocos problemas reales se prestan a soluciones computables, deben ser situados en la segunda categoría, que consiste en problemas que se resuelven con la búsqueda de una solución. Este es el método de resolución de problemas del que se preocupa la IA
 

Resolver problemas mediante búsquedas







Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados o espacio de búsqueda

(El conjunto de todos los nodos) no es necesario hacer una exhaustiva enumeración de todos los estados 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 o estado meta 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. Podríamos decir que una regla tiene una parte izquierda y una 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 (acción).
La heurística es la información acerca de la posibilidad de que un nodo específico sea mejor para intentar la próxima elección que cualquier otro nodo.

Agentes para la solución de problemas (Metas), basado en metas, tiene algoritmos de
búsqueda, el esqueleto es:
• Formulación del Problema
• Formulación de Metas
• Búsqueda (Algoritmos) para llegar del Estado Inicial al estado de meta
• Solución