Monte Carlo 仿真无法识别连通图

Question

我正在编写一个 Monte Carlo 模拟，用于计算连接 n 顶点图所需的最少有向边数的预期值。它通过从全 0 邻接矩阵开始，添加单个有向边然后测试矩阵以查看它是否表示连通图来实现这一点。这个过程一直循环，直到构造出一个连通图，然后到达那里所花费的迭代次数就是单次试验的样本量。该程序对于小图似乎是准确的，但是一旦图超过 10 个顶点，就会越来越清楚地表明，在已经构建了连通图之后，它会不断添加顶点。本质上，该算法在大图上没有足够早地停止。

似乎罪魁祸首可能是 isConnected 函数，但我不完全确定。任何建议将不胜感激。

import numpy as np
import math
import random

# Randomly adds an edge to the graph by
# choosing a random 0 from the adjecency
# matrix and changing it to a 1.
# @param mat - the list type matrix
# @param k   - the dimension of the matrix
def addEdge(mat, k):

    flag = False

    while flag == False:

        colNum = random.randint(0, k-1)
        rowNum = random.randint(0, k-1)

        if mat[rowNum][colNum] == 0:
            mat[rowNum][colNum] = 1
            flag = True 

# Runs singleTrial multiple times and finds
# the average of their sample sizes
def getExpectedValue(size, trials):

    sampleSum = 0.0

    flag = True

    for i in range(trials):
        sample = singleTrial(size)
        sampleSum += sample

    expectedValue = float(sampleSum/trials)

    return expectedValue


# Adds edges to an initially edgeless
# graph UNTIL the graph becomes connected.
def singleTrial(size):

    # Create all zero matrix
    mat = np.random.randint(0,1,size=(size,size))

    sample = 0

    flag = True

    while flag:
        # Uncomment this code to see each matrix that is 
        # generated in a single trial. Upon viewing it
        # is clear that this while loop does not terminate
        # early enough.
        #print mat
        #print "\n"
        addEdge(mat, size)
        sample += 1
        if isConnected(mat, size):
            print mat
            flag = False

    print sample
    return sample 


# Checks if a given matrix is connected by
# calculating the sum of the number of 1 step
# paths though the number of k step paths
# for every pair of verticies. If this number
# is zero for any pair, then the graph is 
# not connected.
def isConnected(A, k):

    B = A

    for i in range(2, k-1):
        B = B + np.linalg.matrix_power(A, i)
    if np.prod(B) != 0:
        return True
    else:
        return False


if __name__ == '__main__' :


    # Perform 1 trial on an 11 vertex graph
    print getExpectedValue(11, 1)

Answer 1

我解决了这个问题。我使用函数 numpy.prod(mat) 检查矩阵是否包含零，因为它 returns 是矩阵中所有条目的乘积。我没有考虑溢出的可能性。我假设如果 numpy.prod 的值变得太大（它肯定会），它将重置为零。这会造成很多漏报。

Monte Carlo 仿真无法识别连通图

Monte Carlo Simulation Fails to Recognize Connected Graph

python

algorithm

math

graph

montecarlo