En una representación basada en estados el proceso de solución trata de encontrar una secuencia de operaciones que transformen al estado inicial en uno final.
Reducción de problemas implica que los subconjuntos candidatos se pueden ver como una conjunción de varios subproblemas a resolver.
En general, si la solución puede especificarse como un camino o un estado, la representación basada en estados es más adecuada.
Por otro lado si la solución es más conveniente representarla como un árbol, entonces una representación de reducción de problemas o gráfo es más adecuada.
Las estrategias se representan mejor si los arcos AND representan cambios ocasionados por situaciones externas y las OR son formas alternativas de reaccionar ante esos cambios.
Otro tipo de problemas susceptibles de ser representados por gráfos AND/OR son los que su solución es una secuencia parcialmente ordenada de acciones (v.g., integración simbólica, pueba de teoremas, las torres de Hanoi).
En particular el problema de las torres de Hanoi, puede ser fácilmente representado como un espacio de estados. Sin embargo, las metas poseen una jerarquía lineal. Una vez resuelto el pasar varios de los discos más grandes, los demás se pueden resolver sin alterar las metas obtenidas.
La clave está en empezar con la meta más crítica (mover el disco más grande a su lugar). Lo cual implica moverlo y mover todos los discos arriba de él a otro poste.
Las metas serían:
discos al poste intermedio
al poste meta
discos al poste meta
En principio la búsqueda de las soluciones puede hacerse de manera independiente. Este plan abstracto puede seguirse aplicando a los siguientes niveles hasta llegar a acciones primitivas.
Algo que tenemos que considerar es cómo encontrar una buena heurística? Cómo usarla para que sea más efectiva? Cómo evaluar sus méritos? Parte de los objetivos del curso es ayudar a contestar estas preguntas.