遞歸遍歷低谷的圖形，計算的方式來點

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