рекурсивный обход по графу, считая пути к точке

Question

Получил график, который выглядит следующим образом:

Я хочу посчитать все возможные пути к конкретной точке p (i, j) из p (0,0) на этом графике. Я думаю, что могу сделать это с помощью поиска в глубину. Как мне расширить поиск в глубину, чтобы он не учитывался дважды?

Answer 1

Вы можете использовать BFS и либо отмечать узлы, либо использовать карту для отслеживания их.Однако, если ваш граф большой, BFS влечет за собой хранение всего этого в памяти.DFS лучше у него.Однако DFS может потеряться на большом графике, если вы не наложите на него ограничение по глубине.

В любом случае, чтобы ускорить выполнение вашей программы, вы можете остановить ее раньше, если:

• графикотключен
• вы достигаете моста

Другие эвристики:

• сначала посетите соседа степени 1, прежде чем идти дальше.

Я написал несколько похожую программу, чтобы посмотреть, насколько я могу ее оптимизировать: https://github.com/eamocanu/allPathsFinder

Answer 2

Лучший способ - это подсчитать количество путей, фактически не следуя всем путям. Пусть F(x, y) будет количеством способов добраться до пункта назначения. Затем вы можете увидеть это на своем графике F(x, y) = F (x+1, y) + F (x, y+1) + F(x+1, y+1). Вы хотите F(0,0). Ваши базовые случаи будут F(i, j) = 1 (один из способов попасть туда, если вы уже там: никуда не ходите) и F(any number > i, any j) and F(i, any number > j) = 0, потому что нет способа добраться до пункта назначения после того, как вы его пройдете.

Обновление с более подробной информацией : Теперь, как оценить эту формулу? Вы можете сделать это рекурсивно, но наивная реализация будет крайне неэффективной. Наивной реализацией будет просто что-то вроде этого в псевдокоде, который выглядит примерно как python:

i = ...
j = ...
def paths (x, y):
    if (x > i) or (y > j):
        return 0         
    if (x == i) and (y == j):
        return 1
    else:
        return paths (x+1, y) + paths (x, y+1) + paths (x+1, y+1)
print F(0, 0)

Проблема в том, что если вы начнете с (0,0), ваш первый уровень рекурсивных вызовов будет (0, 1), (1, 0) и (1, 1). Когда эти вызовы в свою очередь оценят, (0, 1) вычислит (0, 2) (1, 1) и (1, 2); тогда (1, 0) вычислит (1, 1), (2, 0) и (2, 1), а затем (1, 1) вычислит (1, 2), (2, 1) и ( 2, 2). Обратите внимание, сколько из этих вызовов являются избыточными, поскольку они вычисляют одно и то же значение. Чтобы решить эту проблему, нужно сохранить матрицу, которая запоминает значения F. Тогда код может выглядеть примерно так:

i = ...
j = ...
memorizedValues = ... #make an i by j grid filled with -1
memorizedValues[i][j] = 1 #initial condition

def paths (x, y):
    if (x > i) or (y > j):
        return 0
    if (memorizedValues[x][y] != -1): #check for a memorized value before
        return memorizedValues[x][y] # starting more recursion!
    else:
        memorizedValues[x][y] = paths (x+1, y) + paths (x, y+1) + paths (x+1, y+1)
        return memorizedValues[x][y]

print F(0, 0)

Это все еще не самая эффективная реализация, но я думаю, что суть в этом. Это значительно быстрее, чем считать каждый путь, следуя по нему и возвращаясь назад!