La representación que se usa para caracterizar un problema es fundamental para su solución.
Los requerimientos necesarios para una representación de un problema de búsqueda son:
La estrategia de control se dice sistemática si considera todos los posibles caminos (completa), y no explora un objeto más de una vez (eficiente).
La representación debe de ser capaz de representar los objetos de trabajo (caminos, tableros, estrategias).
Es deseable poder representar también subconjuntos de objetos o de soluciones potenciales, ya que nos permite eliminar espacios de búsqueda grandes.
Idealmente también debemos de tener tranformaciones entre estos subespacios de búsqueda.
Una de las más usadas es la de dividir el espacio en subconjunto de soluciones potenciales.
Los candidatos que mostramos en el ejemplo de las 8 reinas, nos dividen el espacio en 3 espacios mutuamente exclusivos (las demás alternativas no se tienen que considerar porque no nos llevan a ninguna solución).
Un tablero parcialmente ocupado nos representa un subconjunto de soluciones potenciales. El añadir una nueva reina, nos refina el espacio.
Es esta habilidad de detectar y eliminar o cortar grandes subconjuntos de búsqueda que hacen que el problema sea fácil de resolver.
Si no, considere resolver el probelma poniendo las reinas en una configuración aleatoria y perturbarla hasta dar con la solución (aunque si se ha hecho con buenos resultados para tableros muy grandes). En esta representación sí se tienen representados los objetos individuales, pero no sus subconjuntos. Por lo que podemos eliminar elementos, pero no subconjuntos.
En el 8-puzzle no se ve claro como eliminar subconjuntos, ya que en principio uno puede regresarse al camino anterior. Claro que si ponemos restricciones en la longitud máxima permitida (L) del camino, podemos eliminar todos aquellos que sean mayores a L.
El estimar en forma temprana caminos sin salida a veces requiere de heurísticas que explotan información que no está explícita en la formulación del problema (v.g., 8-reinas).
El uso de heurísticas imponen requerimientos adicionales en el formato de representación. La representación debe de identificar adecuadamente los subconjuntos y facilitar el cálculo de la heurística.
Por ejemplo, podemos jugar con un contrincante a seleccionar digitos en forma alternada, tratando de encontrar tres digitos que sumen 15. Si se usa un cuadro mágico y se juega gato el juego es trivial.
En muchos casos es deseable incluir dentro de la representación información adicional que nos defina el subpoblema que falta por resolver. El código que especifica ésta información adicional se llama un estado.
El conjunto de todos los subproblemas obtenidos de ejecutar alguna secuencia de operadores de refinamiento se llama un espacio de estados.
La importancia de representar los subproblemas que faltan es que muchas veces éstos: (i) se repiten y podemos aprovechar las experiencias obtenidas o (ii) podemos juzgar que opción es mejor de dos si las dos tienen el mismo espacio faltante y una de ellas es superior a la otra.
El problema de las monedas introduce un nuevo elemento, la estrategia.
La estrategia nos debe de decir qué acción tomar en respuesta a cualquier evento externo, que puede ser el resultado de una prueba, la movida de un oponente, el resultado de un cálculo complicado.
Ahora lo que buscamos, en lugar de caminos, son árboles.
En este caso se tiene una representación en donde los subproblemas candidatos se pueden resolver independientemente de los otros.
Esto sugiere que los subproblemas sean considerados como nodos individuales, resueltos independientemente, guardarlos y usados en el resto de la estrageia.
Un código adecuado es el de gráfos AND/OR.
Los gráfos tienen dos tipos de arcos:
En general, las ligas AND y OR pueden apuntar simultaneamente al mismo nodo. Por otro lado, un nodo puede tener salidas AND y OR. En este caso es conveniente crear un nodo AND artificial.
Como (casi) siempre, el representar el árbol de búsqueda completo es imposible en memoria. Una buena estrategia trata de encontrar una solución explorando sólo una pequeña porción del gráfo.
Algo común es etiquetar los nodos como resueltos (no resueltos). Las reglas de etiquetación son las siguientes:
