0

30 個のノードのセットがあり、各ノードは一度に 1 つだけに接続できます。さらに、あるノードは別の特定のノードに接続できません (たとえば、 と があるノードid= id+15、たとえば 1-16、2-17 ... ルールは関係ありません。関連付けノード番号を変更できます)。私が探しているのは、各行がすべてのノードが別のノードに接続されている可能性のある接続のセットであり、各ノードが他のすべてのノードに接続されているマトリックスです(禁止されているノードを除く)。このようになります（ペアで読んでください）

[1  2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30;
2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  1   30;
1   4   2   5   3   6   7   10  8   11  9   12  13  16  14  17  15  18  19  22  20  23  21  24  25  28  26  29  27  30;
4   7   5   8   6   9   10  13  11  14  12  15  16  19  17  20  18  21  22  25  23  26  24  27  28  1   2   29  3   30;
...
]

私はすべての可能な反復されない組み合わせ (二項式 30 オーバー 2 => 435) を収集することによってこれを開発しようとしていましnchoosekたが、現在、私が持っているすべてのペアを29行15列の行列に配置する問題に取り組んでいます。繰り返しなし。これにより、 の出力から禁止されたペアを削除することで、制約を簡単に尊重できますnchoosek。

これは既知のグラフの問題だと確信していますが、それについて何も見つけることができませんでした。誰もそれを実装することを知っていますか?

目的は、30 のノード間のポイント ツー ポイント接続のタイムラインを説明することです。それぞれが特定の相互に接続できないため、可能な接続の総数は 420 (435 - 15 の禁止された接続) であり、15 ペア (30 列) を含む合計 28 のタイムスロット (行) になります。

Edit2: さらなる方法として、1 から 30 までの数字のすべての可能な組み合わせを行として持つ 30x30 マトリックスを生成することもできますが、ペアが繰り返されない (順序どおりではない) という制約があります。たとえば、以下は可能な有効なベクトル (30 要素ではなく 12 要素に制限されています) ですが、2 番目の要素は couple が couple[2 1]と同等であるため破棄され[1 2]ます。ただし、制約に対処する方法がわかりません。

[1 2 3 4 5 6 7 8 9 10 11 12]
[2 1 3 4 5 6 7 8 9 10 11 12]
4

2 に答える 2

0

出来るよ：

clear   all
%creation of vector
v       = 1:30;
%creation of combinations
[p1,p2] = meshgrid(v,v);
A       = [p1(:) p2(:)];
B       = fliplr(A);
%selection of unique combinations
[~,ind] = ismember(A,B,'rows');
ind     = ind > (1:length(ind))';
A       = A(ind,:);
于 2015-10-02T13:49:58.223 に答える