• Author / Uploaded
• Edward Enrique Morales Perez

Citation preview

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

Tipos de algoritmos de búsqueda Desde el inicio de la IA, el término “heurística” osciló entre dos sentidos fundamentales vinculados a la utilización de información del dominio de problemas (con el fin de hacer una búsqueda más eficiente) y a la imposibilidad de garantizar encontrar la solución de un problema. Entre los algoritmos de búsqueda se encuentran los siguientes métodos: 1. Búsqueda secuencial o lineal 2. Búsqueda Secuencial Indexada 3. Búsqueda Binaria 4. Búsqueda por Interpolación

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.

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

Desventajas de la técnica. 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. Si los registros a los que se accede con frecuencia no están al principio del archivo, la cantidad promedio de comparaciones aumenta notablemente dado que se requiere más tiempo para recuperar dichos registros. Para las aplicaciones interactivas que incluyen peticione s o actualizaciones de registros individuales, los archivos secuenciales ofrecen un rendimiento pobre. Definitivamente, la búsqueda secuencial es el método menos eficiente; porque se basa en comparar el valor que se desea buscar con cada uno de los valores del archivo. Búsqueda Secuencial Indexada es un método popular para superar las desventajas de los archivos secuenciales es el del archivo secuencias indexado; pero implica un aumento en la cantidad de espacio requerida. Funciona de la siguiente manera: Se reserva una taba auxiliar llamada índice además del archivo ordenado mismo. Cada elemento en el índice consta de una llave kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el índice al igual que los elementos en el archivo, deben estar ordenados en la llave. Si el índice es de un octavo del tamaño del archivo, se representa en el índice cada octavo registra el archivo. Si el índice comienza a crecer tanto que se vuelve ineficaz se puede usar un índice secundario que funciona casi de la misma forma que el índice principal, solo que apunta a este, no a la tabla principal la búsqueda empieza con una exploración por el índice secundario; esto nos lleva a un su arreglo en el índice principal; después el procesamiento continua normalmente. Un ejemplo de lo anterior es la siguiente figura.

Ventajas de la técnica Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar. La ventaja real del método secuencial indexado es que los elementos en la tabla pueden ser examinados en forma secuencial si todos los registros en el archivo deben ser accesados, pero sin embargo, el tiempo de búsqueda para algún

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

elemento en particular se reduce considerablemente. La búsqueda secuencial se realiza en la tabla de índices que es más pequeña en lugar de la tabla más grande. Una vez que se ha encontrado un índice correcto, se hace una segunda búsqueda secuencial únicamente en la parte reducida de la tabla que contiene los registros. La organización secuencial indexada es conveniente para archivos con mediana volatilidad, actividad variable y tamaño relativamente estable. Las eliminaciones de una tabla secuencial indexada se pueden hacer fácilmente mediante la asignación de banderas a las entradas que son eliminadas. Durante la búsqueda secuencial a través de la tabla, se ignoran las entradas que han sido eliminadas.

Búsqueda Binaria si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina búsqueda binaria. La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. 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 determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sublista. Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son: 

La lista debe estar ordenada en un orden específico de acuerdo al valor de la llave.



Debe conocerse el número de registros.

