Consiste en un proceso arduo donde la estrategia de resolución se construye mediante un trabajo mental mínimo. Este tipo de algoritmos prueban todas las combinaciones posibles para hallar la/las respuestas buscadas. Existen algunas metodologías:
Se pueden pensar como una serie de decisiones sobre la instancia del problema que modifica su estado, cuentan con un estado inicial, estados intermedios (diferentes elecciones que se van realizando que transforman a la instancia) y estado final (solución a la que llegamos luego del procedimiento).
Un estado puede permitir diferentes soluciones, diferentes soluciones nos llevan a diferentes estados y un mismo estado puede ser accedido desde otros estados. Llamamos un grafo de espacio de estados a esta representación del problema
Un mismo problema permite en la mayoría de las veces ser resuelto de diferentes formas, cada estrategia de resolución determina: la estructura y tamaño de este grafo, la forma en que se construye este grafo y la forma en que se recorre el mismo.
En un problema combinatorio tenemos N elementos con los cuales podemos conformar diferentes soluciones dependiendo de cómo los combinemos. Una posible solución puede ser expresada como una tupla de como mucho T ≤ N elementos (x_1, x_2, …, x_t). Existen un subconjunto de posibles soluciones que comienzan con los “T - 1” elementos iniciales y a su vez estos forman parte de un conjunto de soluciones que inician con los mismos “T - 2” elementos. Mediante un árbol de deciciones podemos representar una jerarquía en el espacio de soluciones.
