algoritmos de busqueda
TRANSCRIPT
ALGORITMOS DE BUSQUEDA Y
ORDENAMIENTO Análisis de algoritmos
Búsqueda de Información
Se asocia comúnmente con tablas de consultas.
Ejemplo:
Lista de estudiantes y sus notas.
Funcionarios y sus remuneraciones,
Animales y sus características, etc.
Es lógico entonces que resulte necesario realizar una búsqueda de un
“elemento en particular” dentro de una lista.
Es por ello que se han creado métodos y algoritmos
que permiten realizar una búsqueda eficiente.
Definición Formal de Búsqueda
La operación de búsqueda de un elemento “X”
en un conjunto de elementos consiste en:
1. Determinar si “X” pertenece al conjunto
y en ese caso, indicar su posición dentro de él.
2. Determinar si “X” no pertenece al conjunto.
Los Métodos más usuales de Búsqueda son:
1) Búsqueda secuencial o Lineal
2) Búsqueda Binaria
3) Búsqueda por Transformación de Claves (hash)
Internas
Externas
Estructura
de Datos
- Vectores
- Matriz Estáticas
Dinámicas
Bases de
Datos
Archivos
Lineales
No Lineales
- Pilas
- Listas
- Colas
- Árboles
- Grafos
¿ Cómo se estructuran los datos ?
TIPOS DE BUSQUEDA
• Búsqueda Lineal
• Búsqueda Binaria
• Búsqueda por transformación de
Claves(Hashing)
• Búsqueda en Textos
• Arboles de búsqueda.
BUSQUEDA LINEAL
Corresponde al método de búsqueda de un elemento dentro de un vector; es sencillo,
debido a que se explora secuencialmente el vector. Recorre el vector desde el primer
elemento hasta el último.
Si encuentra el elemento se lee el mensaje: “EXISTE EL ELEMENTO”
se le puede hasta entregar la posición del elemento(índice) y por lo tanto ha finalizado
el proceso de búsqueda.
En caso contrario el mensaje es: “EL ELEMENTO NO EXISTE”
La búsqueda secuencial compara cada elemento del vector con el
valor deseado, hasta que este se encuentre o termina de leer el
vector completo, lo que implica que no existe
Esta búsqueda no requiere ningún requisito por parte del vector,
por consiguiente no requiere que el vector este ordenado.
BUSQUEDA LINEAL
• El mejor caso(la situación óptima), es que el
registro a buscar sea el primero en ser
examinado.
• El peor caso, es cuando las claves de todos
los registros son comparados con k(el dato a
buscar)
• Caso promedio n/2 comparaciones.
BUSQUEDA BINARIA El presente método utiliza el concepto (método), DIVIDE Y VENCERAS,
para localizar el elemento.
E l e m e n t o a
buscar es m ás
p e q u e ñ o q u e
Central , por lo
tanto la búsqueda
se retoma por el
s u b v e c t o r
izquierdo
Con este método se examina primero
el elemento central de la lista;
si éste es el elemento buscado,
entonces la búsqueda ha terminado.
En caso contrario, se determina si
el elemento buscado está en la primera
o la segunda mitad de la lista y
a continuación se repite este proceso,
utilizando el elemento central de la sublista.
Este método requiere que el vector
donde se va a buscar el elemento
se encuentre en un orden determinado
8 ELEMENTO A BUSCAR
8
4 6 8
8
8
BUSQUEDA BINARIA CON EXITO
I (izquierdo) D(Derecho)
4 6 8 10 12 14 16
Central
I(inferior) D(Derecho)
4 6 8 10 12 14 16
Central
11ELEMENTO A BUSCAR
E l e m e n t o a
buscar es mayor
que Central , por
l o t a n t o l a
b ú s q u e d a s e
r e t o m a p o r e l
s u b v e c t o r
derecho
11
12 14 16
I C D
11
12 I, C, D
BUSQUEDA BINARIA SIN EXITO
BUSQUEDA BINARIA
• En la búsqueda binaria se reduce
sucesivamente la operación eliminando
repetidas veces la mitad de la lista restante.
• Para realizar una búsqueda Binaria la lista
debe estar ordenada de acuerdo al valor de la
clave.
• Se puede aplicar en listas lineales como en
Arboles Binarios de Búsqueda
• Se debe conocer el número de registros.
BUSQUEDA BINARIA
• El esfuerzo máximo para este algoritmo es
log2n
• El mínimo esfuerzo es 1
• El promedio1/2log2n
•
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define fila 5
void busqueda_binaria(int vec[fila]);
void main()
{
int vec[fila];
int i,j,x;
clrscr();
for(i=0; i<5 ;i++) //Ingreso de los datos al vector
{
printf("\nIngrese el elemento %d:",i);
scanf("%d",&vec[i]);
}
busqueda_binaria(vec);
for (i=0 ;i<fila; i++){
printf("\n el elemento %d del vector es %d
",i,vec[i]);}
}
PROGRAMA DE BUSQUEDA BINARIA
PROGRAMA DE BUSQUEDA BINARIA
void busqueda_bianria(int vect[fila])
{
int alto, bajo, centro;
int j,valor,v;
printf("\nProceso de Busqueda\n");
printf("\nIngrese el elemento a buscar");
scanf("%d",&valor);
alto=4; bajo=0;
centro=(bajo + alto)/2;
printf("el indice centro es:%d",centro);
while(bajo <= alto && (vect[centro] != valor))
{
if(valor < vect[centro])
alto = centro - 1;
else
bajo = centro + 1;
centro=(bajo+alto)/2;
}
if (valor == vect[centro])
printf("el elemento no existe");
else
printf("el elemento existe");
}
BUSQUEDA MEDIANTE
TRANSFORMACIÓN DE CLAVES (HASHING)
Los elementos o registros del campo clave no es necesario que estén ordenados de
acuerdo a los valores del campo clave, como se requiere en la búsqueda binaria.
Dada una clave k:
El primer paso en la operación de búsqueda es calcular su índice asociado d<--H(k).
El segundo paso necesario es verificar si el elemento con la clave k es identificado
verdaderamente por h en el vector T.
Existe una función de transformación de clave, H(k)
que convierte (k) en una dirección (d).
La función H es la función de paso o conversión de múltiples claves a direcciones.
• Si una empresa tiene 100 empleados , y si a cada empleado se le asigna un código
como número de identificación de 1 a 100, evidentemente puede existir una
correspondencia directa entre la clave y la dirección definida en un vector de 100
elementos.
• En otro caso si la empresa tiene 80.000 empleados ya no se puede utilizar la
relación entre la clave y la dirección.
BUSQUEDA MEDIANTE
TRANSFORMACIÓN DE CLAVES (HASHING)
Este método consiste en la transformación de claves
(dadas numéricas o alfanuméricas) en una dirección (índice) dentro del vector.
La correspondencia entre las claves y la dirección en el vector se establece por una
dirección definida de conversión (función hash)
METODOS DE TRANSFORMACION DE
CLAVES
Existen numerosos métodos de transformación de claves:
TRUNCAMIENTO
PLEGAMIENTO
ARITMETICA MODULAR
MITAD DEL CUADRADO
345678125
FUNCION DE
CONVERSION
DE CLAVES
[0]
[1]
[J]
[98]
[99]
TABLA DE TRANSFORMACION DE CLAVES
CLAVE=45126034
CLAVE=345678125
CLAVE=4515896
CLAVE=5689235
Ignora parte de la clave y se utiliza la parte restante
directamente como índice (considerando campos no
numéricos y sus códigos numéricos.
TRUNCAMIENTO
Ejemplo:
Se tiene claves de tipo entero de 8 dígitos y para la tabla
de transformación tiene mil posiciones, entonces para la
dirección(índice) se considera: el primer, segundo y quinto
dígito de derecha forman la función de conversión.
clave:72588495 --> h(clave)=728
PLEGAMIENTO
Esta técnica consiste en la partición de la clave en
diferentes partes y la combinación de las partes en un
modo conveniente (a menudo utilizando suma o
multiplicación) para obtener el índice.
La clave x se divide en varias partes x1, x2, x3,....xn,
donde cada parte (con la única posibilidad de
excepción de la última parte, tiene el mismo número
de dígitos que la dirección especificada)
H(x)= x1 + x2 + x3 +...+ xn
Ejemplo 1:
Un entero de 8 dígitos se puede dividir en grupos de
tres(3), tres(3) y dos(2) dígitos, los grupos se suman y
se truncan si es necesario para que estén en el rango
adecuado de índices.
Se considera la clave 62538194
y el número de direcciones es 100:
H(clave)=625 + 381 + 94 =1100 se trunca
H(clave)=100
Ejemplo 2:
El número de identificación de los empleados es el
campo clave de una empresa y consta de cuatro
dígitos y las direcciones reales son 100. Se desea
calcular las direcciones correspondientes por el
método de plegamiento.
Claves: 4205, 3355, 8148
H(4205) = 42 + 05 = 47
H(3355) = 33 + 55 = 88
H(8148) = 81 + 48 = 129 --> 129-100 =29
Este método convierte la clave a un entero, se divide por el tamaño del rango del índice y toma el resto como resultado. La función que se utiliza es el MOD(módulo o resto de la división entera).
H(x)= x MOD m
Donde m es el tamaño del arreglo. La mejor elección de los módulos son los números primos.
ARITMETICA MODULAR
Un vector T tiene cien posiciones (0..100). Se tiene que las claves de
búsqueda de los elementos de la tabla son enteros positivos.
La función de conversión H debe tomar un número arbitrario entero
positivo x y convertirlo en un entero en el rango de (0..100)
H(x)= x MOD m
Si clave=234661234 MOD 101 = 56
234661234 MOD 101 = 56
Este método consiste en calcular el cuadrado de la clave x.
La función de conversión se define como:
H(x)=c
Donde c se obtiene eliminando dígitos a ambos lados de x2.
MITAD DEL CUADRADO
Ejemplo:
Una empresa tiene ochenta empleados y cada uno de ellos tiene un número de identificación de cuatro dígitos y el conjunto de direcciones de memoria varía en el rango de 0 a 100. Se pide calcular las direcciones que se obtendrán al aplicar la función de conversión por la mitad del cuadrado de los números empleados:
x --> 4205 7148 3350
x2 --> 17682025 51093904 11222500
Por lo tanto H(x) =82 93 22
COLISIONES
La función de conversión H(x) no siempre proporciona valores distintos puede suceder que para dos claves diferentes x1 y x2 se obtiene la misma índice(dirección). Se deben encontrar métodos para dar solución a las colisiones que se pueden presentar.
Ejemplo de Colisión:
•H(123445678) = 123445678 MOD 101 = 44
•H(123445880) = 123445880 MOD 101 =44
Para dos claves distintas 123445678 y 123445880; al aplicar la función H la dirección es 44, por lo tanto ha ocurrido una colisión.
RESOLUCION DE COLISIONES
La función de conversión H(x) no siempre proporciona valores distintos puede suceder que para dos claves diferentes x1 y x2 se obtiene la misma índice(dirección).
Se deben encontrar métodos para dar solución a las colisiones que se pueden presentar.
Un método comúnmente utilizado para resolver una colisión es cambiar la estructura del arreglo de modo que pueda alojar más de un elemento en la misma posición. De modo que cada posición i del vector sea por si mismo un vector capaz de contener N elementos.
El problema que se presenta, es como saber el tamaño de N. Si N es muy pequeño, el problema de las colisiones aparecerá cuando aparezcan N + 1 elementos.
...
...
...
...
0
1
2
3
H-1
Encadenamiento
RESOLUCION DE COLISIONES
Otra solución corresponde a utilizar una lista enlazada o encadenada de elementos
para formar a partir de cada posición del arreglo. Cada entrada i del vector es un
puntero que apunta al elemento del principio de la lista de elementos.
La función de transformación de la clave lo convierte en la posición i.
BUSQUEDA POR
TRANSFORMACION DE CLAVES
• Este método permite hacer una búsqueda directa.
• La idea básica corresponde a aplicar una función
que traduce un conjunto de posibles valores claves
en un rango de direcciones relativas.
• El problema que se presenta corresponde a las
colisiones.
Sea clave1<>clave2=>f(clave1)=f(clave2)
• A dos claves distintas les corresponde la misma
dirección, se les denomina sinónimos
• Ventajas:
– Se pueden usar los valores naturales de las
claves.
– Se logra la independencia lógica y física, debido
a que los valores de las claves son independientes
de las direcciones.
– No se requiere espacio adicional para los índices.
• Desventajas:
– No se pueden utilizar registros de longitud
variable.
– No permite claves repetidas.
– Solo permite acceso por una clave.
FUNCIONES HASHING
• Residuo de la División:
– H(k)=k mod m, donde m es un número primo
no muy cercano a una potencia de 2
• Método de la Multiplicación:
– H(k)= en donde 0<A<1, m
se utiliza como un valor potencia de 2, para
facilitar el cálculo computacional de la función.
1modkAm
FUNCIONES HASHING
• Por medio del Cuadrado:
– La clave es elevada al cuadrado, luego unos
dígitos específicos son extraidos de la mitad del
resultado, para constituir la dirección relativa.
Si se desea una dirección de n dígitos entonces
se trunca en los extremos, tomando los n
dígitos.(potencia de 10)
• Por Pliege:
– La clave es particionada en varias partes, cada
una de las cuales tienen el mismo tamaño
excepto la última, son plegadas y
posteriormente sumadas(potencia de 10)
METODOS PARA RESOLVER LAS
COLISIONES
• Area de Desborde: La dirección para k2 se encuentra fuera
del área principal, área especial donde se almacenan los
registros que no pueden ser almacenados en el área principal.
• Sondeo Lineal:Búsqueda secuencial desde la dirección de
origen hasta encontrar la siguiente dirección vacía.
• Doble Hashing: Se aplica una segunda hash a la clave.
• Encadenamiento de Sinònimos: Mantener una lista ligada de
registros.
• Direccionamiento por Cubetas: Asignación de bloques de
espacios.
BUSQUEDA EN TEXTO
• Consiste en la búsqueda de una
palabra(patrón) dentro de un texto.
• Se considera las siguientes convenciones:
– Sea n el tamaño del texto a donde se realizará la
búsqueda.
– Texto=a1,a2,a3,...an
– Patrón=b1,b2,b3,...bm
Ejemplo
Texto=Análisis de Algoritmos
Patrón=algo
n=22 ; m=4
ALGORITMO DE FUERZA BRUTA
• Se alinea la primera posición del patrón con la
primera posición del texto, y se comparan los
caracteres hasta finalizar el patrón; se encontró
una ocurrencia del patrón en el texto o hasta que
se encuentra una discrepancia. Si se detiene el
algoritmo por una discrepancia, se desliza el
patrón en una posición hacia la derecha y se
intenta de nuevo
• En el peor de los casos realiza O(m-n)
comparaciones de caracteres
ALGORITMO BOYER-MOORE
• La comparación se realiza de derecha a izquierda.
• Si hay una discrepancia en el último carácter del
patrón y el carácter del texto no aparece en todo el
patrón, entonces este se puede deslizar m
posiciones, sin realizar ninguna comparación extra
• No fue necesario hacer m-1 comparaciones, lo
cual se puede hacer una búsqueda con menos n
comparaciones.