Site hosted by Angelfire.com: Build your free website today!



Mapa de los Estados Unidos utilizado en los programas de búsqueda

MAPA DE LOS ESTADOS UNIDOS



Tipos de búsquedas ideales. Hacia la inteligencia artificial heurística

La heurística computacional ha desarrollado muy diversos programas de búsqueda para todos los lenguajes informáticos, pero en general, no son los programas, sino la estructura de los datos, los que condicionan y determinan la búsqueda más adecuada en cada caso. Para buscar personas u objetos desaparecidos, hay que salir de la red y estar y moverse en el mundo real, pero las ideas heurísticas son esencialmente válidas tanto dentro como fuera de la red. Tal vez algún día pueda hablarse de algo parecido a un GOOGLE multimedia, pero mientras, somos nosotros los que tenemos que hacer un trabajo de abstracción, búsqueda y proyección. Es decir, que hay que idealizar modelizando lo que se busca, aplicar técnicas heurísticas lo más adecuadas que sea posible, y después llevar los resultados allá donde sean más necesarios.

Sobre la abstracción y la idealización hay muy interesantes puntos de vista, y varias técnicas. Nadie tiene la última palabra, pero posiblemente sí que podamos admitir que los primeros diálogos realmente útiles para buscar fueron los de PLATÓN. Algunos párrafos que el gran mago del pensamiento atribuye a Sócrates tienen gran utilidad para buscar, porque la filosofía puede ser eso y sólo eso: una búsqueda. Personalmente, yo recomiendo el FEDÓN de Platón, a todo el que tiene que asumir la responsabilidad de una dolorosa búsqueda. Cada párrafo del FEDÓN admite profundos estudios, como el que yo mismo he tenido la oportunidad de hacer en lo que puede verse publicado en
La filosofía, y las matemáticas, son, en mi opinión, las mejores guías espirituales para buscar. Por una parte, la lógica, desde la aristotélica a la matemática, y actualmente la lógica difusa (fuzzy logic), y por otra la algorítmica para estructuras y bases de datos, así como la inteligencia artificial aplicada a la heurística, permiten llegar intelectualmente muy lejos, como trataremos de exponer de manera comprensible para un lector de cultura media, en lo que sigue.

La heurística se ha desarrollado desde muy diversas especialidades (ciencias de la computación, biblioteconomía y documentalismo, periodismo, técnicas de investigación, criminalística o policía científica). Por solo citar un ejemplo sobre cómo se puede plantear científicamente la heurística computacional podemos referenciar la página del Alvaro Barreiro en el Departamento de. Computación de la Facultad de Informática de la Universidade da Coruña, de la que copiamos aquí una parte dedicada a la búsqueda computacional del índice de la asignatura de Inteligencia Artificial expuesto en


Resolución de Problemas Mediante Búsqueda


Estrategias de búsqueda. Búsqueda ciega o no informada

Métodos de Búsqueda informada


Estos apartados puede merecer un curso de alta especialización para cada uno de ellos, y hay empresas dedicadas a la inteligencia artificial que han dedicado importantes sumas de dinero a la investigación tecnológica, y a las patentes, de varios mecanismos de búsqueda. Pero nuestra intención es, siendo conscientes de lo lejos que estamos del estado del arte en investigación heurística, poder ser útiles a quienes tienen que buscar con los todos los recursos a su alcance, y también con nuestra mejor voluntad.

Hay conceptos, como el retroseguimiento o la potencia heurística, que explicaremos con carácter general y también para su aplicación a la búsqueda de los desaparecidos, pero conviene no ensimismarse sopesando demasiadas posibilidades sin buscar o comprobar al menos algunas de las opciones, porque también hay que administrar el tiempo que se dedica a planificar, y a corregir anteriores planificaciones, puesto que demasiada reflexión siempre limita las posibilidades de búsqueda, hasta llegar a la atrofia y a la parálisis cuando y donde menos nos la podemos permitir.

Por ello, simplificando, podemos considerar en principio, que los datos, los objetos y los lugares pueden estar dispuestos en series, es decir, en secuencias, por ejemplo, en una lista de nombres, cantidades y teléfonos, o la línea de un rastro continuo que pueda ser olfateado por perros, o la localización de un punto determinado por el kilómetro y los metros de una carretera o de una vía de ferrocarril con referencia a un origen de referencia.

