2.4 Estrategias de búsqueda informada

En la Figura 1 se muestra el espacio de estados que utilizamos para desarrollar la implementación de las estrategias de búsquedas ciegas en Common Lisp: primero en profundidad y primero en amplitud. Estas búsquedas no usan información acerca de la cantidad de pasos necesarios o sobre el costo de ruta para avanzar a partir del estado actual, lo único que permiten hacer es diferenciar entre un nodo meta y el que no lo es.

2.4.1 Búsqueda primero el mejor

En ocasiones, es posible estimar qué tan lejos se encuentra un nodo del final. En tal caso, tiene sentido extender primero la trayectoria que parece acercarnos más rápidamente al nodo final. Esta estrategia se denomina búsqueda primero el mejor. Para implementarla se requiere el uso de una función de evaluación que me permita valorar cada trayectoria parcial usando el valor que regrese esa función h, de estimación heurística, que produce un número que representa lo deseable (o indeseable) que sería la expansión de una trayectoria.

Para lograr esto es necesario ordenar las trayectorias parciales de acuerdo con la estimación que se haya elegido. Normalmente se elige una función de evaluación que regrese valores menores para las trayectorias más deseables.

2.4.1.2 Función de evaluación

En este ejemplo, como en casi todos los casos de determinación de ruta, una buena función heurística es la distancia en línea recta (DLR) del nodo actual hasta el nodo meta. Es decir:

hDLR(n) = Distancia en línea recta entre el nodo n y el nodo meta.

Para calcular la distancia entre dos puntos requerimos sus coordenadas (x,y). La distancia entre los nodos n1 con coordenadas (x1,y1) y el nodo n2 con coordenadas (x2,y2) está dada por la fórmula:

2.4.1.3 LET

Esta función de Common Lisp nos permite definir variables locales a los procedimientos definidos por el usuario.

Sintaxis:

(LET ((var1 valor1)(var2 valor2)...(var-n valor-n)) cuerpo )
Por ejemplo:
(let ((a 6) (b 4)) (+ a b)) → 10
(setq lista1 '(2 4 6))
(let ((a (first lista1)) (b (second lista1))) (+ a b)) → 6

2.4.1.4 SORT

Esta función de Common Lisp ordena listas. Recibe como argumentos una lista y un argumento de compa-ración.

Sintaxis:

(sort lista argumento_de_comparación)

Por ejemplo:

(sort '(9 3 5 2 8) #'<) → (2 3 5 8 9); Números de menor a mayor
(sort '(9 3 5 2 8) #'>) → (9 8 5 3 2); Números de mayor a menor

(sort '( f b e a c) 'string-lessp) → (A B C E F) ; Alfabético ascendente
(sort '( f b e a c) 'string-greaterp) → (F E C B A) ; Alfabético descendente

(sort '((9 a) (4 c) (3 b)) #'(lambda (x y) (< (first x) (first y))))
→ ((3 B) (4 C) (9 A))

El último ejemplo del bloque anterior ordena de menor a mayor usando como argumento de comparación el primer elemento de cada sublista. El siguiente ejemplo ordena ascendentemente usando como argumento de comparación el segundo elemento de cada sublista:

(sort '((9 a) (4 c) (3 b))
#'(lambda (x y) (string-lessp (second x) (second y))))→((9 A) (3 B) (4 C))

2.4.1.5 Coordenadas de los nodos

Para agregar las coordenadas a los nodos del espacio de estados de nuestro ejemplo, utilizaremos setf-get:

(setf (get 's 'coordenadas) '(0 3)
(get 'a 'coordenadas) '(4 6)
(get 'b 'coordenadas) '(7 6)
(get 'c 'coordenadas) '(11 6)
(get 'd 'coordenadas) '(3 0)
(get 'e 'coordenadas) '(6 0)
(get 'f 'coordenadas) '(11 3) )

2.4.1.6 Distancia en línea recta entre puntos

Para calcular esta distancia definimos el procedimiento DLR que recibe como párametros dos nodos y regresa la distancia en línea recta entre ellos:
(defun DLR (n1 n2)
(let ((x1 (first (get n1 'coordenadas)))
(y1 (second (get n1 'coordenadas)))
(x2 (first (get n2 'coordenadas)))
(y2 (second (get n2 'coordenadas))) )
(sqrt (+ (expt (- x2 x1) 2) (expt (- y2 y1) 2)))
)
)
Utilizando DLR es más sencillo determinar si una trayectoria parcial termina más cerca del nodo final que otra:

(defun mas-cercap (trayectoria1 trayectoria2 nodo-destino)
(< (DLR (first trayectoria1) nodo-destino)
(DLR (first trayectoria2) nodo-destino))
)
Usando mas-cercap como argumento de comparación para ordenar la cola de trayectorias parciales, vamos ahora a implementar la estrategia de búsqueda primero-el-mejor:

(defun primero-el-mejor (inicial final &optional
(cola (list (list inicial))))
(cond ((endp cola) nil) ; ¿esta vacia la cola?
((eq final (first (first cola))) ; trayectoria completa?
(reverse (first cola)) ) ; Devuelve trayectoria.
(t (primero-el-mejor inicial final
(sort (append (extiende (first cola)) (rest cola))
#'(lambda (t1 t2) (mas-cercap t1 t2 final)))))
)
)

Al ejecutarlo obtenemos:

> (primero-el-mejor 's 'f) → (S A B E F)
> (trace primero-el-mejor)
;; Rastreando la función PRIMERO-EL-MEJOR.
(PRIMERO-EL-MEJOR)
> (primero-el-mejor 's 'f)
1. Trace: (PRIMERO-EL-MEJOR 'S 'F)
2. Trace: (PRIMERO-EL-MEJOR 'S 'F '((A S) (D S)))
3. Trace: (PRIMERO-EL-MEJOR 'S 'F '((B A S) (D A S) (D S)))
4. Trace: (PRIMERO-EL-MEJOR 'S 'F '((C B A S) (E B A S) (D A S) (D S)))
5. Trace: (PRIMERO-EL-MEJOR 'S 'F '((E B A S) (D A S) (D S)))
6. Trace: (PRIMERO-EL-MEJOR 'S 'F '((F E B A S) (D E B A S) (D A S) (D S)))
6. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
5. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
4. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
3. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
2. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
1. Trace: PRIMERO-EL-MEJOR ==> (S A B E F)
(S A B E F)