4 votos

Contar el número de caminos a través de un grafo cuadriculado que atraviesa todos los vértices exactamente una vez

Así que hice una pregunta en stack overflow y me sugirieron que migrase hacia aquí. Estoy escribiendo un programa para resolver el siguiente problema:

Dada una cuadrícula de dimensiones x por y, calcula el número de caminos que la atraviesan y que comienzan en una esquina (digamos que arriba a la derecha) y terminan en otra (abajo a la derecha) y pasan por cada vértice exactamente una vez

He estado forzándolo pero se vuelve lento rápidamente y la gente en StackOverflow dijo que ni siquiera necesitaba molestarme con el traversal, y que esto era sólo un problema matemático. ¿Alguien tiene alguna idea de cómo podría resolverlo de esta manera?

1voto

Max Puntos 16

Ahí está el papel " El número de trayectorias hamiltonianas en una cuadrícula rectangular ", que da funciones generadoras para $m \times n$ rejillas con $m \leq 5$ . Por lo demás, parece un problema difícil.

0voto

user54230 Puntos 11

Aquí hay un vídeo "educativo" que intenta responder a una pregunta similar:

http://youtu.be/Q4gTV4r0zRs

Además, creo que es una excelente pregunta de informática (es decir, las matemáticas no están preparadas para problemas tan duros, lol).

Aquí es que tu pregunta se utiliza como un reto de programación. Supongo que una buena respuesta informática implica una búsqueda (en profundidad) de fuerza bruta con una poda inteligente en el camino.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X