Busquedas (BFS, DFS)

METODOLOGÍAS DE BÚSQUEDAChristian Antonio Martínez SolísBúsqueda SecuencialSe utiliza comúnmente cuando el contenido de la colección de datos no se encuentra ordenado ó cuando no puede ser ordenadoSe busca el elemento secuencialmente y se devuelve en el momento en el que se encuentreSi se recorren todos los elementos y no hubo coincidencia entonces se devuelve nulo ó -1 Búsquedas 05/03/2010 2Búsqueda BinariaUtiliza la técnica divide y vencerásTrabaja comúnmente sobre colecciones o estructuras de datos ordenadas (puede usarse aunque no estén ordenadas)Cuando se trabaja con datos ordenados la búsqueda se reduce mínimo en un 50% en la cantidad de comparaciones para buscar el elemento Búsquedas 05/03/2010 3Búsqueda Binaria -Ejemplo Búsquedas 05/03/2010 4 Se busca el 2246781522302467242Breadth-FirstSearchEs uno de los algoritmos más simples para buscar en un grafoSe utiliza como apoyo a varios algoritmos que solucionan problemasDijkstraPrimDado un grafo G = (V, E)y un vértice s, busca sistemáticamente explorando las aristas de Gpara “descubrir” cada vértice que es alcanzado por s Búsquedas 05/03/2010 5Breadth-FirstSearchLleva computacionalmente la distancia (número más pequeño de aristas) desde spara cada vértice alcanzableTambién produce un “árbol breadth-fist” con raíz s que contiene todos los vértices alcanzablesPara cada vértice valcanzable desde s, la ruta en el árbol breadth-firstde sa vcorresponde a la “ruta más pequeña” de sa ven G, que es, una ruta que contiene el número más pequeño de aristas Búsquedas 05/03/2010 6Breadth-FirstSearchEste algoritmo es muy nombrado porque expande uniformemente la frontera entre los vértices descubiertos y no descubiertos a través de la anchura de la fronteraEl algoritmo descubre todos los vértices de distancia ka sdescubriendo cualquier vértice a la distancia k + 1Para mantener un historial del progreso, la búsqueda breadth-firstcolorea cada vértice en blanco, gris o negro Búsquedas 05/03/2010 7Breadth-FirstSearchTodos los vértices inician en blanco y pueden convertirse en grises o negros en el futuroUn vértice que es descubiertola primera vez es encontrado durante la búsqueda, y en ese tiempo se convierte a un color no blancoLos vértices grises o negros, por lo tanto, han sido descubiertos, pero la búsqueda breadth-firsthace una distinción entre ellos para asegurar que la búsqueda se guíe en forma de anchura Búsquedas 05/03/2010 8Breadth-FirstSearchSi (u, v) Ey el vértice ves negro, entonces el vértice ues gris o negro; esto es, todos los vértices adyacentes a los vértices negros han sido descubiertosLos vértices grises pueden tener vértices blancos adyacentes; ellos representan la frontera entre los vértices descubiertos y los no descubiertos Búsquedas 05/03/2010 9 ∈Breadth-FirstSearch-Ejemplo Búsquedas 05/03/2010 10 ∞∞∞∞∞∞∞∞1∞0∞∞∞∞∞∞210∞∞∞1∞∞3102∞∞12∞4s0Qwr1Q1NULLQrtx1Q2r s t uv w x yr s t uv w x yr s t uv w x yr s t uv w x y2Breadth-FirstSearch-Ejemplo Búsquedas 05/03/2010 11 102∞212∞5txv2Q2r s t uv w x y21023212∞6xvu2Q2r s t uv w x y3102321237vuy2Q2r s t uv w x y3102321238uy3Q3r s t uv w x yBreadth-FirstSearch-Ejemplo Búsquedas 05/03/2010 12 102321239y3Qr s t uv w x y1023212310r s t uv w x yNULLQDepth-FirstSearchLa estrategia de este algoritmo es buscar por “profundidad” en el grafo tanto como sea posibleEn este algoritmo, las aristas son exploradas fuera del vértice vdescubierto más recientemente que aún no ha explorado las aristas que lo abandonanCuando todas las aristas de vhan sido exploradas, la búsqueda hace una retrospección (backtrack) para explorar las aristas que abandonan el vértice que han sido descubiertas desde vBúsquedas 05/03/2010 13Depth-FirstSearchEste proceso continúa hasta que se han descubierto todos los vértices alcanzables desde el vértice originalSi existen vértices que no se hayan descubierto, entonces uno de ellos es seleccionado como nuevo vértice y la búsqueda se repite a partir de élEste proceso se repite hasta que todos los vértices se han descubierto Búsquedas 05/03/2010 14Depth-FirstSearchAsí como en la búsqueda por anchura, cuando un vértice ves descubierto al escanear la lista de adyacencia de un vértice uya descubierto, la búsqueda por profundidad guarda este evento modificando el predecesor de va uA diferencia de la búsqueda por anchura, donde el subgrafopredecesor forma un árbol, el subgrafopredecesor producido por la búsqueda por profundidad puede ser compuesto por varios árboles, porque la búsqueda puede repetirse desde múltiples vértices Búsquedas 05/03/2010 15Depth-FirstSearchEl subgrafopredecesor de una búsqueda por profundidad es entonces definido de distinta manera que en la búsqueda por anchuraEl subgrafopredecesor forma un “bosque depth-first” compuesto de varios “árboles depth-first”Estos árboles se llaman árboles aristaComo en la búsqueda por anchura, los vértices se colorean para indicar el estado Búsquedas 05/03/2010 16Depth-FirstSearchCada vértice es inicialmente blanco, es gris cuando ha sido descubierto en la búsqueda, y es coloreado en negro cuando ha finalizado, esto es, cuando su lista de adyacencia ha sido examinada completamenteEsta técnica garantiza que cada vértice termine exactamente en un árbol depth-first, de manera que los árboles son disjuntos Búsquedas 05/03/2010 17Depth-FirstSearch-Ejemplo Búsquedas 05/03/2010 18 1u v wx y z2u v w1/x y z3u v w1/2/x y z4u v w1/2/3/x y zDepth-FirstSearch-Ejemplo Búsquedas 05/03/2010 19 5u v w1/2/4/3/x y z6u v w1/2/4/3/x y z7u v w1/2/4/53/x y z8u v w1/2/4/53/6x y zDepth-FirstSearch-Ejemplo Búsquedas 05/03/2010 20 9u v w1/2/74/53/6x y z10u v w1/2/74/53/6x y z11u v w1/82/74/53/6x y z12u v w1/82/79/4/53/6x y zDepth-FirstSearch-Ejemplo Búsquedas 05/03/2010 21 13u v w1/82/79/4/53/6x y z14u v w1/82/79/4/53/610/x y z15u v w1/82/79/4/53/610/x y z16u v w1/82/79/4/53/610/11x y zDepth-FirstSearch-Ejemplo Búsquedas 05/03/2010 22 17u v w1/82/79/124/53/610/11x y z