Pero nuestro modelo se complica si ramificamos la lista por las iniciales alfabéticas de los nombres o las de números mayores o menores, o los prefijos de los teléfonos, porque cada letra, y cada dígito, abre un conjunto más o menos manejable de opciones que deben ser rastreadas de manera diferente a la secuencial. Los rastros también pueden ramificarse o discontinuarse, y las carreteras o los ferrocarriles forman parte de redes con estructuras muy complejas. De hecho, el llamado "problema del viajante" es uno de los desafíos más complejos en el álgebra computacional consiste en la optimización por minimización del recorrido de un viajante que tiene que pasar por varias ciudades intercomunicadas por carreteras porque a partir de cierto número de puntos y de complejidad de las interconexiones posibles, ni los ordenadores más potentes son capaces de encontrar la solución. Pero el problema de los problemas, incluso cuando el número de puntos y de líneas de unión es muy pequeño, es que la mayoría de las personas que deben buscar en ellos ni se imaginan cómo puede plantearse rigurosamente el problema. Intentaremos ayudarles a continuación.


Búsquedas secuenciales (con o sin orden previo) de listas simples

La unidad mínima de búsqueda es la comparación elemental, o cotejo de lo que conocemos en lo que no conocemos, es decir, si un dato identificativo está o no está dentro de lo que buscamos, en este caso, en una lista.

Con seguridad matemática puede demostrarse que si la lista de N elementos es ideal (consideramos un elemento "0", siempre útil instrumentalmente), cuando no está ordenada son necesarias N+1 comparaciones para certificar que no se encuentra en ella lo que buscamos, y cuando sí que está en ella lo que buscamos, como media serán necesarias (N+1)/2 comparaciones (aunque es perfectamente posible que sean necesarias N en el peor de los casos, y sólo 1 en el mejor para el que busca). Es decir, que el coste medio de la búsqueda con éxito es, exactamente, la mitad de lo que cuesta el fracaso, por lo que equivocarse en el cálculo de la prospectiva de búsqueda cuesta el doble que acertar, y además, no sirve para nada, agotando y desmoralizando a quien(es) busca(n).

Si la lista sí está ordenada, en las búsquedas secuenciales bastan N/2 comparaciones, tanto si se tiene éxito, como si se fracasa, pero el orden tiene un coste, y un riesgo. Una mala ordenación del todo en el que buscamos puede imposibilitar para siempre encontrar nada, porque lo damos por seguro, y no volveremos a buscar ahí hasta que no cuestionemos y rehagamos su orden. Es decir, que en la búsqueda en listas la ordenación reduce a la mitad el esfuerzo cuando lo que buscamos no está en la lista aunque estas estimaciones no son tan precisas para el trabajo humano como para los ordenadores, a los que les da igual tener que hacer una comparación crítpica o simple, mientras que al ser humano pronto se le agota la paciencia con el trabajo repetitivo, aumentando la probabilidad de cometer un error, y ese riesgo siempre hay que tenerlo muy en cuenta.

Las listas pueden enlazarse, circularse, cruzarse y en general, admiten formar parte de modelos descriptivos de estructuras de datos mucho más complejos. Los profesionales más familiarizados con el manejo de listas casi intuitivamente organizan su trabajo de manera que en poco tiempo pueden controlar grandes probabilidades de éxito, pero su desarrollado talento debe combinarse con la prudencia, el rigor y el método sistemático de quienes pretendemos no descartar nada que pueda dar una pista para encontrar a un desaparecido. Las listas encuentran sus límites pronto, porque la realidad y su dinámica suele ser multidimensional e hipercompleja, de manera que un buen buscador no puede limitarse a listar listas de listas, sino que tiene que conocer, comprender, y hacer comprender para utilizar correctamente estructuras de datos más complejas.

Actualmente estamos trabajando en un procedimiento informático para el cotejo de listas secretas, de manera que podemos garantizar con total rigor si un elemento (el dato identificativo del desaparecido) pertenece a un conjunto de varios elementos (la lista de datos de otros elementos), sin tener que disponer, o para mayor precisión, sin que nadie tenga que ver, el resto de los elementos. Esta búsqueda ciega puede ser útil para inspeccionar sistemas informáticos complejos que almacenen datos de cierta sensibilidad y protegidos por la ley, permitiendo asegurar la confidencialidad, sin perder eficacia. Estas tecnologías de inspección de ordenadores están relacionadas con experiencias periciales que nos han permitido poner a prueba técnicas avanzadas de ingeniería e informática forense, como las que se explican en el documento Word publicado en
Como veremos a continuación en la búsqueda binaria, cuando se tiene una lista ordenada, es un error técnico el plantear una búsqueda secuencial, porque los resultados (o encontramos, o no encontramos lo que buscamos) se obtienen mucho antes, y con menos esfuerzos intelectuales o de movilidad.

