回溯通过路线的R中

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"

起脚的是，第二个字符第二条路是错误的，但其他一切都是正确的。我如何避免这种情况？我不知道如何正确存储路径，而不会回到旧路径。我觉得这件事情做的追加的订货和发送功能，下一个单元格，但如果我扭转他们再追加从未发生过......

来源

2014-10-04 Jeff

除非您知道如何轻松地从您附加的图片中轻松获取而无需手动输入，否则您应该为该问题添加数据集 – 2014-10-04 20:34:32

更具体地说：发布'dput（矩阵）'的输出。 – 2014-10-04 20:38:37

很酷，不知道dput（）！编辑。 – Jeff 2014-10-04 20:42:47

的问题是：

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

当你有两个选择的单元格时，例如“VH”时，for循环将经历两次迭代：list由第一次迭代修改，然后该修改后的值传递给第二次迭代。相反，每次迭代必须使用原始值。所以，你可以替换为：

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

，并通过l而不是list到threading通话。

另外，最好避免将变量命名为matrix或list，因为它们也是函数的名称。

来源

2014-10-04 22:27:02 flodel

谢谢。这对我来说太明显了！是的，你说得对，我需要改进我的命名。 – Jeff 2014-10-05 02:32:21

回溯通过路线的R中

回答

相关问题