0

加重グラフがあります。グラフ内の各ノードに 3 つのキーを割り当てました。グラフ内の 2 つの一意のノードを指定すると、共通のキーが存在する場合に 2 つのノードを接続するすべてのパスを表示するコードが必要です。ノードはマルチホップ方式でも接続できます。

keypool = randint(n,n,[1,10]) %key pool generation
for l = 1:n
for k = 1:3
    nodekey(l,k) = keypool(l,k);%Selects key from key pool
end;
end;
for i=1:n
fprintf('%s %d \t =  %d  %d  %d \n','key_node',i,nodekey(i,:));
end

これは、すべてのノードにランダムなキーを生成するために書いたコードです。共通キーがある場合にのみ、2 つのノード間のパスを見つける方法がわかりません。ノード数を入力してください:5

keypool =

 5     3     1     7     7
 3     7     8     4     3
 9     3    10     7    10
 2     5     2     7     8
 7    10     7     3     5

key_node 1   =  5  3  1 
key_node 2   =  3  7  8 
key_node 3   =  9  3  10 
key_node 4   =  2  5  2 
key_node 5   =  7  10  7

n の値は、ユーザーが入力したノードの数です。上記のコードは、5 つのノードに対してそのようなランダム キーを生成します。ノード 1 とノード 5 の間のパスを見つけたい場合、考えられるパスは 1->2->3->5、1->5、1->2->5 であると仮定します。共通キーのみを持つパスを出力する必要があります。つまり、1->2->3->5、1->2->5 です。

wt=zeros(n,n);
while(1)
    i=input('enter the starting node:(0 to quit):');
    if (i==0)    
        break;
    end
    j=input('enter the destination node:');
    wt(i,j)=input('Enter the cost: '); 
end
disp('Adjacency Matrix');
for i=1:n
fprintf('           %d',i);
end
for i=1:n
fprintf('\n%d          ',i);
for j=1:n
    fprintf('%d          ',wt(i,j));
end
end
Adjacency Matrix
       1           2           3           4           5
1          0          1          1          0          0          
2          0          0          0          0          0          
3          1          0          0          1          0          
4          0          0          1          0          0          
5          0          0          0          0          0

これは、ノード (1,2) (1,3) (3,4) (4,3) が接続されていることを意味します。

ユーザーはグラフに接続性を入力します。キープールの数値はランダムに生成されます。node1 に割り当てられたキーは 5,3,1 で、node5 には 7,10,7 です。これら 2 つのノードには共通のキーがありません。したがって、このパスは出力されません。ソース (ノード 1) からの共通キーが存在する場合は、ルートを宛先 (ノード 5) までたどる必要があります。

4

1 に答える 1

1

問題を 2 つのステップに分けることができます。

  1. 接続されているノードを特定し、同じキーを共有します。この情報は行列に格納され ( で表しましょうM)、これを修正隣接行列と呼びます。

  2. 修正された隣接行列に基づいて、あるノードから別のノードへのすべての可能なパスを見つけます。

最初の部分は次のように解決できます。

%// Obtain matrix 'sh' where each element at position (i, j) indicates if
%// node i and node j share a key
pairs = nchoosek(1:n, 2);                %// All possible pairs of nodes
sh = zeros(n);
for k = 1:size(pairs, 1)
    node1 = pairs(k, 1);
    node2 = pairs(k, 2);
    sh(node1, node2) = any(ismember(nodekey(node1, :), nodekey(node2, :)));
    sh(node2, node1) = sh(node1, node2); %// Matrix must be symmetrical
end

%// Obtain the modified adjacency matrix
M = sh & (wt > 0);

後編はお任せします。与えられた (変更された) 隣接行列を使用して、ノード A からノード B へのすべての可能なパスを見つけることMは、よく知られた問題です。可能な実装の 1つへのリンクを次に示します。

お役に立てれば！

PS: 次のように記述して
、 の生成を簡素化できます。nodekey

nodekey = keypool(:, 1:3);

MATLAB のベクトル化された演算は、コードをより効率的かつエレガントにするのに本当に役立ちます!

于 2013-03-03T19:51:33.113 に答える