Pero, para bien o para mal, la vida, los espacios y lugares, las estructuras, formas y con todo ello, las opciones de búsqueda, rara vez son tan planas y casi nunca están perfectamente ordenadas, a menos que busquemos un teléfono en una guía, y aún así, podríamos tener muchas dudas, a menos que encontremos pronto todo lo que buscamos.

Búsquedas binarias, posibles balanceos de sus árboles y retroseguimiento.

"Divide y vencerás" es el lema de la mejor búsqueda cuando es posible dividir bien el espacio, el tiempo y los recursos para buscar. Cualquier superficie a rastrear, y cualquier recorrido por laberíntico que parezca, puede ser convertido en un árbol con nodos y tramos equivalentes a cualquier geometría de una búsqueda. La teoría de grafos demuestra que esos árboles representan de forma precisa, hasta ser perfectamente equivalentes, todos los posibles recorridos.

Una vez que tenemos bien definido el árbol de la búsqueda, hay que estar dispuesto a volver al principio, porque la experiencia demuestra que retroceder desmoraliza, pero que la tenacidad vence, y encuentra. El término técnico para denominar ese retroceso hasta una lugar anteriormente explorado, se llama "retroseguimiento", y hay que verlo con claridad, e incluso como una necesidad en la mayoría de las búsquedas, que pueden ser mejores si se reducen los retroseguimientos, pero que tampoco son necesariamente malas si se retrosigue de vez en cuando.

El punto de encuentro de los buscadores organizados es siempre un punto de retroseguimientos por lo que conviene elegirlo bien, y tratar de cuidar esos detalles que hacen que una búsqueda sea eficiente, tanto por disponer de planos, documentación y comunicaciones en el punto de encuentro, como por ser un buen lugar para recuperar energías y descansar. Los vecinos siempre son una ayuda valiosísima en la búsqueda de un ser querido, y sus casas son ideales para retroseguir sin afectar a la familia ni alterar el último punto de presencia del desaparecido, con sus valiosas pruebas y sus incontables indicios.

Y a partir del punto principal de encuentro, hay que organizar las batidas, los rastreos, las comprobaciones y los seguimientos y retroseguimientos.

Explosión combinatoria en búsquedas complejas .
Técnicas de búsqueda en profundidad, anchura, escalada y coste.
Inteligencia artificial aplicada a la búsqueda con heurística muy avanzada

 

 

Programas de Metodos de Búsqueda

Introducción

Los métodos de Búsqueda Heurística se originaron en I.A con el objeto de encontrar un procedimiento de Razonamiento Universal independiente del dominio y desde los Primeros Principios de cada uno de ellos, ahora la atención se centra en el Conocimiento Heurístico con el fin de modelar el Conocimiento Específico o Expertise o Pericia.

Sin embargo, la aplicación de las técnicas de búsquedas heurísticas pueden ser encontradas en programas tales como: Entendimiento de Lenguaje Natural, Solución de Problemas Combinatorios, Recuperación de Información, Robótica, Juegos y Prueba de Teoremas Matemáticos. Las técnicas de Solución de problemas mediante la creación y modificación secuencial de expresiones simbólicas, generan estados potenciales que se prueban para verificar si representan soluciones al problema

 

El algoritmo A*

Cuando tenemos un tablero de dos dimensiones con celdas con costes podemos pensar en representarlo como un grafo (celdas=nodos y adyacencia=arcos) etiquetado con los costes de moverse de una celda a otra y otros factores de ponderación como el raiz de dos si las celdas son cuadradas y nos movemos en diagonal.

Con un grafo entre las manos podemos recurrir a las herramientas típicas de los mismos. Ya bien conocidas por todos. La primera de todas podría ser el algoritmo de Djkstra (o Dijkstra) que nos calcula el camino mínimo de ir de un nodo (celda) a otro. El problema es que este algoritmo es O(n^2). Es decir, que si tenemos un tablero de 100x100 (no muy pequeño, pero tampoco inmenso) habremos de hacer 100x100x100x100 iteraciones con cada bichito que quiera buscar un camino. Bastante lento.

