Trazado gráfico de n pasos
Dado un gráfico simple no dirigido como este:
A partir de D, A, B o C (V_start
) —Tengo que calcular cuántas rutas posibles hay desde el punto de inicio (V_start
) al punto de partida (V_start
) den
pasos, donde cada borde y vértice se pueden visitar una cantidad ilimitada de veces.
Estaba pensando en hacer una primera búsqueda profunda, deteniéndome cuandosteps > n || (steps == n && vertex != V_start)
Sin embargo, esto se vuelve bastante costoso si, por ejemplo,n = 1000000
. Mi siguiente pensamiento me llevó a combinar DFS con programación dinámica, sin embargo, aquí es donde estoy atascado.
(Esto no es tarea, solo me quedo atascado jugando con gráficos y algoritmos para aprender).
¿Cómo voy a resolver esto en un tiempo razonable con una grann
?