12

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

给定 6 个节点的 4 个不同的图（不同，我的意思是不同的结构，例如 STAR、LINE、COMPLETE 等）和 24 个唯一对象，设计一个算法将这些对象分配给这 4 个图4 次，使得在 4 个分配上的图上重复的邻居被最小化。例如，如果对象 A 和 B 在一个分配中的 4 个图中的 1 个上是邻居，那么在最好的情况下，A 和 B在其他 3 个分配中不会再次成为邻居。

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

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

4

4 回答 4

5

表示：

你有 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} 并且

总和（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)= ...

算法描述

  1. 从初始位置开始 A=e1... X=e24
  2. 实现 L(A),L(B)... L(X)
  3. 解决这个问题（使用求解器，例如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 次。

于 2011-06-13T14:04:46.397 回答
3

如果所有四个图都是K_6，那么您可以做的最好的事情是选择 24 个对象的 4 个集合划分为 4 个集合，每个集合的基数为 6，这样任何两个集合的成对交集的基数最多为 2。您可以通过选择 set 来做到这一点在具有由细化给出的偏序的集合分区的 Hasse 图中相距最大的分区。一般情况要困难得多，但也许您仍然可以从解决方案的这种粗略近似开始，然后巧妙地在四个分配中为哪个顶点分配哪个对象。

于 2011-06-10T23:43:44.773 回答
0

假设您不想循环所有组合并每次都计算总和并选择最低的，您可以实现最小问题（根据您的约束使用线性规划求解器，即 symplex 算法引擎或非线性求解器来解决，在时间方面更难谈论）对变量的限制（24）取决于路径的形状。您还可以使用 LINGO/LINDO 等免费软件快速创建决策理论模型并测试其正确性（尽管您需要决策理论概念）

于 2011-06-06T19:01:55.807 回答
0

如果这与现实世界有任何关系，那么您不太可能绝对必须有一个真正最低限度的解决方案。接近最小值应该足够了，对吧？如果是这样，您可以反复随机分配 4 个作业并检查结果，直到时间用完或有足够好的解决方案或似乎已停止改进您的最佳解决方案。

于 2011-06-10T21:07:52.227 回答