モンテカルロシミュレーションで接続グラフが認識されない

Question

n頂点グラフを接続するのに必要な有向エッジの最小数の期待値を計算するモンテカルロシミュレーションを作成しています。これは、すべての0の隣接行列から始め、単一の有向辺を追加し、次にそれが接続されたグラフを表すかどうかを調べるために行列をテストします。このプロセスは、接続されたグラフが構築されるまで繰り返され、そこに到達するまでに要した反復回数は、1回の試行のサンプルサイズです。プログラムは小さなグラフでは正確であるように見えますが、グラフが〜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）を使用して、行列内のすべてのエントリの積を返すため、行列にゼロが含まれているかどうかを確認しました。私はオーバーフローの可能性を考慮しなかった。私は、numpy.prodの値が大きすぎると（最も確実に）、ゼロにリセットされると仮定します。これは多くの偽陰性を引き起こす。