Metodos de busqueda PDF

Preview

Summary

Descripción y explicación de los métodos de búsqueda...

Description

18-5-2018

Métodos de búsqueda Estructura de datos

Franky Antonio Reyes ABEL MARIÑELARENA PEREZ

Búsqueda binaria La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una. Usamos la búsqueda binaria en el juego de adivinar en la lección introductoria. Una de las maneras más comunes de usar la búsqueda binaria es para encontrar un elemento en un arreglo. Por ejemplo, el catálogo estelar Tycho-2 contiene información acerca de las 2,539,913 estrellas más brillantes en nuestra galaxia. Supón que quieres buscar en el catálogo una estrella en particular, con base en el nombre de la estrella. Si el programa examinara cada estrella en el catálogo estelar en orden empezando con la primera, un algoritmo llamado búsqueda lineal, la computadora podría, en el peor de los casos, tener que examinar todas las 2,539,913 de estrellas para encontrar la estrella que estás buscando. Si el catálogo estuviera ordenado alfabéticamente por nombres de estrellas, la búsqueda binaria no tendría que examinar más de 22 estrellas, incluso en el peor de los casos. Los siguientes artículos discuten cómo describir cuidadosamente el algoritmo, cómo implementar el algoritmo en JavaScript y cómo analizar su eficiencia.

Pseudocódigo para la búsqueda binaria Al describir un algoritmo para un ser humano, a menudo es suficiente una descripción incompleta. Algunos detalles pueden quedar fuera de una receta de un pastel; la receta supone que sabes cómo abrir el refrigerador para sacar los huevos y que sabes cómo romper los huevos. La gente puede saber intuitivamente cómo completar los detalles faltantes, pero los programas de computadora no. Es por eso que necesitamos describir completamente los algoritmos computacionales. Para poder implementar un algoritmo en un lenguaje de programación, necesitarás entender un algoritmo hasta sus últimos detalles. ¿Cuáles son las entradas del problema? ¿Las salidas? ¿Qué variables deben crearse, y qué valores iniciales deben tener? ¿Qué pasos intermedios deben tomarse para calcular otros valores y calcular en última instancia la salida? ¿Estos pasos repiten instrucciones que se pueden escribir en forma simplificada al usar un bucle? Veamos cómo describir cuidadosamente la búsqueda binaria. La idea principal de la búsqueda binaria es llevar un registro del rango actual de intentos razonables. Digamos que estoy pensando en un número entre uno y 100, justo como en el juego de adivinar. Si ya intentaste decir 25 y te dije que mi número es más grande, y ya intentaste decir 81 y te dije que mi número es más chico, entonces los números en el rango de 26 a 80 son los únicos intentos razonables. Aquí, la sección roja de la recta numérica contiene los intentos razonables, y la sección negra muestra los intentos que hemos descartado:

En cada turno, haces un intento que divide el conjunto de intentos razonables en dos rangos de aproximadamente el mismo tamaño. Si tu intento no es correcto, entonces te digo si es muy alto o

muy bajo, y puedes eliminar aproximadamente la mitad de los intentos razonables. Por ejemplo, si el rango actual de los intentos razonables es de 26 a 80, intentarías adivinar a la mitad del camino, (26 + 80) / 2(26+80)/2left parenthesis, 26, plus, 80, right parenthesis, slash, 2, o 53. Si después te digo que 53 es demasiado alto, puedes eliminar todos los números de 53 a 80, dejando 26 a 52 como el nuevo rango de intentos razonables, reduciendo a la mitad el tamaño del rango.

Para el juego de adivinar, podemos llevar un registro del conjunto de intentos razonables al usar unas cuantas variables. Sea la variable minminm, i, n el intento razonable mínimo actual para esta ronda, y sea la variable maxmaxm, a, x el intento razonable máximo actual. La entrada (o input en inglés) al problema es el número nnn, el mayor número posible que tu oponente está pensando. Suponemos que el menor número posible es uno, pero sería fácil modificar el algoritmo para tener el menor número posible como una segunda entrada. Aquí está una descripción en pseudocódigo de la búsqueda binaria: Sea min = 1min=1m, i, n, equals, 1 y max = nmax=nm, a, x, equals, n. Adivina el promedio de maxmaxm, a, x y minminm, i, n, redondeado hacia abajo de modo que sea un entero. Si adivinaste el número, detente. ¡Lo encontraste! Si el intento fue demasiado bajo, haz que minminm, i, n sea uno más grande que el intento. Si el intento fue demasiado alto, haz que maxmaxm, a, x sea uno menos que el intento. Regresa al paso dos. Podríamos hacer este pseudocódigo todavía más preciso al describir claramente las entradas y las salidas para el algoritmo, y al aclarar lo que entendemos por instrucciones como "intenta un número" y "detente". Pero por ahora está bien.