Algoritmo Se compara la llave buscada con la llave localizada al centro del arreglo. Si la llave analizada corresponde a la buscada fin de búsqueda si no. Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior. El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n. Búsqueda por Interpolación este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal. El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado. Si se determina que la clave buscada XX se encuentra dentro del intervalo INTABLA de la tabla, y que la variación en ese intervalo de la clave es INCLAVE, la siguiente posición a probar es: PX = PI + ENTERO ((XX-XI) * (INTABLA / INCLAVE)) El algoritmo es similar al de búsqueda binaria, la diferencia está en que en vez de dividir el área en mitades, se delimita por medio de los valores resultantes de la interpolación. En búsqueda binaria el espacio se corta siempre adentro a medias, las garantías de lo que desea el funcionamiento logarítmico. Sin embargo, durante la búsqueda encontramos un valor que esté muy cerca del número z de la búsqueda, parece más razonable continuar la búsqueda en esa área en vez de ocultar e ir a la media punta siguiente. En detalle, si z es muy pequeño, debemos comenzar la búsqueda en alguna parte en el principio de la secuencia en vez de la punta intermedia Considere la manera que abrimos un libro cuando estamos buscando para cierta página. Diga que la página es 200 y el libro parece de 800 páginas. La paginación 200 es así alrededor de la marca de un cuarto, y nosotros utilizamos este conocimiento como indicación de donde abrir el libro. No golpearemos probablemente la paginación 200 en el primer intento; suponga que conseguimos la paginación 250 en lugar de otro. Ahora cortamos la búsqueda a un rango de 250 páginas, y la paginación deseada está en alrededor la marca de 80 por ciento entre la paginación 1 y 250. Ahora intentamos ir detrás de un quinto de la manera corta. Podemos continuar este proceso hasta que conseguimos bastante cercanos a la paginación 200, de que podemos mover de un tirón una página al mismo tiempo. Ésta es exactamente la idea detrás de la búsqueda de la interpolación. En vez de cortar el espacio de la búsqueda por una mitad fija, la cortamos por una cantidad que se parezca la más probable tener éxito. El funcionamiento de la búsqueda de la interpolación depende no solamente de la talla de la secuencia, pero también de la entrada de información misma. Hay entradas de información para los chequeos de la búsqueda de interpolación del deseado en cada número en la secuencia. Sin embargo, la búsqueda de la

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

interpolación es muy eficiente para las entradas de información que consisten en elementos relativamente uniformemente distribuidos (las paginaciones de un libro, por supuesto, se distribuyen uniformemente). Puede ser mostrado que el número medio de comparaciones se realizó por la búsqueda de interpolación, donde el promedio asume el control todas las secuencias posibles, es 0 (logn del registro). Aunque éste se parece ser un orden de la mejora magnitud concluida del funcionamiento de la búsqueda binaria (debido al logaritmo adicional). Búsqueda Indexada Necesita que los elementos sobre los que se realiza la búsqueda estén ordenados de acuerdo a una determinada clave. El método utiliza un array auxiliar denominado array índice. Cada objeto en el array índice consta de un valor y la posición que ocupa dicho valor en el correspondiente array ordenado:

En Java se define como se muestra a continuación: class ElemIndice{ private intclave; private intposicion; public ElemIndice(intc, intp){ clave=c; posicion=p;} public intgetClave(){ return clave; } public intgetPosicion(){ return posicion; } }

Materia: Inteligencia Artificial

Grupo: MS9

Profeso(a): Suarez Amendola Rosario de Fátima

29 de octubre de 2014

Alumno: Morales Pérez Edward Enrique

Redes Neuronales En los intentos por sistematizar la comprensión del cerebro pueden distinguirse dos caminos: 1. El primero es el seguido por los neurofisiólogos, quienes generalmente confrontan una abundancia de datos tan vasta que dificulta el examen sistemático dentro de un marco de trabajo experimental. Los datos están perturbados por una cantidad muy grande de influencias que no pueden ser fácilmente eliminadas por el experimentador. 2. El segundo es el que han abierto los constructores de modelos sobre la base de un conjunto también grande de suposiciones acerca del sistema que se busca explicar, con la esperanza de que el enfoque ayude al surgimiento de nuevas hipótesis, susceptibles de ser verificadas con la diversidad de datos disponibles.

Dentro del segundo de los caminos antes mencionados hay dos opciones para los creadores de modelos: 1. La primera opción consiste en tratar de modelar al sistema real tanto como sea posible. Sin embargo, suele suceder que se introducen tantos parámetros que en realidad no se alcanza ningún entendimiento profundo; de donde se llega al resultado paradójico de que, buscando tanta fidelidad al sistema real, resulta una copia tan mala que la comprensión del fenómeno se desvanece. 2. El otro enfoque consiste en descartar, a priori, todos aquellos parámetros que a primera vista parecen no ser esenciales, a fin de simplificar el análisis matemático. Estos no constituyen representaciones realistas del cerebro, sino que su inspiración neuronal puede contribuir a comprender algunas de las propiedades que los caracterizan en el procesamiento de información}. La combinación de estas dos últimas opciones va acompañada y motivada por la experiencia, la intuición y el deseo de cuantificar el problema. La calidad del enfoque puede respaldarse en los resultados obtenidos en años recientes, que han mostrado progresos en el proceso de incorporación de más detalles biológicos a los modelos analíticamente solubles.