Según la Wikipedia (en inglés), la expresión explosión combinatoria describe el efecto de funciones que crecen muy rápidamente como resultado de consideraciones combinatorias. En este vídeo vamos a ver un ejemplo muy descriptivo de este concepto.
La cuestión es sencilla: trata simplemente de contar los caminos mediante los que podemos llegar desde vértice superior izquierdo hasta el inferior derecho en una cuadrícula dependiendo de la complejidad de dicha cuadrícula. Vamos a ver algún ejemplo.
Si la cuadrícula tiene un único cuadrado, como ésta
¿cuántos caminos distintos pueden escogerse para llegar de A a B? Pues claramente dos, ¿verdad? Son estos:
 |
 |
Bien, ¿y si ahora tenemos una cuadrícula con 4 cuadrados como ésta?
¿Cuántas formas distintas habría ahora de llegar del punto A al punto B? Pues exactamente son 12, las siguientes:
Y podríamos continuar preguntándonos cómo iría creciendo ese número de caminos conforme aumentamos el tamaño de la cuadrícula. Por ejemplo, con 9 cuadrados
el número de caminos pasa a ser 184. Gran salto en número…y en tiempo de cálculo, claro está.
Para ver cuántos caminos tendríamos para una cuadrícula mayor que ésta os recomiendo que le echéis un ojo al vídeo:
Por cierto, la sucesión formada por estos números de caminos es la A007764 en la OEIS.
Vía la cuenta de Twitter de @mezvan. Si todavía no lo sigues ya estás tardando.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Esta Excelente este Video y más la información, me gusto ya que me inclino por la matemática aplicada. lo Máximo lo compartire
Con los valores conocidos de la serie parece que tiene una ley de crecimiento parecido al de la función a(n) = 10^((n/2)^2)
Muy buen vídeo. Con ese toque oriental que tanto apasiona (y desorienta) a occidente. Un detalle que me llama la atención es que en el vídeo la lectura de los números es en grupos de cuatro cifras, en vez de tres.
Información Bitacoras.com…
Valora en Bitacoras.com: Según la Wikipedia (en inglés), la expresión explosión combinatoria describe el efecto de funciones que crecen muy rápidamente como resultado de consideraciones combinatorias. En este vídeo vamos a ver un ejemplo muy de……
Los caminos tienen la restriccion de no pasar dos veces por el mismo lugar.
Yo estoy acostumbrado a la restriccion de que sean de longitud minima :p
O sino que sean de longitud minima y no pasen por la diagonal.
http://es.wikipedia.org/wiki/N%C3%BAmeros_de_Catalan
Muy interesante para un ejercicio de programación, he posteado en Solveet.
Por otra parte, en A007764 comentan:
«Daniel Forgues, Jan 03 2011 (Start) For n=14, there exists at least one Hamiltonian path from (0,0) to (14,14). For which n do we have at least one Hamiltonian path?»
Sin embargo, parece obvio que para N impar siempre existe un camino de Hamilton (sin mas que zizaguear).
¿Qué no estoy viendo? ¡Gracias!
Hace muchos años, creo que en 1º de carrera, me pusieron un problema en un examen relacionado con este tema, pero limitando el Nº de caminos a diferentes caminos de longitud mínima.
Era una ciudad rectangular 9*6 y había que calcular cuantos caminos mínimos existian.
Con esta limitación el resultado disminuía drásticamente a 84
@josejuan
Para n caminos pares se hace asi:
http://imageshack.us/photo/my-images/9/caminos.png/
@Toppus entonces quedemos en es un toque desoriental 😛
@Luis, el dibujo que indicas tiene nodos impares (pero es culpa mía, usé «N impar» incorrectamente) y se resuelve simplemente zizgagueando.
Me refería a que Daniel (en oeis.org) pregunta:
«For which n do we have at least one Hamiltonian path?»
Él (Daniel) está presentando un caso con nº de nodos impar (N cuadros par), pero es trivial ver que para cualquier cuadrícula de nodos impares (N cuadros pares) hay un camino de hamilton.
Ah perdon, lo interprete como cantidad de cuadrados.
No se porque me confundi y pense que en la cantidad de cuadrados impar se podia hacer el zigzag normal y aca tenia que cambiarlo y hacer uno mas rebuscado.
Al final, por donde esta la solucion del problema…
Hay alguna manera de contar los caminos que no sea uno por uno o con computadoras????