Lógica de primer orden - Base de conocimientos de relaciones familiares

Se muestra a continuación, una representación sistemática, del dominio del parentesco, a través del uso de la lógica de primer orden. La base de conocimientos, de esta manera, viene a conformarse por los siguientes predicados y funciones:

Búsquedas - Mapa de Rumania y Eight Puzzle

Se adjunta a continuación un link con el código fuente relativo a las búsquedas (heurísticas y no heurísticas), implementado tanto para resolver el mapa de Rumania, así como el Eight Puzzle.

http://www.multiupload.com/FWPVLZI4KX

Heurística, y búsquedas heurísticas

Heurística

Heurística, es un término para técnicas basadas en la experiencia, que ayudan en la resolución de un problema, aprendizaje, y descubrimiento. Un método heurístico es usado para llegar a una solución rápidamente que se espera sea cercana a la mejor respuesta posible, o “solución óptima”. Una heurística es una conjetura, un juicio intuitivo, o simplemente sentido común.

En ciencias computacionales, una heurística es una técnica diseñada para resolver un problema que ignora si la solución puede ser probada correcta, pero que usualmente produce una buena solución o resuelve un problema más simple que contiene o intersecta con la solución de un problema más complejo.

La intención de las heurísticas, es ganar desempeño computacional, o simplicidad conceptual, potencialmente al costo de precisión.

Búsqueda heurística

Una búsqueda heurística, es aquella que emplea  una “heurística”, tal como fue definida en la sección anterior. En una búsqueda de este tipo, cada sucesión iterativa, depende del paso anterior, por lo tanto, la búsqueda heurística aprende qué caminos perseguir, y qué caminos ignorar midiendo qué tan cerca la iteración actual, se encuentra a la solución. Por lo tanto, algunas posibilidades nunca serán generadas pues son consideradas de menor probabilidad para llegar a la solución.

Un método heurístico puede lograr su tarea, usando árboles de búsqueda. Sin embargo, en lugar de generar todas las ramas de posibles soluciones, una búsqueda heurística selecciona las ramas con mayor probabilidad de producir resultados, que otras ramas. Es selectiva en cada punto de decisión, escogiendo las ramas, que tienen mayor probabilidad de generar soluciones.

Búsqueda primero el mejor (Best first search)

La aproximación general para estrategias de búsqueda informada, es conocida como búsqueda primero el mejor (best first search), donde un nodo es seleccionado para expansión, basados en una función de evaluación f(n).

La función de evaluación se interpreta como un estimado del costo, de tal manera que el nodo con la menor evaluación, se expande primero.

Lo anterior, implica para la implementación del algoritmo, la necesidad de ordenar los nodos en la frontera de acuerdo a un orden incremental de los costos.

La mayoría de los algoritmos primero el mejor, incluyen a una función heurística como componente de f, denominado h(n):

h(n) = costo estimado de la ruta de menor costo desde el estado en el nodo n, al estado final.

Existen dos casos especiales de búsqueda primero el mejor:

• Búsqueda voraz primero el mejor (Greedy best first search).
• Búsqueda A*.

Estos algoritmos se analizan con mayor detenimiento a continuación.

Búsqueda voraz primero el mejor (Greedy best first search)

La búsqueda voraz primero el mejor, intenta expandir el nodo que se encuentra más cerca de la meta, bajo la suposición de que esto es probable que lleve a una solución rápidamente. De esta manera, evalúa nodos usando sólo la función heurística; esto es, f(n) = h(n).

Propiedades

• Este algoritmo no es completo, puede quedarse atascado en ciclos.
• Tiempo: O(b^m), pero una buena heurística puede proporcionar una mejora dramática.
• Espacio: O(b^m), mantiene todos los nodos en memoria.
• Óptimo: No.

Búsqueda A*

Es un algoritmo  que se utiliza ampliamente en la búsqueda de rutas, y el recorrido de grafos, el proceso de trazar un camino eficientemente transitable entre puntos, denominados nodos. Conocido, por su desempeño, y precisión, goza de un amplio uso. Se le considera una extensión del algoritmo de Dijkstra. A* logra un mejor desempeño (con respecto al tiempo), haciendo uso de heurísticas.

Descripción

El algoritmo A* utiliza una búsqueda primero el mejor, y encuentra la ruta de menor costo dado un nodo inicial, hacia un nodo objetivo.

Utiliza una función heurística de “distancia más costo” (generalmente denominada f(x)) para determinar el orden en que la búsqueda visitará los nodos en el árbol. La heurística de “distancia más costo” es una suma de dos funciones:

• La función del costo de la ruta, la cual consiste en el costo desde el nodo inicial, al nodo actual (usualmente denominada g(x)).
• Y un “estimado de heurística” admisible de la distancia a la meta (usualmente denominado h(x)).

La parte h(x), de la función f(x), debe ser una heurística admisible, lo que significa, que no debe sobrestimar la distancia a la meta. De esta manera, para una aplicación como el ruteo, h(x) puede representar la distancia en línea recta a la meta, dado que físicamente, es la distancia más pequeña posible entre dos puntos, o nodos cualquiera.

Si la heurística satisface además la condición h(x) ≤ d(x, y) + h(y) para toda arista x, y del grafo (donde d denota la longitud de esa arista), entonces h es llamada monótona, o consistente. En tal caso, A* puede ser implementado más eficientemente.

Propiedades

De la misma manera que la búsqueda primero en anchura, A* es completa, y siempre encontrará una solución, si es que existe.

Si la función heurística h es admisible, entonces A* es admisible (óptimo) si no usamos una lista de nodos ya visitados (conjunto cerrado).

Si se utiliza un conjunto cerrado, entonces h debe ser monótona (o consistente) para que A* sea óptimo.

Asimismo, A* es óptimamente eficiente, para cualquier heurística h, lo cual significa, que ningún algoritmo que emplee la misma heurística, expandirá menos nodos que A*, excepto cuando existan múltiples soluciones parciales, donde h predice exactamente el costo del camino óptimo.

La complejidad en tiempo de A* depende se la heurística. En el peor caso, el número de nodos expandidos es exponencial en la longitud de la solución (el camino más corto), pero es polinomial cuando el espacio de búsqueda es un árbol, hay un sólo estado objetivo, y la función heurística cumple la condición de que su error no crecerá más rápidamente que el logaritmo de la “heurística perfecta” (aquella que regresa la verdadera distancia a la meta).

Formalización de problemas

Criptoaritmética

Estados: Un estado es una asignación (parcial) de dígitos a letras.

Operadores: La asignación de un dígito a una letra. (Puede incluir restricciones como que el dígito no haya sido ya usado, y que las reglas aritméticas no sean violadas).

Prueba de si se ha llegado al estado objetivo: Determinar si a todas las letras, le han sido asignadas dígitos, y que la suma sea correcta.

Estado inicial: Una asignación parcial de dígitos a letras.

Estado final: Un estado en el que a todas las letras le han sido asignadas dígitos, y la suma es correcta.

Misioneros, y caníbales

Operadores: Son cinco los operadores, los cuales se listan a continuación:

1. Llevar a un misionero al otro lado.
2. LLevar a un caníbal.
3. Llevar a dos misioneros.
4. Llevar a dos caníbales.
5. Llevar a un misionero, y a un caníbal.

Estados: Un estado se conforma de tres variables:

1. Número de lanchas en un lado.
2. Número de caníbales.
3. Número de misioneros.

Prueba de si se ha legado al estado objetivo: Determinar si el estado actual corresponde a (0, 0, 0)

Estado inicial: (3, 3, 1)

Estado final: (0, 0, 0)