2

让我给你看一个例子来说明我的问题。我有 4 个处理器 1-4。他们中的任何一个都必须进行一些交流。因此,为了节省时间,我们可以按如下方式进行。

时间 1:(1,2)(3,4)
时间 2:(1,3)(2,4)
时间 3:(1,4)(2,3)

所以我们可以看到,对于偶数 n,我们可以在 n-1 次内完成这个通信。但是当处理器数量n变大时,要找到一种算法来确保每次都没有空闲处理器就不是一件容易的事了。

如果 n 等于 6。以下不是一个好的选择:

时间1:(1,2)(3,4)(5,6)
时间2:(1,3)(2,4) ....(5和6已经通信,所以空闲在时间 2)。

尽管我的专业是电磁学,但我查阅了很多关于组合学的书籍。但我仍然找不到答案。有人可以引导我朝着正确的方向前进吗?

4

1 回答 1

1

这个问题相当于对具有偶数个顶点的完整图的边缘着色。每个顶点对应于一些“处理器”,每个颜色对应于原始问题的“时间”。

维基百科关于边缘着色的文章为这种情况提出了一个简单的算法:

将 n 个点放在正 (n − 1) 边多边形的顶点和中心。对于每个颜色类,包括从中心到多边形顶点之一的一条边,以及连接多边形顶点对的所有垂直边。

在此处输入图像描述

于 2013-06-04T11:50:45.080 回答