递归遍历低谷的图形，计算的方式来点

Question

有一个图是看起来像这样的：

我想指望从对所有可能的方式，以一个特定的点P（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可能会丢失在大图中。

总之，加快你的程序，你可能会考虑停止早期如果：

• 图是不
• 你达到一个桥梁

其他启发式：

• 先访问1级的邻居，然后再继续。

我写了一个有点类似程序，看看我到底能优化它： https://github.com/eamocanu/allPathsFinder