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

我想指望從對所有可能的方式，以一個特定的點P（I，J）（0 ，0）。我想我可以用深度優先搜索來做到這一點。我應該如何擴展深度優先搜索，所以它不算兩次？謝謝！

2011-12-19 0xbadc0de

最好的方法是在沒有真正遵循所有路徑的情況下計算路數。讓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)

這仍然不是最有效的實現，但我認爲它得到跨點。這比通過跟蹤和回溯計算每條路徑快得多！

來源

2011-12-19 22:47:48 Gravity

感謝。我雖然關於這個解決方案，但需要遵循所有的方式，因爲我必須從邊緣讀取其他信息，導致一個特定的點。所以如果我只讀一次文件就不會存儲我不需要的信息，那會好很多。 – 0xbadc0de 2011-12-19 23:04:20

嗯...那麼我的更新解釋算法可能實際上並沒有用。那麼我真的不明白你想要解決什麼問題。爲什麼深度優先搜索會爲您提供重複路徑？ – Gravity 2011-12-19 23:18:07

您可以使用BFS並標記節點或使用地圖來跟蹤它們。但是，如果圖形很大，BFS需要將它全部保存在內存中。 DFS更好。但是，除非對深度進行限制，否則DFS可能會丟失在大圖中。

總之，加快你的程序，你可能會考慮停止早期如果：

圖是不
你達到一個橋樑

其他啓發式：

先訪問1級的鄰居，然後再繼續。

我寫了一個有點類似程序，看看我到底能優化它： https://github.com/eamocanu/allPathsFinder

來源

2011-12-21 18:01:23 Adrian

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

回答

相關問題