用于将节点分配给图的算法设计

Question

我有一个图论(也与组合学有关)问题,如下所示,并想知道设计算法解决它的最佳方法是什么.

给定4个不同的6个节点的图形(不同的,我的意思是不同的结构,例如STAR,LINE,COMPLETE等)和24个独特的对象,设计一种算法将这些对象分配给这4个图形4次,这样就可以了在4个分配上重复图形上的邻居被最小化.例如,如果对象A和B在一个分配中的4个图中的1个上是邻居,则在最佳情况下,A和B 在其他3个分配中将不再是邻居.

显然,这种最小化的程度取决于给定的特定图形结构.但是我对这里的一般解决方案更感兴趣,因此给定任何4个图形结构,这种最小化作为算法的结果得到保证.

任何解决这个问题的建议/想法都是受欢迎的,一些伪代码可能足以说明设计.谢谢.

Answer 1

表示:

你有24个元素,我将这个元素命名为A到X(24个首字母).这些元素中的每一个都将在4个图中的一个中占有一席之地.我将从1到24为4个图形的24个节点分配一个数字.

我将通过24-uple =(xA1,xA2 ...,xA24)识别A的位置,如果我想将A分配给节点号8作为例子,我将写(xa1,Xa2..xa24) =(0,0,0,0,0,0,0,1,0,0 ... 0),其中1位于第8位.

我们可以说A =(xa1,... xa24)

e1 ... e24是单位向量(1,0 ... 0)到(0,0 ... 1)

关于运营商'.'的说明:

• A.e1 = XA1
• ...
• X.e24 = Xx24

使用这些符号对A,...... X有一些限制:

Xii在{0,1}和

Sum(Xai)= 1 ... Sum(Xxi)= 1

总和(Xa1,xb1,... Xx1)= 1 ...总和(Xa24,Xb24,... Xx24)= 1

由于一个元素只能分配给一个节点.

我将通过定义每个节点的邻居关系来定义图,假设节点8具有邻居节点7和节点10

检查A和B是节点8上的邻居,例如:

A.e8 = 1且B.e7或B.e10 = 1然后我只需要A.e8*(B.e7 + B.e10)== 1

在函数isNeighborInGraphs(A,B)我测试每个节点,我得到一个或零取决于邻域.

符号:

• 4个节点的图形,每个元素的位置由1到24的整数定义.(第一个图形为1到6等)
• e1 ... e24是单位向量(1,0,0 ... 0)到(0,0 ... 1)
• 设A,B ...... X为N个元素.

A =(0,0 ...,1,...,0)=(XA1,XA2 ... xa24)

B = ...

...

X =(0,0 ...,1,...,0)

• 图表说明:

IsNeigborInGraphs(A,B)= A.e1*B.e2 + ... //如果1和2是一个图中的neigbors例如

• 系统状态:

L(A)= [B,B,C,E,G ...] // A的neigbors列表(可以重复)

actualise(L(A)):
for element in [B,X]
if IsNeigbotInGraphs(A,Element)
L(A).append(Element)
endIf
endfor

• 目标函数

N(A)= len(L(A))+ Sum(IsneigborInGraph(A,i),i in L(A))

...

N(X)= ......

算法描述

1. 从初始位置A = e1 ... X = e24开始
2. 实现L(A),L(B)...... L(X)
3. 解决这个问题(与solveur,AMPL的为例将工作我想因为它是一个非线性优化问题):

目标功能

min(总和(N(Z),Z = A到X)

约束:

Sum(Xai)= 1 ... Sum(Xxi)= 1

总和(Xa1,xb1,... Xx1)= 1 ...总和(Xa24,Xb24,... Xx24)= 1

您将获得最佳解决方案

4.重复步骤2和3,再重复3次.