0

我有一组 30 个节点，每个节点一次只能连接一个。此外，一个节点无法连接到另一个特定的节点（例如，带有 and的节点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 个禁止连接），总共 28 个时隙（行）包含 15 个对（30 列）。

Edit2：另一种方法可能是生成一个 30x30 矩阵，该矩阵具有从 1 到 30 的所有可能的数字组合作为行，但约束不能重复对（不按顺序）。例如，以下是可能的有效向量（限制为 12 个元素而不是 30 个），但是第二个被丢弃，因为 Couple[2 1]等同于 Couple [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

好的，

我发现的第一个解决方案是使用 perms(1:30) 但输出太大了！它给出了一个所有可能排列为 1:30 的数组（30！超过 10^32..）。

所以我们需要找到另一种方法来先验地选择有效行。

一种可能的方法是递归地计算 N 的所有偶数值的所有行，从 N=2（初始化）到 N=30（你想要的结果），即：

（我将用 Res(k) 表示满足 N=k 条件的行集）

初始化：

N=2 : Res(2)=[12];

N-->N+2 ：

分辨率（N+2）={

  • Res(N) 的所有行最后加上 [N+1 N+2]
  • 对于 (1:N-1)x(2:N) 中的 (i,j)，i < j，找到包含对 (ij) 的行：将其替换为 (i N+1)(j N) 和(i N)(j N+1)

}

示例： 2-->4

资源[4]=[

  • 1234

  • 1423 和 1324 (i=1, j=2)

]

示例 2： 4-->6

水库（6）= [

  • 123456 , 142356 , 132456

  • 152634 和 162534 (i=1 j=2) , 153624 和 163524 (i=1 j=3) , 154623 和 164523 (i=1 j=4) , 253614 和 263514 (i=2 j=3) ,132546 和132645 (i=2 j=4) , 123546 和 123645 (i=3 j=4)

]

我建议您使用单元格数组为每个单元格保留一对，以便轻松找到对。

于 2015-10-05T12:37:12.283 回答
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 回答