Búsquedas en grafos#
Introducción#
¿Qué es un recorrido?
Es un procedimiento sistemático de exploración de un grafo mediante la visita a todos sus vértices y aristas.
¿Cuándo un recorrido es eficiente?
Un recorrido es eficiente si visita todos los vértices y aristas en un tiempo proporcional a su número, es decir, en tiempo lineal.
¿Cuál es el interés de las búsquedas en grafos?
Permiten realizar recorridos parciales en grafos infinitos o tan grandes que resultan inmanejables.
Facilitan buscar un elemento en un grafo a partir de un vértice de origen.
Tipos de búsquedas en grafos#
Búsqueda ciega o sin información
No utiliza información sobre el problema.
Normalmente, se realiza una búsqueda exhaustiva.
Búsqueda heurística
Utiliza información sobre el problema, como: costos, distancias o pesos.
Se posee información valiosa que orienta la búsqueda.
¿En qué consiste una búsqueda ciega?
La búsqueda consiste en escoger uno de los nodos posibles.
Si hay varios nodos que se pueden expandir, la elección de cuál se expande primero se hace según una estrategia de búsqueda.
El proceso de búsqueda se concibe como la construcción de un recorrido del grafo.
Las técnicas se diferencian en el orden en que expanden los nodos.
Estrategias de búsqueda#
Por extensión o amplitud (Breadth-First Search)
Se visitan primero el origen y luego todos sus vecinos directos, antes de avanzar a niveles más profundos.
Por profundidad (Depth-First Search)
Se expande un nodo hasta que no se pueda más y luego se regresa para explorar otras ramas.