时间戳

首页 > 解决方案 > 最小生成树的循环不起作用

r - 最小生成树的循环不起作用

问题描述

我们作为 3 个朋友尝试使用 r 解决具有冲突问题的最小生成树。在解决这个问题时，我们读取了包含 for ex 的 .txt 格式的文件。“1 2 5 2 4 6”等表示从节点1到2，存在一条权重为5的边，“1 2 2 4”等表示边1-2和2-4之间存在冲突关系. 为了继续，我们必须形成一个 nxn 冲突矩阵，如果边之间不存在冲突关系，我们将存储 0，如果存在冲突关系，则存储 1。为此，我们开发了一个 3-for 循环 for(i in 1:dim(edges_read)[1]){

for(i in 1:dim(edges_read)[1]){
  for(k in 1:dim(edges_read)[1]){
    for(t in 1:dim(conflicts)[1]){
      if(all(conflicts[t,] == c(edges_read[i,1], edges_read[i,2],
                                  edges_read[k,1], edges_read[k,2]) )){
        conflictmatrix[i,k] <- 1
      }
    }
  }
}

但是，R 无法为我们提供解决方案，而且这个 for 循环需要很长时间。我们该如何解决这种情况？感谢您的进一步帮助

标签： rfor-loopconflictminimum-spanning-tree

解决方案

正如您所发现的，for()R 中的循环并不快。有更快的方法，但很难提供没有数据的示例。请使用类似dput(edges_read)和dput(conflicts)提供数据的一个小例子。

例如，您可以在 Rcpp 包中实现 for 循环以提高速度。根据您问题中的代码，您可以像这样重新实现 3 循环代码：

Rcpp::cppFunction('NumericVector MSTC_nxn_Cpp(NumericMatrix edges_read, NumericMatrix conflicts){
int n = edges_read.nrow(); //output matrix size (adjust to what you need)
int m = conflicts.nrow();  //output matrix size (adjust to what you need)
NumericMatrix conflictmatrix( n , m ); //the output matrix 
for(int i=0;i<n;i++){ //your i loop
  for(int k=0;k<n;k++){ // your k loop
  double te = edges_read( i, 0 ); //same as edges_read[i,1]
  double tf = edges_read( i, 1 ); //same as edges_read[i,2]
  double tg = edges_read( k, 0 ); //same as edges_read[k,1]
  double th = edges_read( k, 1 ); //same as edges_read[k,2]
  NumericVector w =  NumericVector::create(te,tf,tg,th); //this could probably be more simple
    for(int t=0;t<m;t++){   //your t loop
        NumericVector v = conflicts( t , _ ); // same as conflicts[t,]
        LogicalVector r;   //vector for checking if conflicts and edges are the same
        for(int p=0; p<4; p++){  //loop to check logic 
          r[p]=v[p]==w[p];  //True / False stored
        };
        int q = r.size();
  for (int ii = 0; ii < q; ++ii) {  //similar to all() This code could be simplified!
    if (!r[ii]) {false;}
  else{conflictmatrix[i,k] = 1;}}
  }}}
  return conflictmatrix;  //your output
}')

#Then run the function
MSTC_nxn_Cpp(edges_read, conflicts )

推荐阅读