IT干货网

r之通过 R 中的方向矩阵回溯

jiqing9006 2025年01月19日 编程设计 64 0

我有一个这样的矩阵:

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" 

关键是后两条路径的第二个字符是错误的,但其他一切都是正确的。我该如何避免这种情况?如果不返回旧路径,我无法弄清楚如何正确存储路径。我认为这与追加的顺序和将函数发送到下一个单元格有关,但如果我反转它们,那么追加永远不会发生......

请您参考如下方法:

问题在于:

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

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

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

并将 l 而不是 list 传递给 threading 调用。

另外,最好避免将变量命名为 matrixlist,因为它们也是函数的名称。


评论关闭
IT干货网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!