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
Pasos
en la resolución de problemas
Formulación de
problemas
Problemas ejemplo
Búsqueda de soluciones
Estrategias de búsqueda. Búsqueda ciega o no informada
Criterios
de evaluación
Primero en anchura
Coste uniforme
Primero
en profundidad
En profundidad limitada
Profundización
iterativa
Métodos de Búsqueda informada
Búsqueda
el primero mejor
Búsqueda Greedy
Búsqueda
Funciones
heurísticas
Búsqueda con limitaciones de
memoria
Algoritmos de mejora iterativa
Escalada
Enfriamiento
simulado
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
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.