Estructuras De Busqueda

ESTRUCTURAS DE BÚSQUEDA
Investigación
08/04/2011 José Vega Rodríguez

INTRODUCCIÓN Los algoritmos que se trataran en el presente trabajo de investigación son de gran importancia para el manejo de datos e información, una implementación adecuada de los conocimientos adquiridos mediante este artículo nos permitirá realizar pseudocódigos más cortos y más eficaces propiciando menor cantidad deprocesos en nuestra computadora. Los algoritmos de ordenación se pueden clasificar atendiendo a distintos criterios. Una posible clasificación consiste en distinguir entre algoritmos simples y sofisticados. Los algoritmos de búsqueda que se exponen a continuación se aplican a árboles. Como se verá, muchos problemas de optimización pueden modelarse de manera de generar un árbol cuyos nodosconstituyen posibles soluciones o pasos intermedios a la solución del problema; cada uno de estos algoritmos define un orden en el cual se generarán los nodos del árbol, y una forma en la cual se encontrará la solución buscada. Los algoritmos de ordenación, como su propio nombre apunta, sirven para ordenar datos. Hay unos cuantos, y son bien conocidos y estudiados por la algoritmia... Que si la burbuja,que si el quicksort... La mayor parte de ellos son sencillos de entender y codificar. Pero muchas veces no se utilizan con un criterio claro.

¿QUÉ ES UNA ESTRUCTURA DE BÚSQUEDA? Un algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente. Complejidad computacional Si la solución seencuentra en el nivel n, y la cantidad máxima de hijos de un nodo es i, habrá que expandir, en el peor de los casos, la cantidad de nodos de un árbol de orden i y de altura n:

Por lo tanto, tanto el tiempo de procesamiento como el requerimiento de memoria tendrán un orden exponencial, tanto si evita o no expansiones repetidas. Ventajas y desventajas Expandir los nodos de forma uniforme garantizaencontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, parta obtener todas las soluciones posibles. La desventaja principal es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados losparámetros i y n del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables. Un algoritmo de búsqueda en profundidad recorre todos los nodos de un árbol de manera ordenada, pero no uniforme. Consiste en ir expandiendo cada uno de los nodos a medida que los encuentra, empezando siempre por el primer nodo hijo no visitado del nodo actual; cuando ya no quedan más nodos hijos que visitaren el actual, regresa (backtracking), y el padre del nodo pasa a ser el nodo actual. El criterio de camino agotado debe ser elegido cuidadosamente, de manera de evitar la expansión indefinida de nodos. Asimismo, para garantizar la convergencia, en muchos casos debe evitarse la expansión de nodos repetidos, al menos en un mismo camino.

Para implementar tanto la búsqueda en profundidad, como labúsqueda en anchura, la de costo fijo y la heurística, puede utilizarse un algoritmo genérico: 1. Colocar el nodo inicial en la lista abierta. 2. Elegir el próximo elemento de la lista abierta a extraer, y realizar la extracción. 3. Si se corresponde con un estado final, devolver el elemento o la secuencia de acciones correspondiente, si no, continuar. 4. Expandirlo, colocando los descendientesque correspondan en la lista abierta. 5. Colocarlo en la lista cerrada y volver a 2. De las características de la estructura de datos utilizada como lista abierta, dependerán las características del algoritmo: Si la estructura es una pila, el algoritmo elegirá siempre el último nodo generado, y a partir de ese nodo generará nuevos nodos, que serán agregados a la pila, y el primero será elegido, y...