回溯通過路線的R中

Question

矩陣我有這樣一個矩陣：

http://i.imgur.com/3HiEBm4.png

可以加載像這樣：

matrix = structure(c("-", "-", "C", "G", "C", "A", "-", "0", "V", "V", 
"V", "V", "C", "H", "D", "V", "DV", "V", "A", "H", "H", "D", 
"DV", "D", "C", "H", "DH", "DH", "D", "V", "G", "H", "H", "D", 
"H", "D", "T", "H", "H", "H", "DH", "DH", "A", "H", "H", "H", 
"DH", "D", "T", "H", "H", "H", "DH", "H"), .Dim = c(6L, 9L)) 

開始在右下角時，目標是遵循方向（D =斜向0移動，H =向左移動，V =向上移動），使所有路徑到達零。正如你所看到的，有一些單元格有多個方向（如DH）。

我想通過這樣的矩陣找到所有可能的路徑。我用遞歸做了它。但是我很難正確存儲路徑。看起來好像當函數返回到一箇舊的單元格取其他方向時，它會將路徑追加到錯誤的列表中。

這裏是我的遞歸函數代碼：

threading = function(matrix,i,j,list) { #Function wants the matrix to be threaded, number of rows and cols, and an empty list 
    if (matrix[i,j] == 0) { #If the recursion has arrived at zero, stop and print out the path that arrived there 
    print(list) 
    } 
    else { #If still elsewhere inside the matrix... 
    for (move in strsplit(matrix[i,j],"")[[1]]) { #Iterate through each move in that cell 
     if (move == "D") { #If a move is D... 
     list = paste(list, "D", sep="") #Append that to the path 
     threading(matrix,i-1,j-1,list) #Send the function to the diagonal cell 
     } 
     if (move == "V") { #If a move is V... 
     list = paste(list, "V", sep="") #Append that to the path 
     threading(matrix,i-1,j,list) #Send the function to the above cell 
     } 
     if (move == "H") { #If a move is H... 
     list = paste(list, "H", sep="") #Append that to the path 
     threading(matrix,i,j-1,list) #Send the function to the left cell 
     } 
    } 
    } 
} 

所以，當我與上述矩陣運行它，它給這個作爲一個輸出：

> threading(matrix, 6,9, emptylist) 
[1] "HDDDDHH" 
[1] "HDDDDHHD" 
[1] "HDDHHDDD" 

起腳的是，第二個字符第二條路是錯誤的，但其他一切都是正確的。我如何避免這種情況？我不知道如何正確存儲路徑，而不會回到舊路徑。我覺得這件事情做的追加的訂貨和發送功能，下一個單元格，但如果我扭轉他們再追加從未發生過......

Answer 1

的問題是：

list = paste(list, "*", sep="") 

當你有兩個選擇的單元格時，例如「VH」時，for循環將經歷兩次迭代：list由第一次迭代修改，然後該修改後的值傳遞給第二次迭代。相反，每次迭代必須使用原始值。所以，你可以替換爲：

l = paste(list, "*", sep="") 

，並通過l而不是list到threading通話。

另外，最好避免將變量命名爲matrix或list，因爲它們也是函數的名稱。