График обхода n шагов
Имеется простой неориентированный граф, подобный этому:
Начиная с D, A, B или C (V_start
) & # x2014; Я должен рассчитать, сколько возможных путей существует от начальной точки (V_start
) к начальной точке (V_start
) изn
шаги, где каждое ребро и вершину можно посещать неограниченное количество раз.
Я думал о том, чтобы сделать первый глубокий поиск, останавливаясь, когдаsteps > n || (steps == n && vertex != V_start)
Однако это становится довольно дорого, если, например,n = 1000000
, Моя следующая мысль привела меня к объединению DFS с динамическим программированием, однако именно здесь я застрял.
(Это не домашнее задание, просто я застреваю, играя с графиками и алгоритмами ради обучения.)
Как бы я решил это в разумные сроки с большимn
?