Para formalizar un problema se sugieren los siguientes puntos:
- El espacio de estados, es decir, el conjunto de todos los estados válidos posibles que cumplen con las restricciones del problema.
- La representación de los estados es consistente: la variable que define el estado inicial contiene los mismos elementos que la del estado objetivo.
- Los operadores específicos son en base a las variables representadas.
- El estado inicial puede ser una configuración cualquiera de las variables en caso de no tener una determinada.
- Los estados corresponden a estructuras de datos del programa.
- Los operadores se encargan de modificar con algoritmos las estructuras de datos.
- Completo significa que se representan todos los estados posibles. No redundante, que se eliminan ciclos.
- Los elementos esenciales de un nodo son: estado, profundidad, operador que lo creó y su nodo padre.
En el ejemplo de la búsqueda de un número telefónico teniendo el nombre y apellido de la persona a buscar, en clase se planteó lo siguiente:
Estado inicial: Directorio, Nombre, Apellido
Operadores: Cambiar directorio, verificar directorio, buscar en índice, ir a página, cambiar página, buscar en página, comparar apellido y nombre.
Estado objetivo: Directorio, Nombre, Apellido y número conocidos.
Costo de la ruta: Cuántas veces se cambió de directorio o página.Como podemos observar, el número de variables en el estado inicial no concuerda con las variables del estado objetivo, por lo que tenemos un primer problema. Como siguiente observación, nos podemos dar cuenta que los operadores son muy generales y no están completos y/o correctos. Tenemos que recordar que los operadores deben ser lo más claros y específicos posibles.
Como segundo ejemplo se expuso la resolución del cubo de rubik, teniendo lo siguiente:
-Estado inicial: 6 caras cada una con una combinación de 9 bloques con un máximo de 6 distintos colores.
*6 matrices de 3x3, cada una con 4 matrices adyacentes donde cada celda es de un color.
-Operadores: Giro de 90° hacia la derecha, izquierda, arriba o abajo.
*Girar una cara 90°
-Estado objetivo: Cada cara del cubo tiene que tener todos los bloques del mismo color.
*Todas las celdas de cada matriz deben tener sólo un color.
-Costo de la ruta: Número de movimientos realizados hasta llegar al estado objetivo.
En este caso se corrigió cada uno de los puntos expuestos arriba, de modo que las líneas que comienzan con asteriscos (*) indican la corrección de cada parte de la formulación de este problema. De nuevo, los operadores deben ser lo más específicos posibles pero también se deben minimizar en la medida de lo posible, como fue el caso de este planteamiento.