Método de Búsqueda Secuencial La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave. Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones. Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Mejoras en la eficiencia de la búsqueda secuencial 1) Muestreo de acceso Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas. 2) Movimiento hacia el frente Este esquema consiste en que las listas de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el. 3) Transposición Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros. Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista. 4) Ordenamiento Una forma de reducir el número de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

EJEMPLO DE BÚSQUEDA SECUENCIAL El siguiente programa cumple con los siguientes requerimientos: Crea un menú de opciones (INSERTAR, CONSULTAR, ELIMINAR Y FINALIZAR). INSERTAR: Almacena el nombre de personas en vectores estáticos tipo String de tamaño 50. CONSULTAR: Utilizando el algoritmo de búsqueda secuencial pide el nombre y si lo encuentra imprime un mensaje de encontrado, en caso contrario un mensaje de no localizado. ELIMINAR: Utilizando el algoritmo de búsqueda secuencial pide el nombre y si lo encuentra imprime un mensaje de encontrado y elimina el nombre ajustando el vector para no dejar espacios en blanco, en caso contrario un mensaje de no localizado. FINALIZAR: Imprime los nombres almacenado y sale del programa.

Búsqueda mediante transformación de claves (hashing) Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash. La correspondencia más sencilla es la identidad, esto es, al número 0 se le asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible. Por ejemplo, se quiere guardar en un arreglo la información de los 1000 usuarios de una empresa, y se elige el número de DNI como elemento identificativo. Es inviable hacer un arreglo de 100.000.000 elementos, sobre todo porque se desaprovecha demasiado espacio. Por eso, se realiza una transformación al número de DNI para que nos dé un número menor, por ejemplo, coger las 3 últimas cifras para guardar a los empleados en un arreglo de 1000 elementos. Para buscar a uno de ellos, bastaría con realizar la transformación a su DNI y ver si está o no en el arreglo. TABLAS HASH Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado. QUE ES UNA FUNCIÓN DE HASH Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales, por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que, si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son. Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite). Son usadas en múltiples aplicaciones, como los arreglos asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas (ver función inyectiva). La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son:

Restas sucesivas: esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Por ejemplo, si el número de expediente de un alumno universitario está formado por el año de entrada en la universidad, seguido de un número identificativo de tres cifras, y suponiendo que entran un máximo de 400 alumnos al año, se le asignarían las claves: 1998-000 --> 0 = 1998000-1998000 1998-001 --> 1 = 1998001-1998000 1998-002 --> 2 = 1998002-1998000 ... 1998-399 --> 399 = 1998399-1998000 1999-000 --> 400 = 1999000-1998000+400 ... yyyy-nnn --> N = yyyynnn-1998000+(400*(yyyy-1998)) Aritmética modular: el índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que cuando hay N+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante. Si el número N es el 13, los números siguientes quedan transformados en: 13000000 --> 0 12345678 --> 7 13602499 --> 1 71140205 --> 6 73062138 --> 6 Mitad del cuadrado: consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión: 123*123=15129 --> 51 136*136=18496 --> 84 730*730=532900 --> 29 301*301=90601 --> 06 625*625=390625 --> 06 Truncamiento: consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 8 cifras se debe ordenar en un arreglo

de 1000 elementos, se pueden coger la primer, la tercer y las últimas cifras para formar un nuevo número: 13000000 --> 100 12345678 --> 138 13602499 --> 169 71140205 --> 715 73162135 --> 715 Plegamiento: consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos los números de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres últimas cifras): 13000000 --> 130=130+000+00 12345678 --> 657=123+456+78 71140205 --> 118 --> 1118=711+402+05 13602499 --> 259=136+024+99 25000009 --> 259=250+000+09 Tratamiento de colisiones: Pero ahora se nos presenta el problema de qué hacer con las colisiones, qué pasa cuando a dos elementos diferentes les corresponde el mismo índice. Pues bien, hay tres posibles soluciones: Cuando el índice correspondiente a un elemento ya está ocupada, se le asigna el primer índice libre a partir de esa posición. Este método es poco eficaz, porque al nuevo elemento se le asigna un índice que podrá estar ocupado por un elemento posterior a él, y la búsqueda se ralentiza, ya que no se sabe la posición exacta del elemento. También se pueden reservar unos cuantos lugares al final del arreglo para alojar a las colisiones. Este método también tiene un problema: ¿Cuánto espacio se debe reservar? Además, sigue la lentitud de búsqueda si el elemento a buscar es una colisión. Lo más efectivo es, en vez de crear un arreglo de número, crear un arreglo de punteros, donde cada puntero señala el principio de una lista enlazada. Así, cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del arreglo, ya que se pueden añadir nodos dinámicamente a la lista... En una "tabla hash", los elementos están formados por una pareja: una clave y un valor, como en un SortedList, pero la diferencia está en la forma en que se manejan internamente estos datos: la "tabla hash" usa una "función de dispersión" para colocar los elementos, de forma que no se pueden recorrer secuencialmente, pero a cambio el acceso a partir de la clave es muy rápido, más

que si hacemos una búsqueda secuencial (como en un arreglo) o binaria (como en un ArrayList ordenado). Un ejemplo de diccionario, parecido al anterior (que es más rápido de consultar para un dato concreto, pero que no se puede recorrer en orden). Si un elemento que se busca no existe, se lanzaría una excepción, por lo que deberíamos controlarlo con un bloque try..catch. Lo mismo ocurre si intentamos introducir un dato que ya existe. Una alternativa a usar try..catch es comprobar si el dato ya existe, con el método "Contains" (o su sinónimo "ContainsKey"). Otras posibilidades son: borrar un elemento ("Remove"), vaciar toda la tabla ("Clear"), o ver si contiene un cierto valor ("ContainsValue", mucho más lento que buscar entre las claves con "Contains"). Una tabla hash tiene una cierta capacidad inicial, que se amplía automáticamente cuando es necesario. Como la tabla hash es mucho más rápida cuando está bastante vacía que cuando está casi llena, podemos usar un constructor alternativo, en el que se le indica la capacidad inicial que queremos. Una tabla Hash es una tabla donde tienes clave, y valor. El código hash es único para cada valor y cada valor sólo tiene un código hash. Ejemplo de una taba hash: clave 1: valor"Nombre" clave 2: valor"Apellido" entonces si tú quieres buscar el nombre, consultas en la tabla por su clave. VENTAJAS E INCONVENIENTES DE LAS TABLAS HASH Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones: Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente). Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones. Los inconvenientes de las tablas hash son: Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa. Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos. Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.

INSERCIÓN Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen a la clave del elemento. El resultado de la función resumen ha de mapearse al espacio de direcciones del arreglo que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla. El elemento se almacena en la posición de la tabla obtenido en el paso anterior. Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar asociando una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos. Las tablas hash se suelen implementar sobre arreglo de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1),[1] sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos. Comparada con otras estructuras de arreglo asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información. Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios autobalancéales son más rápidos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.

Códigos: Búsqueda binaria import java.util.Scanner; public class BusquedaBinaria { public static void BusquedaBinaria(int x, int v[]){ int n=v.length; int c = 0; int i = 0; int j = n-1; int contador=0; boolean bandera=false; while(iv[c]){ i=c+1; } else{ j=c-1; } } contador++; } if(bandera==true){ System.out.println("El elemento esta en la posicion: "+c+" se comparo "+contador); }

else{ System.out.println("El elemento no esta en el arreglo se comparo "+contador); } } Scanner sn = new Scanner(System.in); public static void main(String[] args){ int [] valores = new int[10]; llenararreglo(valores); imprimeArreglo(valores); BusquedaBinaria(5,valores); } public static void llenararreglo(int[] valores){ for (int i=0; i...