Matematicas Discretas 2

Contenido.

Estratregias y Algoritmo de Busqueda

Definición

Estrategias de búsqueda

• Una estrategia se define eligiendo el ORDEN EN LA EXPANSION DE NODOS - sea donde se insertan los nodos expandidos en la lista o cola

• La evaluación de las estrategias tiene las siguientes dimensiones:

– Completitud - encuentra o nó una solución siendo que existe?

– Complejidad temporal - número de nodos generados/expandidos

– Complejidad espacial - máximo número de nodos en memoria

– Optimalidad - encuentra o nó una solución de mínimo costo?

• Las dos complejidades (temporal y espacial) se miden usando:

– b - factor de ramificación del árbol de búsqueda

– d - profundidad de la solución de mínimo costo

– m - maxima profundidad del espacio de búsqueda (p. ej., ∞)

Algoritmo

La palabra algoritmo se deriva de la traducción al latín de la palabra árabe alkhowarizmi, nombre de un matemático y astrónomo árabe que escribió un tratado sobre manipulación de números y ecuaciones en el siglo IX.

Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema especifico.

Algoritmos de búsqueda.

En muchas situaciones de programación es necesario repetir ciertos procedimientos hasta alcanzar un punto en que no se puede o no se desea continuar. Esta repetición de tareas puede llevarse a cabo básicamente de dos maneras diferentes: la iteración y la recursión. Como se supone que en cada repetición se procesa un estado diferente de cosas -sin lo cual el proceso tendería al infinito-, ambos métodos presentan también alguna forma de control de fin de tarea. La idea básica en un algoritmo iterativo es que la repetición de la tarea se controla desde afuera. Se ejecuta un conjunto de acciones en forma completa, se verifica la condición de salida y si es necesario se vuelve a ejecutar el conjunto de acciones en forma completa. El orden en que se ejecuta y evalúa determina que el algoritmo sea de evaluación previa (primero se evalúa la condición de salida y luego se ejecutan las acciones) o de evaluación posterior (primero se ejecutan las acciones y luego se evalúa el resultado). En ambos casos, sin embargo, el control de las repeticiones es exterior al grupo principal de acciones. En un algoritmo recursivo, en cambio, la tarea se controla desde adentro. Se comienza a ejecutar un conjunto de acciones, pero antes de finalizar se evalúa si se ha llegado a la condición de salida; si no es así, se continúa ordenando una nueva ejecución del mismo conjunto de acciones. Finalmente se concluye con la tarea iniciada. Dicho en otros términos, el procedimiento se llama repetidas veces a sí mismo, y el control de esas llamadas forma parte del grupo principal de acciones. Por otra parte, si bien hay problemas que se resuelven más directamente en forma iterativa y otros que son más naturalmente recursivos, ambas técnicas son compatibles e intercambiables, por lo que todo algoritmo recursivo puede transformarse en iterativo y viceversa.

Algoritmos De Búsqueda

Cuando se trata de buscar un valor en un arreglo ordenado de datos, el algoritmo de búsqueda binaria es el más frecuentemente utilizado. La idea central de este algoritmo es comparar el elemento ubicado en el lugar central del arreglo con el valor buscado. Si el elemento central es igual al valor buscado la búsqueda finaliza con éxito. Si no es así, puede ocurrir o bien que el elemento central sea mayor que el buscado -en cuyo caso el elemento coincidente debe estar en la mitad inferior del arreglo- o bien que sea menor -y el elemento coincidente se encuentra en la mitad superior. En ambos casos se prosigue la búsqueda en la mitad que corresponde, si es que quedan elementos en esa dirección, o bien se finaliza la búsqueda sin éxito, en caso contrario. Existe naturalmente una solución recursiva, ya que si el valor buscado no es hallado en la posición del centro se repite el mismo procedimiento con una de las mitades del arreglo, y así hasta que se encuentre el valor o no queden más "mitades". Compárese esto con el problema de las bolillas dentro de las cajas, en el cual la "bolilla blanca" sería el valor buscado y la "caja interior" sería la mitad que se debe seguir examinando.

En ocasiones es necesario determinar no sólo si el valor buscado se halla en el arreglo, sino además saber en qué posición está (o debería estar, si es que no existe). Por ejemplo, si se desea insertar un nuevo valor en un arreglo ordenado, una solución eficaz es "buscar" el valor en el arreglo (aunque se sepa de antemano que no se encuentra) para determinar la posición correcta en la que debe ser insertado. En esos casos se debe informar por algún medio (generalmente un puntero pasado como parámetro o una variable global) cuál es la posición lógica del elemento buscado dentro del arreglo.

Ejemplo de un Algoritmo de Búsqueda

A modo de ejemplo se presenta una versión de la función int busbin (int *vec, unsigned tam, int val, unsigned *ord); Ésta realiza una búsqueda binaria del elemento val en el vector de enteros apuntado por vec de tam elementos y deja en la memoria apuntada por ord la posición lógica que tiene (o debería tener) el elemento buscado. Retorna 1 si el elemento es hallado o 0 en caso contrario. Para calcular el elemento mitad del vector se desplaza tam un bit a la derecha, lo que equivale a dividirlo en dos, pero resulta mucho más rápido para el procesador que la operación de división.

int busbin (int *vec, unsigned tam, int val, unsigned *ord) {if (!(vec && tam && ord)) return 0; unsigned mitad = tam >> 1; // Divide tam en 2 desplazando un bit a la// derecha. Es más rápido que tam / 2. if (vec [mitad] == valor) { *ord += mitad; return 1; }

if (vec [mitad] < valor) { mitad++; *ord += mitad; vec += mitad; tam -= mitad; }

else tam = mitad;return tam? busbin (vec, tam, va, ord): 0;}

1.-

...