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

Question

Есть график, который выглядит как этот:

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

Answer 1

Лучший способ - подсчитать количество способов, фактически не следуя всем путям. Пусть 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, потому что нет способа добраться до пункта назначения после его передачи.

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

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) 

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

Answer 2

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

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

• граф отсоединен
• вы достигнете моста

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

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

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