Trabajo de optimizaciòn no lineal

Método De Búsqueda
Métodos Elementales de Búsqueda
Búsqueda Secuencial: Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeño (hasta aproximadamente 500 elementos). Consiste en:
1) Almacenar todos los registros en un arreglo o lista,
2) Insertar cada registro al final del arreglo o lista, y
3) Recorrer o iterar sobre el arreglo o lista hastaconseguir el elemento requerido.
Propiedad 1: La búsqueda secuencial (implementadas empleando arreglos) siempre utiliza N comparaciones para una búsqueda sin éxito y alrededor N/2 comparaciones (en termino medio) para una búsqueda con éxito.
Lo primero es obvio. Por otra parte, si suponemos que todos los registros tienen la misma probabilidad de ser buscados, el número medio de comparacionespara una búsqueda exitosa es:

Propiedad 2: Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz.
Búsqueda Binaria: Si el conjunto de registro es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y viceversa:
1) Se divide el registro en 2 partes
2) Se determina la partedebe contener la clave buscada
3) Se repite el proceso en esa parte
Una forma razonable de dividir el conjunto de registro es mantener los registros ordenados y después utilizar los índices del arreglo ordenado para determinar la parte del arreglo sobre la que se va a trabajar.
|
Ilustración de la búsqueda binaria. |
Propiedad 3: La búsqueda binaria nunca utiliza más de lg N+1comparaciones para cada búsqueda (con éxito o sin él).
Búsqueda por Interpolación: Consiste en tratar de acertar en qué parte del intervalo está la clave que se esta buscando en lugar de ciegamente dividir el arreglo a la mitad. Para ello se utiliza la siguiente fórmula:
x = izq + key-a[izq].key)*(der-izq)/(a[der].key-a[izq].key)
Si aplicamos la búsqueda por interpolación al ejemplo de la Figurael elemento se obtiene en un sólo paso ya que:
| | |   |
| | |   |
| | |   |
| | |   |
Propiedad 4: La búsqueda por interpolación utiliza menos de lglgN+1comparaciones tanto para una búsqueda con éxito como para una búsqueda infructuosa en archivos con claves aleatorias.
Nótese que este método:
1) Depende fuertemente de que las claves estén bien distribuidas en elintervalo. Esta técnica puede ser “engañada” una distribución no uniforme (lo que es frecuente en la práctica).
2) Los cálculos requeridos no merecen la pena si N es pequeño (lgN ≈ lglgN).
3) Debe tenerse en cuenta cuando el arreglo es grande y las comparaciones entre claves son costosas.
Búsqueda por Árbol Binario: Es un método simple y eficaz que constituye un algoritmo fundamental de lainformática.
La propiedad que hace que un árbol binario sea un árbol binario de búsqueda es la siguiente:
Sea x un nodo de un árbol binario, entonces los valores de todos los elementos en su subárbol izquierdo son menores que x y los elementos en el subárbol derecho son elementos mayores que o iguales a x.
Buscar: Esta operación retorna el elemento buscado o nulo en caso de que falle labúsqueda.
Para encontrar un elemento con una clave dada se aplican los siguientes pasos de forma recursiva:
1) Se compara la clave con la raíz.
2) Si es más pequeña se va al subárbol izquierdo.
3) Si es mayor se va al subárbol derecho.
4) Si es igual se detiene la búsqueda.
Insertar: Para insertar un nodo en el árbol típicamente se efectúa una búsqueda infructuosa de su clave ya continuación se agrega el nuevo nodo en el lugar del nodo externo (z ó null) donde terminó la búsqueda.
Propiedad 5: El tiempo de ejecución de las operaciones de búsqueda e inserción depende mucho de la forma del árbol binario de búsqueda. Una búsqueda o inserción en un árbol binario de búsqueda requiere alrededor de 2lgN comparaciones, por término medio, en un árbol construido a partir de...