backtracking.md

Backtracking

Backtracking es un algoritmo general para resolver problemas de búsqueda completa, el cual usa la estrategia de abandonar soluciones candidatas si no puede ser posible que se vuelva una solución al problema.

Backtracking solo puede ser aplicable si el problema admite un parcial candidato de una solución.

Aun siendo un enfoque de busqueda completa, muchos algoritmos np son solucionables optima y exactamente con este enfoque. Entre ellos se encuentran problemas como sudoku, 8 reinas, covertura exacta, knapsack problem, etc.

C

Estructura del backtracking

def backtracking(params)
  if (not possibleSolution(params)) return //<-backtrack
  if (isSolution(params)) process(params)
  
  for (next in allPossibleNextState(params)) {
    backtracking(next)
  }

Problemas clasicos

knapsack problem:

Dado n objetos con peso w_i y valor v_i, y C la capacidad de una mochila. Imprimir con que objetos debo llenar la mochila de tal forma que su suma de pesos sea menor o igual a C y que al mismo tiempo maximize la suma de valores.

solucion:

vector<int> solution;
int maxValue = -1;

void backtracking(int pos, int C, int partialValue, vector<int>& partialSolution) {
  if (pos == n) {
      if (partialValue > maxValue) {
          maxValue = partialValue;
          solution = partialSolution;
      }
      return;
  }
  backtracking(pos + 1, C, partialValue, partialSolution); //<-- no tomar objeto
  if (C >= weight[pos]) {
    partialSolution.push_back(pos);
    backtracking(pos + 1, C - weigth[pos], partialValue + value[pos], partialSolution); //<-- tomar objeto
    partialSolution.pop_back();
  }
}

Esta solución genera un árbol de decisiones, cada elemento puede ser tomado o no tomado, cada nivel de la recursion tiene el doble de nodos que el nivel anterior. complejidad O(2^n).

8 queen problem

dado un tablero de ajedrez de 8x8, colocar 8 reinas de tal forma que no se ataquen entre si.

solucion.

bool ok = 0;
void backtracking(int col, vector<int> rows, vector<int> diag1, vector<int> diag2) {
  if (ok) return;
  if (col == 8) {
     ok = 1;
     for (int r : rows) cout << r << " "; cout << endl;
     return;
  }
  for (int i = 0; i < 8; ++i) {
    bool used = 0;
    for (int r : rows) if (r == i) {
      used = 1;
      break;
    }
    for (int d : diag1) if (d == col + i) {
      used = 1;
      break;
    }
    for (int d : diag2) if (d == abs(col - i)) {
      used = 1;
      break;
    }
    if (used) continue;
    rows.push_back(i);
    diag1.push_back(col + i);
    diag2.push_back(abs(col - i));
    backtrack(col+1, rows, diag1, diag2);
    rows.pop_back();
    diag1.pop_back();
    diag2.pop_back();
  }
 }

sudoku

dado una configuracion de un sudoku, mostrar una solucion si es que esta existe.

solucion

bool nextPosition(vector<vector<int>>& table, int& x, int& y) {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      if (table[i][j] == 0) {
        x = i; y = j;
        return 1;
      }
    }
  }
  return 0;
}

void backtrack(vector<vector<int>> table, set<int> rows[9], set<int> cols[9], set<int> cuad[3][3]) {
    int x, y;
    if (not nextPosition(x, y)) {
      for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
          cout << table[i][j] << " ";
        }
        cout << endl;
      }
      return;
    }
    
    for (int i = 1; i <= 9; ++i) {
      if (rows[x].count(i)) continue;
      if (cols[x].count(i)) continue;
      if (cuad[x/3][y/3].count(i)) continue;
      rows[x].insert(i);
      cols[y].insert(i);
      cuad[x/3][y/3].insert(i);
      backtracking(table, rows, cols, cuad);
      rows[x].erase(i);
      cols[y].erase(i);
      cuad[x/3][y/3].erase(i);
    }
}