1. ¿Qué es un camino?
Un camino es una secuencia ordenada de posiciones o decisiones que lleva desde un punto inicial hasta uno final. En combinatoria, el objetivo suele ser determinar cuántos caminos diferentes existen.
El mismo concepto puede representar movimientos sobre una cuadrícula, estados de un algoritmo, conexiones de una red o pasos de un proceso.
2. Caminos en una cuadrícula
Consideremos una cuadrícula en la que solo se permite avanzar hacia la derecha o hacia abajo. Para llegar desde la esquina superior izquierda hasta una celda situada a r filas y c columnas hay que realizar r movimientos hacia abajo y c hacia la derecha.
Caminos = C(r + c, r) = C(r + c, c)
La fórmula surge de elegir qué posiciones de la secuencia de movimientos serán pasos hacia abajo; las restantes serán pasos hacia la derecha.
3. Ejemplo de caminos sin obstáculos
Para llegar a una celda ubicada a 2 filas y 3 columnas del origen se necesitan 2 pasos hacia abajo y 3 hacia la derecha. Por lo tanto:
C(5, 2) = 10
Existen diez recorridos diferentes.
4. Enumerar movimientos
Otra forma de interpretar el problema es formar cadenas con dos símbolos: D para bajar y R para avanzar a la derecha. Cada cadena con r símbolos D y c símbolos R representa un camino.
function caminosSinObstaculos(filas, columnas) {
const tabla = Array.from({ length: filas + 1 }, function () {
return Array(columnas + 1).fill(0);
});
for (let f = 0; f <= filas; f++) tabla[f][0] = 1;
for (let c = 0; c <= columnas; c++) tabla[0][c] = 1;
for (let f = 1; f <= filas; f++) {
for (let c = 1; c <= columnas; c++) {
tabla[f][c] = tabla[f - 1][c] + tabla[f][c - 1];
}
}
return tabla[filas][columnas];
}
console.log(caminosSinObstaculos(2, 3)); // 105. Recurrencia de caminos
Si af,c representa la cantidad de caminos hasta la celda (f, c), el último paso pudo venir desde arriba o desde la izquierda:
af,c = af-1,c + af,c-1
Los bordes de la cuadrícula tienen valor 1 porque solo existe un camino para llegar a ellos: avanzar siempre en la misma dirección.
6. Programación dinámica
La recurrencia genera muchos subproblemas repetidos si se calcula de forma recursiva. Una tabla permite guardar cada resultado y reutilizarlo cuando se necesitan caminos hacia otras celdas.
Este enfoque transforma una exploración potencialmente enorme en un algoritmo cuyo costo depende del número de celdas visitadas.
7. Caminos con obstáculos
Si una celda está bloqueada, ningún camino puede atravesarla y su cantidad de caminos se considera cero. Para las demás celdas se mantiene la misma recurrencia:
af,c = 0 si la celda está bloqueada.
af,c = af-1,c + af,c-1 en otro caso.
8. Implementación con obstáculos
function contarCaminos(mapa) {
const filas = mapa.length;
const columnas = mapa[0].length;
const tabla = Array.from({ length: filas }, function () {
return Array(columnas).fill(0);
});
if (mapa[0][0] || mapa[filas - 1][columnas - 1]) return 0;
tabla[0][0] = 1;
for (let f = 0; f < filas; f++) {
for (let c = 0; c < columnas; c++) {
if (mapa[f][c]) continue;
if (f > 0) tabla[f][c] += tabla[f - 1][c];
if (c > 0) tabla[f][c] += tabla[f][c - 1];
}
}
return tabla[filas - 1][columnas - 1];
}
console.log(contarCaminos([
[false, false, false],
[false, true, false],
[false, false, false]
])); // 29. Conteo mediante el complemento
Cuando hay un único punto obligatorio, puede ser más sencillo contar todos los caminos y restar los que pasan por una celda prohibida. Si el obstáculo está en (f, c), los caminos que lo atraviesan se calculan multiplicando:
caminos desde el inicio hasta el obstáculo × caminos desde el obstáculo hasta el final
10. Caminos que pasan por un punto
Para exigir que un camino pase por un punto intermedio, se divide el recorrido en dos tramos. El primer tramo llega al punto y el segundo sale de él.
Por el principio del producto, la cantidad total es el producto de las cantidades de ambos tramos, siempre que los movimientos permitidos sean compatibles.
11. Caminos con movimientos diferentes
Si además de avanzar y bajar se permiten movimientos diagonales, la recurrencia cambia. Por ejemplo, si se puede llegar a una celda desde arriba, desde la izquierda o desde la diagonal:
af,c = af-1,c + af,c-1 + af-1,c-1
La regla de conteo siempre debe reflejar exactamente los movimientos autorizados.
12. Recorridos en grafos
En un grafo, un recorrido es una secuencia de vértices y aristas. Si el grafo es acíclico y dirigido, el número de caminos entre dos vértices puede calcularse acumulando las cantidades de caminos que llegan desde sus predecesores.
Esta idea relaciona el conteo de caminos con el ordenamiento topológico y la programación dinámica.
13. Recorridos y estados de un algoritmo
Un problema puede modelarse como un grafo de estados: cada nodo representa una situación y cada arista una decisión posible. Contar caminos permite saber cuántas secuencias de decisiones llevan a un objetivo.
14. Simulación: cuadrícula con obstáculos
Configura una cuadrícula. La simulación coloca un obstáculo en el centro cuando el tamaño lo permite y calcula los recorridos que avanzan solo hacia la derecha o hacia abajo.
15. Verificación de resultados
Para verificar un conteo de caminos conviene analizar cuadrículas pequeñas, comparar con una enumeración explícita y revisar los casos límite. Una celda inicial o final bloqueada debe producir cero recorridos.
16. Resumen
El conteo de caminos transforma recorridos en problemas de enumeración. En cuadrículas, la recurrencia suma los caminos que llegan desde las posiciones anteriores; los obstáculos se modelan con valor cero. La misma técnica se extiende a grafos, estados de algoritmos, restricciones y programación dinámica.