Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Copy of Búsqueda ciega

IA search methods: uninformed or blind search.
by

Jorge Saavedra

on 10 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of Búsqueda ciega

¿Qué es la búsqueda ciega? Búsqueda Bidireccional Breadth First Search Búsqueda Ciega Iterative Deepening
Search UCS expande primero el nodo con menor costo Depth Limited Search Criterios evaluados Esta estrategia es una modificación del BFS: (cc) photo by jimmyharris on Flickr Depth First Search Son estrategias de búsqueda que no poseen información acerca del número de pasos o el costo de pasar del estado actual al estado final o estado objetivo.
Por lo tanto realizara una búsqueda evaluando cada uno de los estados, hasta encontrar el estado deseado. Lo único que pueden hacer es distinguir entre un estado objetivo y uno que no lo es. Tipos: BFS: Breadth First Search
Búsqueda por Amplitud DFS: Depth First Search
Búsqueda Preferente
por Profundidad DLS: Depth Limited Search
Búsqueda limitada por
Profundidad IDS: Iterative Deepening Search
Búsqueda por Profundidad
Iterativa BS: Bidirectional Search
Búsqueda Bidireccional UCS: Uniform cost search
Búsqueda de Costo Uniforme Completitud Complejidad Temporal Complejidad Espacial Optimalidad ¿La estattegia encontrará la solución, si esta existe? ¿Cuánto se tarda en en contrar la solución? ¿Cuánta memoria se requiere para ejecutar la búsqueda? Cuando hay varias soluciones distintas, ¿encontrará la estrategia la más adecuada? Es una estrategia sistemática: considera todos los caminos de costo 1, luego los de costo 2, y así en adelante. Garantías: Si existe una solución, será encontrada.

Si existen varias, se encontrará primero la que se encuentre más cerca del nodo inicial. Evaluación: Completitud: Sí.
Óptima: sí, si el costo es una función no decreciente de la profundidad del nodo. Consideraciones de tiempo y espacio: En el peor de los casos, si se tiene un árbol de profundidad d, si sólo se pueden expander b nodos en cada nivel, entonces el número máximo de nodos expandidos antes de encontrar una solución es: Ejemplo de BFS Depth First Search Dado que la solución menos profunda no necesariamente es la que menos costo implica para llegar, BFS no siempre obtiene la mejor solución. Restricciones: Para obtener la solución óptima, el costo de cada camino no debe decrecer. Esta estrategia siempre va expandiendo uno de los nodos al nivel más profundo del árbol. Sólo al llegar a un nodo sin hijos que no sea el objetivo, dejará de expandir en esa dirección: regresará al nodo más cercano y seguirá expandiendo en profundidad a partir de él. La memoria requerida por este método es mucho menor comparada con la BFS puesto que sólo requiere guardar el nodo raíz y los nodos intermedios entre éste y el nodo que se expande en el momento. ¿Cuándo no es conveniente? Este método puede quedarse expandiendo siempre un nodo de una rama muy larga o infinita Por esto, no es completo ni óptimo, y sólo se recomienda para árboles de búsqueda muy profundos o infinitos. Básicamente sigue siendo un DFS, sólo que tiene un límite de profundidad de una expansión. Con esta modificación, la estrategia se vuelve completa pero no óptima, puesto que si el límite es muy pequeño, es posible que haya soluciones más allá de dicho límite. Uniform Cost Search Esta estrategia implementa lo mejor de BFS y DFS. Es óptimo y completo, como BFS,
pero requiere sólo la memoria de DFS A pesar de que parezca ineficiente, expande sólo 11% más nodos que
un BFS a una profundidad d. En general, IDS es la estrategia preferida cuando hay un gran espacio de búsqueda y se desconoce la profundidad de la solución. Desventajas: En ciertas ocasiones, calcular los predecesores puede ser muy complicado.

Si sólo se sabe que hay varias soluciones y no cuáles son éstas, no hay manera de generar estados objetivo a partir de los cuales construir los antecesores.

Debe haber una manera eficiente de buscar si los nodos del árbol de solución ya están en el primero.

Se debe utilizar algún otro método de búsqueda en cada uno de los árboles. Ventajas: Se encontrará la solución en O(b^(d/2)) Complejidad de espacio: O(b^(d/2)) espacios en memoria. Mejorando la eficiencia de las estrategias: No generar ningún estado ya expandido (Hash table)

No crear caminos con ciclos -> No generar sucesores de nodos que sean también ancestros del mismo nodo.

No regresar al mismo nodo -> No generar sucesores de nodos que sean el mismo nodo. Conclusiones ARBOLES En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Característica importante:

Cada nodo sólo puede ser apuntado
por otro nodo, es decir, cada nodo sólo
tendrá un padre.

Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el
nodo que usaremos para referirnos al árbol.
En el ejemplo, ese nodo es el 'A'. Nodo hoja: nodo
que no tiene hijos. En el ejemplo
hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Nodo rama: aunque esta definición apenas la
usaremos, estos son los nodos que no
pertenecen a ninguna de las dos categorías
anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'. CARACTERÍSTICAS Orden: es el número potencial de hijos que
puede tener cada elemento de árbol.
De este modo, diremos que
un árbol en el que cada nodo puede apuntar
a otros dos es de orden dos, si puede apuntar
a tres será de orden tres, etc. CARACTERÍSTICAS Grado: el número de hijos que tiene
el elemento con más hijos dentro del
árbol. En el árbol del ejemplo, el grado
es tres, ya que tanto 'A' como 'D' tienen
tres hijos, y no existen elementos con más
de tres hijos. Nivel: se define para cada elemento del
árbol como la distancia a la raíz, medida en
nodos. El nivel de la raíz es cero y el de sus
hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. Altura: la altura de un árbol
se define como el nivel del nodo de mayor nivel.
Como cada nodo de un árbol puede considerarse
a su vez como la raíz de un árbol, también
podemos hablar de altura de ramas. El árbol del ejemplo tiene
altura 3, la rama 'B' tiene altura 2,
la rama 'G' tiene altura 1, la 'H' cero, etc Con esta técnica se pretende visitar
los nodos de un árbol, por niveles: primero
los del nivel 1, luegos los del nivel 2, luegos
los del 3, y así sucesivamente. Búsqueda por Amplitud En el siguiente ejemplo, los nodos se visitarían en el siguiente orden:
A, C, B, D, G, H, F, E, J, I. Búsqueda por Amplitud Búsqueda por Amplitud Si hay solución, es seguro que se encontrará mediante la búsqueda preferente por amplitud.
Si son varias soluciones, siempre encontrará primero el estado de meta más próximo (menos profundidad, más a la izquierda).
La búsqueda preferente por amplitud es completa y óptima siempre y cuando el costo de ruta sea una función que no disminuya al aumentar la profundidad del nodo.
Búsqueda por Amplitud Ing. Jorge Saavedra
Full transcript