找到從板的一個角落到另一個沒有回溯的多條獨特路徑

Question

我被卡在算法優化中。

的目標是找到你多少種方式可以使用從A點到B點的棋盤，其中：

• A是左下角廣場。
• B是右上角的正方形。
• 每一圈只能走一個或一個右轉。

這裏是一個虛擬的解決方案：

# -*- conding: utf-8 -*- 
import time 

def solution(n, m, x, y): 
    ret = 0 
    if x < n-1: 
     ret += solution(n, m, x+1, y) 
    if y < m-1: 
     ret += solution(n, m, x, y+1) 
    if x == n-1 and y == m-1: 
    ret = 1 
    return ret 

def wrapper(n, m): 
    start = time.time() 
    reponse = solution(n, m, 0, 0) 
    stop = time.time() 
    print "Response: %dx%d = %d\nTime : %f\n" % (n, m, reponse, stop-start) 



if __name__ == "__main__": 
    for i in range(10): 
     wrapper(i+1,i+1) 
    #wrapper(7,7) 
    #wrapper(10,10) 
    #wrapper(100,100) 
    #wrapper(1000,1000) 
    #wrapper(10000,10000) <- way too slow 

雖然我留在小棋盤，它工作正常，結果是相關的。但我的目標是找到一個10000x10000電路板的解決方案。

Anyboy有沒有想法？

Answer 1

動態規劃：O（N）

它已經提到這個問題已經通過使用Triangle of Pascal的解決方案，它關係到Binomial coefficient。此外，Catalan number的條目還有一個很好的說明，即n×n的情況。

Ñ×Ñ情況

通過利用上述資源可以得出結論，對於大小的網格Ñ×Ñ需要計算C（2N - 2，N - 1）。您可以通過將網格旋轉45度並映射Pascal的三角來仔細檢查它。

實際上，直接計算這個數字需要以一種天真的方式計算最多3個不同的因子，這是一個非常昂貴的任務。如果你可以預先計算它們，那麼這裏就不討論了，你可以認爲這個問題具有複雜性O（1）。如果你對預先計算的方式不感興趣，那麼你可以繼續閱讀。

您可以使用動態規劃（DP）計算這樣不祥的數字。這裏的訣竅是以較小的步驟執行操作，而不需要您計算大的因子數。也就是說，要計算C（n，k），你可以先將自己置於C（n，1）處，然後步行到C（n，k）。我們首先以C（n，k-1）的形式定義C（n，k）。

C(n, k) = n!/k! * (n - k)!       ; k! = (k - 1)! * k 
     = n!/(k - 1)! * k * (n - k)!     ; (n - k)! = (n - k + 1)!/(n - k + 1) 
     = n! * (n - k + 1)/(k - 1)! * k * (n - k + 1)! ; C(n, k - 1) = n!/(k - 1)! * (n - k + 1)! 
     = C(n, k - 1) * (n - k + 1)/k 

在此基礎上，可以定義一個函數來計算C（N，K）爲在Python如下：

def C(n, k): 
    """ 
    Calculate C(n, k) using Dynamic Programming. 
    C(n, k) = C(n, k - 1) * (n - k + 1)/k 
    """ 
    C = 1 
    for ki in range(1, k + 1): 
     C = C * (n - ki + 1)/ki 
    return C 

它運行在線性時間，O（N）。

對於你需要計算C中的Ñ×Ñ情況下（2N - 2，N - 1）。

>> print "Response: %dx%d = %d" % (n, n, C(2 * n - 2, n - 1),) 
Response: 10000x10000 = 5... 

Ñ×米情況

對於一般Ñ×米情況下，你只需要計算C（N + M - 2，M - 1）。

>> print "Response: %dx%d = %d" % (n, m, C(n + m - 2, m - 1),) 
Response: 10000x10000 = 5...  

最後但並非最不重要的，you can see a live example at Ideone here.

時序

我跑了下面的網格大小的算法。

 N x N  | Response's Length | Time 
-----------------+-------------------+----------- 
     1 x 1  |   1 chars | 0.000001 
    10 x 10  |   5 chars | 0.000004 
    100 x 100 |   59 chars | 0.000068 
    1000 x 1000 |   600 chars | 0.002207 
    10000 x 10000 |  6018 chars | 0.163647 
100000 x 100000 |  60203 chars | 40.853971 

由於涉及的數量非常龐大，看起來網格大小爲100 000 x 100 000的操作看起來非常荒謬。沒有什麼可以驚訝的。

Answer 2

想想這樣：既然你的A點和B點在同一個地方，你必須移動相同數量的UP和RIGHT，但是順序會有所不同。所以你需要找到不同組合的數量。

Answer 3

你不需要這樣的算法。只是數學。這裏有一些值得思考的事情：當你在右上方時，你沒有任何不同的選擇。我們將其計爲零。當你剛好在右上角的右邊時，你唯一的選擇就是右轉（一個選項），因爲你不允許回溯。當你剛好在右上角以下時，你唯一的選擇就是上升。讓我們將其映射出

... 1 0 
..... 1 

那麼從目標角落向左/向下的角落呢？從那裏，有兩條路的角落（的選項去鄰居總和）：你可以去到右：

... 1 0 
....2 1 

擴大我們與那些隨時擴展的邊緣：當你在頂部，只有一個方式去右上：

...1 1 1 0 
...... 2 1 
........ 1 
........=1 

但每個非邊緣的選擇是數字的北部和東部鄰國的總和：

...1 1 1 0 
.....3 2 1 
.......3 1 
........ 1 

等等上。希望這可以讓你開始一個解決方案。

對此也有不同的思考方式。鑑於NxN板，你必須做2N的動作才能從一個角落到另一個角落。這些移動中的N個是北移，而N是東移。問題是：有多少個不同的 N東移動和N北移動的組合可以有一個2N長的字符串。

Answer 4

您正在尋找帕斯卡的三角形。該wikipedia link甚至提到您的具體問題