2

我有一个加权图，我用一个邻接矩阵存储。矩阵如下所示：

       v1 v2 v3 v4
    v1 0  1  0  2
    v2 1  0  3  0
    v3 0  3  0  0
    v4 2  0  0  0

现在我想在均匀边缘随机选择一个。我已经尝试过这样做，而且它似乎有效。但问题是有时它会找到边缘 (v1,v1) 或 (v2,v2) 或 ... 。但在我的图中，这条边永远不存在。

那么如何在没有这个问题的情况下选择均匀边缘的随机数呢？

这是我的代码：

int countEdges = matrix.getCountEdges();
Random rand = new Random();
int randomNum = rand.nextInt((2*countEdges));
int x=0,y=0,s=0;
while(s<randomNum) {
    s = s + matrix.getamountOfEdgesOnVertex(x);
    x = x + 1;
}
randomNum = randomNum - (s-(matrix.getamountOfEdgesOnVertex(x)));
s = 0;
while(s<randomNum) {
    s = s + matrix.getWeightOfEdge(x, y);
    y = y + 1;
}
System.out.println("x: "+x+" y: "+y);
4

2 回答 2

1

1:n*n-n如果您在数组中订购有效对，您可以简单地选择一个随机整数 k in并选择第 k 个元素，例如 columnwise : [(v1,v2),(v1,v3),(v1,v4),(v2,v1),...]。

如果该集合中的边被加权，请查看启用这种加权的随机数生成算法。一些库正在实现这样的生成器，例如RandomSelect 类中的http://randomlib.sourceforge.net/。

于 2013-04-28T20:03:53.027 回答
0

我认为您的代码似乎是合理的，但它使关于统一选择的推理（关于边缘权重）变得困难。

考虑下图。

   v1  v2  v3  v4
v1  0   1   1   1
v2  1   0   0   0
v3  1   0   0 999
v4  1   0 999   0

countEdges = 4
randomNum in [0, 7]

If randomNum < 3 then we see that 
   s = 0; x = 0; => we continue the loop
   s = 3; x = 1; => we exit the first loop

所以现在 x 在代码中的任何地方都不会改变，所以顶点 v2 必须参与边，至少 3/8% 的时间，这是没有意义的，因为边权重在 v3 和 v4 之间是巨大的。

替代解决方案 1

在我的评论中使用@antitrust 的解决方案。但是，如果您的图表太大，这是令人望而却步的。

替代解决方案 2

首先获得总边权重，因此遍历每个条目并获得矩阵的总和。这需要 O(n) 时间（其中 n 是条目数）和恒定空间。

int weight = Random.nextInt(totalWeight) + 1;
for(int i = 0; i < matrixSize; i++) {
    for(int j = i+1; j < matrixSize; j++) {
        if(weight <= Matrix[i][j]) {
            System.out.println("Row: " + i + " Col: " + j);
            return;
        }
        weight -= Matrix[i][j];    
    }
}

显然，这会遍历矩阵中的每个条目。如果您愿意以时间换取空间，则可以通过保持累积行总数来加快速度，这样您就可以在 O(MatrixSize + log(MatrixSize)) 中找到正确的条目以供您选择，并在其中使用二进制搜索变体通过二进制搜索通过行总和。

替代解决方案 3

您可能需要考虑使用替代数据结构（不是邻接矩阵），具体取决于您想要采样的频率。也许邻接列表或某种地图可能会更好。还取决于您的邻接列表中有多少个 0。

于 2013-04-28T20:21:05.507 回答