En el capítulo sobre representación del conocimiento, cuando hablamos de sistemas de producción vimos a la resolución de problemas como un proceso de búsqueda en un espacio de estados y discutimos dos estrategias de control: forward y backward. Ahora discutiremos más en profundidad las diversas formas de utilizar la búsqueda para la solución de problemas.
Definición de problema: El primer aspecto a considerar para definir a un problema es el espacio de estados (el conjunto de todos los estados alcanzables a partir de un estado inicial). El espacio de estados está definido por un estado inicial y un conjunto de acciones posibles. Otro de los elementos para la definición de un problema es la condición de solución, la cual se establece como una propiedad que debe cumplir un estado. En el juego del TATETI la condición de solución determina que el estado final del juego es aquel en el cual están alineadas tres fichas del mismo color (o tres cruces/círculos).
Podemos entonces asociar un problema a un grafo donde cada nodo es un estado y las acciones se representan mediante arcos o ejes conectando los estados/nodos.
Existen casos en los cuales no todas las soluciones son igual de buenas, por ejemplo tomemos el problema de ir de una ciudad a otra mediante carreteras interconectadas. En la figura vemos un grafo que representa la abstracción de dicho problema.
Grafo representando un problema
Los nodos denotan ciudades {A,B,C,D,E,F} y los arcos denotan rutas entre ellas. Claramente existen varias soluciones posibles al problema de ir de A hasta E. Una solución será {A, B, E} es decir ir primero a B y de B ir a E, otra solución es {A, C, D, E }. ¿Cuál es la mejor?. Eso depende de lo que se entienda por mejor. Si queremos minimizar el trayecto entonces habrá que tomar en cuenta las distancias entre las ciudades y ver cual camino es el más corto. Pero si queremos minimizar tiempo entonces debemos ver por que camino se llega primero (un camino puede ser corto pero no estar completamente asfaltado, lo cual hace que sea más lento circular por él mientras otro más largo puede tener autopistas que haga rápida la circulación).
Básicamente estamos hablando del costo del camino, el cual nos permite elegir entre varias soluciones, a aquella de menor costo.
Definimos el costo del camino como una función g que asigna un costo a una ruta determinada. Se considera que el costo del camino es la suma de los costos de cada una de las acciones individuales.
Existe otro costo que es el costo computacional asociado a la búsqueda(tiempo de procesamiento y memoria necesaria). El costo total de la búsqueda es el costo del camino más el costo computacional. En muchos problemas es posible encontrar un camino de costo mínimo pero el costo computacional de encontrarlo es tan grande que vuelve imposible utilizarlo.