Búsqueda por Amplitud – Presentations – Ventajas y desventajas

View Github Repository Open presentation in a new window

jorgelipa

See all presentation from jorgelipa

Búsqueda por Amplitud – Presentations – Ventajas y desventajas

1 0

pst-busqueda-amplitud

Presentacion de la busqueda por amplitud

On Github jorgelipa / pst-busqueda-amplitud

Búsqueda por Amplitud

Presentations

Integrantes:Cespedes Alcocer Cristian Lipa Challapa JorgeRamirez Iriarte Elvis R.Lopez Choque Franz A.

Conceptos para entender la búsqueda en árboles y grafos

Para entender los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

Qué es búsqueda ?

Es un método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente. En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

Estructuras de datos para la búsqueda de camino

En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

Búsqueda por amplitud (Breadth-First search BFS)

La búsqueda por amplitud es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles).

Complejidad computacional La cantidad mínima de nodos a ser expandidos para garantizar la mejor solución es la misma que en la búsqueda en anchura, es decir: La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.

Ventajas y desventajas

ventajas

Expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un roblema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede evolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.

desventajas

Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los querimientos y se vuelvan inaceptables y que además requiere de mucha memoria.Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante.Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.

Pseudocódigo para grafos

					DFS(grafo G)
					  PARA CADA vertice u ∈ V[G] HACER
					        estado[u] ← NO_VISITADO
					        padre[u] ← NULO
					        tiempo ← 0
					  PARA CADA vertice u ∈ V[G] HACER
					        SI estado[u] = NO_VISITADO ENTONCES
					        DFS_Visitar(u,tiempo)
					  DFS_Visitar(nodo u, int tiempo)
						    estado[u] ← VISITADO
					    	tiempo ← tiempo + 1
					     	d[u] ← tiempo
					     	PARA CADA v ∈ Vecinos[u] HACER
					        SI estado[v] = NO_VISITADO ENTONCES
					                padre[v] ← u
					                DFS_Visitar(v,tiempo)
					    estado[u] ← TERMINADO
					    tiempo ← tiempo + 1
					    f[u] ← tiempo

En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado ecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.Si las aristas tienen pesos negativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos versiones.

THE END

Gracias