algo

backtraking

* Introducción
* La vuelta del caballo
* El problema de las ocho reinas
* El problema de la mochila (selección óptima)
* Problemas propuestos
 
Introducción
Los algoritmos de vuelta atrás se utilizan para encontrar soluciones a un problema. No siguen unas reglas para la búsqueda de la solución, simplemente una búsqueda sistemática, que más o menos viene a significar que hayque probar todo lo posible hasta encontrar la solución o encontrar que no existe solución al problema. Para conseguir este propósito, se separa la búsqueda en varias búsquedas parciales o subtareas. Asimismo, estas subtareas suelen incluir más subtareas, por lo que el tratamiento general de estos algoritmos es de naturaleza recursiva.
¿Por qué se llaman algoritmos de vuelta atrás?. Porque en elcaso de no encontrar una solución en una subtarea se retrocede a la subtarea original y se prueba otra cosa distinta (una nueva subtarea distinta a las probadas anteriormente).
Puesto que a veces nos interesa conocer múltiples soluciones de un problema, estos algoritmos se pueden modificar fácilmente para obtener una única solución (si existe) o todas las soluciones posibles (si existe más deuna) al problema dado.
Estos algoritmos se asemejan al recorrido en profundidad dentro de un grafo (ver sección de grafos, estructuras de datos, y recorrido de grafos, algoritmos), siendo cada subtarea un nodo del grafo. El caso es que el grafo no está definido de forma explícita (como lista o matriz de adyacencia), sino de forma implícita, es decir, que se irá creando según avance el recorrido. Amenudo dicho grafo es un árbol, o no contiene ciclos, es decir, al buscar una solución es, en general, imposible llegar a una misma solución x partiendo de dos subtareas distintas a y b; o de la subtarea a es imposible llegar a la subtaréa b y viceversa.
Gráficamente se puede ver así:

 
A menudo ocurre que el árbol o grafo que se genera es tan grande que encontrar una solución o encontrar lamejor solución entre varias posibles es computacionalmente muy costoso. En estos casos suelen aplicarse una serie de restricciones, de tal forma que se puedan podar algunas de las ramas, es decir, no recorrer ciertas subtareas. Esto es posible si llegado a un punto se puede demostrar que la solución que se obtendrá a partir de ese punto no será mejor que la mejor solución obtenida hasta el momento.Si se hace correctamente, la poda no impide encontrar la mejor solución.
A veces, es imposible demostrar que al hacer una poda no se esté ocultando una buena solución. Sin embargo, el problema quizás no pida la mejor solución, sino una que sea razonablemente buena y cuyo coste computacional sea bastante reducido. Esa es una buena razón para aumentar las restricciones a la hora de recorrer unnodo. Tal vez se pierda la mejor solución, pero se encontrará una aceptable en un tiempo reducido.
Los algoritmos de vuelta atrás tienen un esquema genérico, según se busque una o todas las soluciones, y puede adaptarse fácilmente según las necesidades de cada problema. A continuación se exponen estos esquemas, extraídos de Wirth (verBibliografía). Los bloques se agrupan con begin y end,equivalentes a los corchetes de C, además están tabulados.
- esquema para una solución:
procedimiento ensayar (paso : TipoPaso)
  repetir
  |  seleccionar_candidato
  |  if aceptable then
  |  begin
  |    anotar_candidato
  |    if solucion_incompleta then
  |    begin
  |      ensayar(paso_siguiente)
  |      if no acertado then borrar_candidato
  |    end
  |    else begin  |      anotar_solucion
  |      acertado = 0 && u < N && v >= 0 && v < N) { /* esta dentro de los limites? */
if (tablero[u][v] == 0) { /* es valido? */
tablero[u][v] = i; /* anota el candidato */
if (i < ncuad) { /* llega al final del recorrido? */
mover(tablero,i+1,u,v,q);
if (!*q) tablero[u][v] = 0; /* borra el candidato */
}
else *q = 1;...