2.4 Cómo Inventar Heurísticas

Para el 8-puzzle, es más o menos fácil convencer que la heurística que cuenta las distancias Manhattan entre cuadros y sus lugares es una buena heurística.

Lo más sorprendente es que la estimación y el convencimiento es por que cumple $h(n) \leq h^*(n)$, donde $h^*(n)$ la cual desconocemos (por eso hacemos la estimación).

Muchas veces el costo de una solución exacta para un problema con menos restricciones o simplificado (relaxed) es una buena heurística para el problema original.

La mayoría de las heurísticas no sólo son admisibles sino también consistentes.

Por ejemplo, podemos usar la notación de STRIPS para representar movimientos (ver tabla 2.13).

Tabla 2.13: La accción de mover un cuadro en el 8-puzzle usando notación de Strips.

Si eliminamos las condiciones: LIBRE(CuadroZ), ADY(CuadroY,CuadroZ) nos queda un problema en donde cada cuadro se puede mover a cualquier otro. El número requerido de pasos para resolver este problema es igual al número de cuadros que no están en su lugar ($h_1$).

Si sólo eliminamos LIBRE(CuadroZ), corresponde a intercambiar dos cuadros y nos dá la heurística $h_2$.

Si eliminamos sólo ADY(CuadroY,CuadroZ), nos dá otra heurística que se introdujo 13 años después de las otras dos.

Si queremos añadir más posibilidades, lo que tenemos que hacer es expresar las relaciones, tales como $ADJ$ en más simples, eg., VECINOS y MISMA-LINEA.

Eliminando una de las dos, dá nuevas heurísticas.

Por ejemplo un programa ABSOLVER se escribió para generar automáticamente heurísticas usando varios métodos. Generó nuevas heurísticas para el 8-puzzle mejores que las existentes y encontró una heurística útil para el cubo de Rubik.

Sólo hay que tener cuidado, a veces el problema resultante de eliminar restricciones, puede ser más difícil de resolver.

Si tenemos un conjunto de heurísticas admisibles lo mejor es hacer: $h(n) = max(h_1(n), \ldots, h_m(n))$ con lo cual $h$ domina a todas.

Otra forma de inventar heurísticas es usando información estadística. Por ejemplo, si observamos que casi siempre que nuestra heurística nos da un cierto valor, la distancia real es otra, podemos usar ese otro valor. Esto deja de garantizar la admisibilidad, pero puede dar en promedio muy buenos resultados.

Los estimadores (e.g., $h$ en A$^*$), puede ser un estimador estadístico y se pueden utilizar técnicas de muestreo estadístico.

Otra forma es escoger un conjunto de atributos que puedan contribuir al cálculo de la función de evaluación. Para ésto, podemos usar un algoritmo de aprendizaje que aprenda los coeficientes adecuados de estos atributos.

Hemos asumido que el costo de cálculo de una heurística es aproximadamente el mismo que el costo de expander un nodo. Pero si el costo es mucho mayor, se tiene que reconsiderar.