Los más inteligentes habrán pensado. Puedo precalcularlo y sólo tengo que mirar en una tabla el nodo (celda) que más me convenga tomar para ir de un sitio a otro. Pues bien, eso es lo que hace el algoritmo de Floyd. Este algoritmo es O(n^3) así que nos sale 100x100x100x100x100x100 que son ya un montón de ceros, aún así, algún cabezon dirá que solo se ejecuta una vez por mapa (si éste no varía en el juego, claro). Pero entonces ¿Cuanto ocupa la matriz para almacenar estos datos? Pues si tengo 100x100 nodos, la matriz es de 100x100x100x100=100Megas. Un poquito.

Al final, hemos de buscar el camino sobre la marcha y tocando los menos nodos posibles. El algoritmo que nos hace esto es el A*. Para explicar el algoritmo A* tenemos muchas páginas web por ahí (en inglés la mayoría) pero voy a dar una pequeña idea sin ser muy formal: En un punto de la búsqueda del camino menor que nos une el origen con el destino tendremos una serie de nodos explorados, otros inexplorados y otros que hacen frontera. De los que están explorados y los fronterizos sé cual es el camino que los lleva al origen y el coste del mismo. Entonces, de los que hacen frontera tomo el más prometedor y lo paso a los explorados. De los que tiene alrededor calculo el coste de llegar a ellos desde el origen a traves del nodo que hemos pasado de fronterizo a explorado. Si alguno de estos nodos que tiene alrededor era uno ya fronterizo y el coste es menor ahora, sé que es mejor pasar por el nodo recien marcado como explorado que por donde llegase antes a este nodo fronterizo. Si el nodo de alrededor era inexplorado, es que no había aún ningun camino para llegar y digo que la mejor manera de llegar es por el nodo recien marcado como explorado. Cuando pasamos de fronterizo a explorado el nodo destino, he acabado y sólo tengo que ver marcha atrás por qué sitios he pasado (recordemos que siempre que hacemos un nodo fronterizo o encontramos un mejor camino, sabemos de qué nodo venimos).

En verdad, la explicación del algoritmo anterior no es A*. Es un paso inferior que se llama A. La diferencia radica en cómo estimar el nodo fronterizo a pasar a explorado y expandir sus nodos adyacentes. Esta estimación se basa en la suma de: el coste de llegar a este nodo más la estimación del coste de llegar de este nodo al destino. Para que el algoritmo sea A* hemos de hacer que esta estimación sea menor o igual que el coste real. Es decir, que si tomamos esta estimación como cero y tan sólo usamos el camino hasta el nodo fronterizo dado, funciona bien. Si no cumplimos el requisito de A*, entonces puede que no encontremos el mejor camino.

Una estimación buena es tomar la distancia (en celdas o nodos) hasta el destino y multiplicarla por el coste mínimo que tengamos. Pero esto es peligroso ya que A* buscará mucho. No pasa tampoco mucho si tomamos una estimación no A*, no siempre encontraremos el mejor camino, pero el algoritmo irá mucho más rápido. A fin de cuentas, en vez de multiplicar por el coste mínimo multiplicamos por el coste medio (o un poquitín menos). Mientras no haya un terreno muy favorable para viajar, nuestro héroe encontrará el camino adecuado y si no encuentra el camino adecuado, tampoco importa mucho ya que de todas formas va a tardar poco en llegar (coste bajo).

Hay múltiples mejoras al algoritmo A*: estimaciones más complejas, cálculo a múltiples escalas, hibridación con algoritmos tipo Floyd o Djkstra y uso de cotas para hacer que si hay varios caminos con costes similares que tome uno de ellos y no todos a la vez. Algunos toman el camino perfecto, otros se aproximan, algunos tardan más otros menos, pero ninguno resuelve el problema del movimiento a la vez. Hemos dicho que el algoritmo A* (y en general todos en cierta medida) explora por adelantado antes de andar. Si explora una casilla relativamente lejana puede que para cuando nuestro héroe llegue allí su coste haya cambiado: se haya puesto otro bicho (un troll en el camino del heroe o los agentes de Expediente X con el marciano) o se haya quitado. Así que no nos podemos fiar ni de A* ni de ningún otro de sus hermanos.