Scribd
Cargar
76 vistas1 página

Algoritmos de Búsqueda No Informada

Este documento describe diferentes algoritmos de búsqueda ciega en grafos, incluyendo búsqueda en anchura (BFS), búsqueda de costo uniforme (UCS), búsqueda en profundidad (DFS), búsqueda en profundidad limitada (DLS) e iterativa (IDS), y búsqueda bidireccional. Explica las estructuras de datos utilizadas y cómo cada algoritmo explora el grafo para encontrar un objetivo.

Cargado por

Gissela López
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
76 vistas1 página

Algoritmos de Búsqueda No Informada

Este documento describe diferentes algoritmos de búsqueda ciega en grafos, incluyendo búsqueda en anchura (BFS), búsqueda de costo uniforme (UCS), búsqueda en profundidad (DFS), búsqueda en profundidad limitada (DLS) e iterativa (IDS), y búsqueda bidireccional. Explica las estructuras de datos utilizadas y cómo cada algoritmo explora el grafo para encontrar un objetivo.

Cargado por

Gissela López
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Búsqueda Ciega -> No informada.

Hay que tener en cuenta que se utilizan dos estructuras de datos, una lista de expandidos y otra es
la agenda la cual contiene los estados que se van a visitar

1. Breadth first search (BFS -> Búsqueda primero en anchura): La estructura de datos que se utiliza
es una cola, es decir, el primero que entro es el primero que sale. Lo que se hace en esta búsqueda
en el caso de los grafos es ir agregando los nodos alcanzables por el nodo inicial y así
sucesivamente repetidamente con los otros nodos agregándolos al final de la pila hasta llegar al
nodo objetivo, cuando este último se encuentra se debe ver desde donde provino para así saber
cuál es la ruta más optima, considerando sólo el número de pasos que le toma llegar al objetivo.

2. Búsqueda de costo uniforme (UCS): es una modificación de BFS, se modifica estructura de datos
por una cola de prioridad, el elemento que tiene menor costo es el que se encuentra al frente, el
algoritmo no se detiene cuando encuentra el nodo objetivo, sino que cuando el elemento se
encuentra al frente de la cola de prioridad.

3. Búsqueda en profundidad (DFS Depth First Search): Se utiliza una pila, es decir, el primero que
entra es el último que sale. El algoritmo se detiene cuando se satisface el objetivo o cuando se
acaban los estados por visitar.

4. Búsqueda en profundidad limitada (DLS): Variación del algoritmo DFS, tiene dos modificaciones,
cuenta con un parámetro que es la cota de profundidad y no cuenta con un conjunto de
expandidos, es decir, ya no guarda estos nodos en memoria. Si uno define la cota de profundidad
menor a la profundidad donde se encuentra el nodo objetivo, este no va a encontrar una solución,
por lo tanto, no es un algoritmo completo y tampoco es óptimo en el número de pasos si es que la
cota de profundidad es mayor a la profundidad donde se encuentra el objetivo.

5. Búsqueda en profundidad iterativa (IDS): es una modificación del algoritmo DLS, debido a que si

6. Búsqueda bidireccional:

También podría gustarte