Características de un problema resoluble con backtracking

La  solución puede expresarse como una n-tupla,

 (x1,x2,x3,…,xn) 

donde cada xi es seleccionado  de  un  conjunto finito Si.

El  problema se  puede formular como la  búsqueda de  aquella tupla que optimiza (maximiza o  minimiza) un  determinado criterio P(x1, ...,xn).

Algoritmo Genérico de Backtracking:

Bt(A, k)

1          if Solucion?(A, k)

2          then procesarSolucion(A, k)

3          else for each c ∈ Sucesores(A, k)

4          do A[k] = c

5          Bt(A, k + 1)

6          if terminar?

7          then return

Donde:

• Solucion?(·) es una función que retorna verdadero si su argumento es una solución.

• procesarSolucion(·), depende del problema y que maneja una solución.

• Sucesores(·) es una función que dado un candidato, genera todos los candidatos que son extensiones de éste.

• terminar? es una variable global booleana inicialmente es falsa, pero que puede ser hecha verdadera por procesarSolucion, en caso que sólo interesa encontrar una solución.