Tema 49: Problemas combinatorios mediante algoritmos

1. Del problema matemático al algoritmo

Resolver un problema combinatorio comienza por definir con precisión qué objetos se cuentan, qué decisiones pueden tomarse y qué configuraciones son válidas.

Luego se diseña un procedimiento que genere todas las soluciones, cuente sus posibilidades o encuentre una solución que cumpla las restricciones.

2. Representar una solución

Una solución puede representarse como una cadena, una lista, un subconjunto, una permutación, un camino o una asignación.

La representación debe permitir agregar decisiones, deshacerlas y verificar rápidamente si el estado parcial todavía puede conducir a una solución válida.

3. Generación exhaustiva

La generación exhaustiva recorre todas las configuraciones del espacio de búsqueda. Es apropiada cuando el tamaño es pequeño, cuando se necesita una respuesta exacta o cuando se desea crear un programa de referencia.

function cadenasBinarias(n) {
  const resultado = [];
  function generar(prefijo) {
    if (prefijo.length === n) {
      resultado.push(prefijo);
      return;
    }
    generar(prefijo + "0");
    generar(prefijo + "1");
  }
  generar("");
  return resultado;
}

console.log(cadenasBinarias(3));

4. Backtracking

El backtracking construye una configuración parcial y retrocede cuando una elección ya no puede formar una solución válida. Su estructura general es:

1. Elegir una alternativa.
2. Agregarla al estado parcial.
3. Verificar restricciones.
4. Continuar o deshacer la elección.

5. Poda

La poda es una condición que evita explorar una rama completa. Cuanto antes se detecte que un estado es imposible, más pequeño será el número de configuraciones visitadas.

6. Ejemplo: permutaciones

Para generar permutaciones se elige un elemento que todavía no fue utilizado y se continúa con los restantes. Al completar la configuración se obtiene una solución.

function permutaciones(elementos) {
  const resultado = [];
  function generar(actual, usados) {
    if (actual.length === elementos.length) {
      resultado.push(actual.slice());
      return;
    }
    for (let i = 0; i < elementos.length; i++) {
      if (usados[i]) continue;
      usados[i] = true;
      actual.push(elementos[i]);
      generar(actual, usados);
      actual.pop();
      usados[i] = false;
    }
  }
  generar([], Array(elementos.length).fill(false));
  return resultado;
}

console.log(permutaciones(["A", "B", "C"]).length); // 6

7. Validación de restricciones

Una validación puede comprobar que no se repitan elementos, que dos valores no sean adyacentes, que una suma alcance un objetivo o que dos tareas no ocupen el mismo recurso.

Es preferible validar durante la construcción, en lugar de generar una solución completa y descartarla al final.

8. Programación dinámica

Cuando distintos caminos de decisión llegan al mismo subproblema, la programación dinámica almacena el resultado y lo reutiliza. La solución se define mediante:

• Estados que describen el subproblema.
• Casos iniciales.
• Transiciones entre estados.
• Orden de cálculo o memorización.

9. Ejemplo: suma de subconjunto

En el problema de suma de subconjunto se busca saber si algunos valores suman exactamente un objetivo. El estado puede ser la cantidad de elementos considerados y la suma alcanzada.

function existeSuma(valores, objetivo) {
  const posible = Array(objetivo + 1).fill(false);
  posible[0] = true;
  for (const valor of valores) {
    for (let suma = objetivo; suma >= valor; suma--) {
      posible[suma] = posible[suma] || posible[suma - valor];
    }
  }
  return posible[objetivo];
}

console.log(existeSuma([3, 4, 7, 10], 14)); // true

10. Conteo frente a decisión

Un algoritmo puede responder preguntas diferentes:

• Existencia: ¿hay al menos una solución?
• Conteo: ¿cuántas soluciones hay?
• Optimización: ¿cuál es la mejor solución?
• Enumeración: ¿cuáles son todas las soluciones?

El mismo modelo combinatorio puede adaptarse cambiando la información que se guarda en cada estado.

11. Algoritmos voraces

Una estrategia voraz toma la mejor decisión local disponible. Puede resolver algunos problemas de asignación o selección, pero necesita una justificación matemática para garantizar que no descarta la solución óptima.

Cuando no existe esa garantía, el backtracking o la programación dinámica suelen ser alternativas más seguras.

12. N-queens como modelo combinatorio

El problema de las n reinas consiste en colocar n reinas en un tablero n × n sin que dos compartan fila, columna o diagonal.

Una solución puede construirse asignando una columna por fila y podando cada posición que entre en conflicto con las reinas ya colocadas.

13. Implementación de una búsqueda con poda

El siguiente algoritmo cuenta las soluciones del problema de las n reinas. Las diagonales se identifican mediante la suma y la diferencia entre fila y columna.

function contarReinas(n) {
  let soluciones = 0;
  const columnas = new Set();
  const diagonales1 = new Set();
  const diagonales2 = new Set();
  function colocar(fila) {
    if (fila === n) {
      soluciones++;
      return;
    }
    for (let columna = 0; columna < n; columna++) {
      const diagonal1 = fila - columna;
      const diagonal2 = fila + columna;
      if (columnas.has(columna) ||
          diagonales1.has(diagonal1) ||
          diagonales2.has(diagonal2)) continue;
      columnas.add(columna);
      diagonales1.add(diagonal1);
      diagonales2.add(diagonal2);
      colocar(fila + 1);
      columnas.delete(columna);
      diagonales1.delete(diagonal1);
      diagonales2.delete(diagonal2);
    }
  }
  colocar(0);
  return soluciones;
}

console.log(contarReinas(4)); // 2

14. Simulación: tablero de n reinas

Elige el tamaño del tablero. La simulación cuenta las soluciones mediante backtracking y muestra una de ellas cuando existe.

15. Complejidad y límites

La cantidad de configuraciones puede crecer factorial o exponencialmente. Las restricciones, la poda y las estructuras auxiliares reducen la exploración, pero no siempre eliminan el crecimiento combinatorio.

16. Resumen

Los problemas combinatorios se resuelven definiendo estados, decisiones y restricciones. La generación exhaustiva sirve para espacios pequeños; el backtracking agrega poda; la programación dinámica reutiliza subproblemas. La combinación de conteo y algoritmos permite diseñar soluciones correctas y estimar sus límites.