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

Question

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

给定 4 个具有 6 个节点的不同图(不同，我指的是不同的结构，例如 STAR、LINE、COMPLETE 等)和 24 个独特的对象，设计一个算法将这些对象分配给这 4 个图 4 次，以便在 4 个分配的图形上重复邻居的数量最小化。例如，如果对象 A 和 B 在一个分配中的 4 个图中的其中一个上是邻居，那么在最好的情况下，A 和 B 将不会再次成为邻居其他 3 个作业。

显然，这种最小化的程度取决于给定的特定图形结构。但我对这里的通用解决方案更感兴趣，因此给定任意 4 个图结构，算法的结果可以保证这种最小化。

欢迎提出解决此问题的任何建议/想法，一些伪代码可能足以说明设计。谢谢。

Answer 1

表示:

你有 24 个元素，我将把这些元素命名为 A 到 X(24 个首字母)。 这些元素中的每一个都将在 4 个图表中的一个中占有一席之地。我将给 4 个图的 24 个节点分配一个编号，从 1 到 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} 和

总和(Xai)=1 ...总和(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) 中，我对每个节点进行测试，并根据邻域得到 1 或 0。

符号:

• 4 个图，有 6 个节点，每个元素的位置由 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+... //if 1 and 2 are neigbors in one graph for exemple

• 系统状态:

L(A)=[B,B,C,E,G...] // list of neigbors of A (can repeat)

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. 解决这个问题(使用求解器，ampl 用于 我想这个例子会起作用，因为它是 非线性优化 问题):

目标函数

min(Sum(N(Z),Z=A to X)

约束:

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

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

你得到最好的解决方案

4.重复步骤2和3，再重复3次。