3

私はMATLABでコードを作成しました。これにより、頂点のランダムグラフを生成できますn。各頂点には、cループのない固定隣接点があります（エッジが方向付けられているため、「aがbに接続されている」とは「bがaに接続されている」ことを意味しません）。

n = 10000ただし、特にやなどの大きさで作業する必要がある場合は、非常に非効率的c = 1000です。誰かがそれを大いに最適化できるか、または建設的な何かを提案できるかどうか疑問に思いましたか？

function [M]=matsrand(n,c)


MM=0;   %arbitrary starting value
while MM ~=n*c

    M = sparse(zeros(n));       
    ctin = zeros(1,n);  


    for i=1:n
        rp = randperm(n);   %generate vector of the randomly permuted order of n vertices
        rp(rp==i)=[];       %get rid of itself to avoid self connection

        noconnect=find(ctin(:)>=c); %generate list that i is not allowed to connect to
        where=ismember(rp,noconnect);   %returns 1 to the subset noconnect in rp
        noconnectind=find(where);

        rp(noconnectind(:))=[];         %remove the neurons i is not allowed to connect to

        if length(rp)<c
            break
        else
            r=rp(1:c);
        end
        M(i,r)=1;
        ctin(r)=ctin(r)+1;

    end
    MM=sum(ctin);
end
4

1 に答える 1

1

これは物事を少しスピードアップします：

function [M]=matsrand(n,c)

    MM=0;   %arbitrary starting value
    all_nums=1:n;

    while MM ~=n*c

        M = sparse([],[],[],n,n,n*c);
        ctin = zeros(1,n);

        for ii=1:n
            noconnect=ctin>=c;
            noconnect(ii)=true;

            rem_nums = all_nums(~noconnect); % remaining numbers
            rp=randperm(n-sum(noconnect));
            rp = rem_nums(rp); % remaining numbers, hussled

            if numel(rp)<c
                break
            else
                r=rp(1:c);
            end
            M(ii,r)=1;
            ctin(r)=ctin(r)+1;
        end
        MM=sum(ctin);
    end
end

メモリが問題にならない場合は、スパース行列を通常のに置き換えることができると思いますzeros(n,n)。

主な問題はまだあなたがその幸運な組み合わせを打たなければならないということです。

于 2012-08-08T15:41:31.650 に答える