Como hemos visto para el algoritmo A*, y esto también aplica para otros algoritmos de búsqueda informada, las características de la heurística definen tanto la calidad de la solución como el desempeño del algoritmo en términos de cuántos recursos computacionales consume. ¿Pero de dónde vienen las heurísticas? Una manera de proponer una heurística es imaginar una versión relajada del problema original. Esto es, quitar algunas de las restricciones e imaginar que la gente puede tomar acciones que en el problema original no se podían tomar. A partir de estas acciones, estimar el costo a la meta u objetivo. [MÚSICA] En el ejemplo de encontrar rutas en un mapa, consideramos la distancia en línea recta como una buena heurística. En este mapa vemos que la restricción para un vehículo es moverse sobre el sistema carretero. Esta ruta está alejada de la línea recta. Si quitamos esta restricción, estamos considerando que la gente puede viajar en línea recta. A pesar de que esto no es cierto en la realidad, esta heurística es una buena aproximación respecto del costo a la meta. Cumple, además, con el criterio de que es fácilmente computable. Como en el mejor de los casos la carretera es una recta entre los puntos de interés, en un espacio euclídeo esta heurística es consistente y admisible. Otro ejemplo donde podemos ilustrar cómo proponer una heurística relajando las restricciones del problema original, es el juego del rompecabezas del ocho. La restricción del juego solo permite el movimiento de las fichas adyacentes al espacio libre. En esta configuración, son las fichas siete y ocho. Al quitar esta restricción, podemos considerar que las fichas se pueden mover, no importando si están adyacentes al espacio o no. Aquí, para llegar a la meta, las seis fichas se podrían mover. Por ejemplo, la ficha cuatro debe moverse una casilla hacia abajo para llegar a su posición deseada en la configuración final. La heurística entonces se define como el número de movimientos sin restricción necesarios para alcanzar la meta. Para la ficha cuatro, es un movimiento. Para la ficha uno, también es un movimiento. Acumulamos los movimientos de todas las fichas para calcular una distancia del estado inicial al final. Esta distancia que considera movimientos únicamente horizontales y verticales, pero no diagonales, se conoce como distancia de Manhattan. En nuestro ejemplo, la distancia es seis. La distancia de Manhattan es una heurística que no sobrestima. Adicionalmente, cumple con el requerimiento de que es computacionalmente poco costosa de calcular. Sin embargo, es más costosa de calcular que simplemente contar las fichas fuera de lugar. ¿Nos conviene este costo adicional? Denotemos como h1 la heurística que cuenta el número de fichas fuera de lugar y como h2 la heurística que calcula la distancia de Manhattan a la meta. Para la configuración mostrada, el valor de h1 es cinco, el valor de h2 es seis. Podemos ver que la diferencia radica en que la ficha dos tiene que moverse dos veces para llegar a la configuración deseada, una a la derecha y otra hacia arriba. Si las heurísticas dan valores diferentes para la misma configuración, ¿cuál podemos considerar como la mejor? Para responder a esta pregunta no solo hay que tomar en cuenta el costo de calcular la heurística, sino también qué tan buena es la estimación de la función. Ambas heurísticas no sobrestiman. Esto quiere decir que las estimaciones se mantienen por debajo del costo real. La más cercana al costo real debe ser la que nos entregue un valor más grande. En este caso, la distancia de Manhattan nos da una mejor aproximación del costo estimado para llegar a la meta. Esto nos permite plantear una manera de incorporar varias heurísticas en una nueva heurística más informativa. Si tenemos n heurísticas distintas, todas ellas admisibles, proponemos una heurística nueva que calcule el máximo de los valores resultantes de aplicar cada heurística a un estado. Pero hay que tener cuidado. En este ejemplo es claro que la heurística h2 siempre nos entregará un estimado mayor o igual al de la heurística h1. Por lo tanto, es infructuoso calcular ambas. Nos quedaremos con la distancia de Manhattan. Consideremos ahora el cubo de Rubik. También para el cubo podemos definir una heurística basada en la distancia de Manhattan en tres dimensiones. Sin embargo, esta heurística es poco informativa. Para observar la razón, veamos qué sucede si aplicamos una acción al cubo ordenado. Digamos que lo rotamos 90 grados. En esta figura vemos, del lado derecho, dos configuraciones posibles si rotamos el cubo una vez. Hemos aplanado las caras para poder verlas simultáneamente. Hay que imaginar que el cubo se obtiene doblando 90 grados en cada unión de las caras. Observamos que se desacomodan ocho subcubos. Si definiéramos la distancia como el número de subcubos fuera de lugar, esto resultaría en una heurística que sobrestima el valor real. En este caso, solo se realizó un movimiento. Es decir, tenemos un costo real de uno. Para hacer la heurística de Manhattan en tres dimensiones una heurística admisible, se tendría que dividir el valor entre ocho. Con ayuda de las supercomputadoras de Google, Tomas Rokicki demostró en 2010 que la distancia máxima a la que pueden estar dos configuraciones del cubo es 20, cuando se consideran como acciones rotaciones de las caras de 90 y 180 grados. Si tenemos un total de 26 subcubos, de los cuales los seis subcubos centrales de cada cara no pueden moverse, podemos ver que 20 entre ocho nos daría una distancia máxima de 2.5. Esta heurística es muy mala, pues está muy alejada del valor máximo esperado que es 20. Richard Korf propone tomar solo algunos subcubos, por ejemplo, los de las esquinas, o los de las orillas de en las cruces. Tomándolos de las orillas, la distancia a Manhattan se divide entre cuatro y el valor esperado de distancia es de 5.5. Esto sigue siendo malo para guiar a los algoritmos informados en un espacio de más de 43 trillones de configuraciones. Korf propone el uso de bases de datos de patrones, una idea desarrollado por Culberson y Schaeffer en 1996 para el rompecabezas del 15. La idea es simple, partiendo de la configuración meta, hay que realizar una búsqueda tipo BFS y observar cada configuración descubierta y poner atención solo a un subconjunto de los subcubos. Por ejemplo, aquí ponemos atención solo a los subcubos de las esquinas. Guardamos en una base de datos el patrón descubierto junto con la profundidad mínima a la que se encontró dicho patrón. Como vemos en la figura, el patrón con los subcubos azules en las esquinas captura todos los estados en los que esto es posible. Las configuraciones mostradas, todas tienen el mismo patrón de esquinas. Aquí mostramos un segundo patrón. Ahora nos fijamos en los cubos de las orillas, los que forman la cruz. Al descubrirse este patrón de orillas azules, el algoritmo tipo BFS guardará el patrón junto con su profundidad. La profundidad servirá para todo estado que exhiba el patrón, un conjunto muy grande de estados. Por construcción, esta heurística es admisible. Resumiendo. Muchas veces podemos proponer una heurística relajando las restricciones del problema y calculando una distancia de los estados la nodo meta. Podemos combinar varias heurísticas utilizando la función máximo sobre el resultado de aplicar cada una de ellas a un estado. Las heurísticas deben poder calcularse de manera eficiente, porque vamos a evaluar la heurística de cada nodo descubierto. Se pueden estimar los costos mínimos de un conjunto de estados descritos por un patrón y ser almacenados en una base de datos. Finalmente los agentes pueden incorporar técnicas de aprendizaje máquina para proponer heurísticas de manera automática. [MÚSICA] [MÚSICA]
