表示:
你有 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,...X 有一些限制:
Xii 在 {0,1} 并且
总和(Xai)=1 ...总和(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,...Xx24)=1
因为一个元素只能分配给一个节点。
我将通过定义每个节点的邻居关系来定义一个图,假设节点 8 有邻居节点 7 和节点 10
检查 A 和 B 是否是节点 8 上的邻居,例如我 nedd:
A.e8=1 和 B.e7 或 B.e10 =1 那么我只需要 A.e8*(B.e7+B.e10)==1
在函数 isNeighborInGraphs(A,B) 中,我对每个节点进行测试,并根据邻域得到一个或零。
注释:
- 6 个节点的 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)
乙=...
...
X=(0,0...,1,...,0)
IsNeigborInGraphs(A,B)=A.e1*B.e2+... //如果1和2是一个图中的邻居,例如
L(A)=[B,B,C,E,G...] // A 的邻居列表(可以重复)
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)= ...
算法描述
- 从初始位置开始 A=e1... X=e24
- 实现 L(A),L(B)... L(X)
- 解决这个问题(使用求解器,例如ampl会起作用,因为它是一个非线性优化问题):
目标函数
min(总和(N(Z),Z=A 到 X)
约束:
总和(Xai)=1 ...总和(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,...Xx24)=1
你得到最好的解决方案
4.重复步骤 2 和 3,再重复 3 次。