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

我有一个图论（这也与组合问题有关）问题，下面举例说明，并想知道设计算法解决问题的最佳方法是什么。将节点分配给图的算法设计

鉴于4个不同6个节点的曲线图（由不同的，我的意思是不同的结构，例如星形，线形，COMPLETE，等等），和24个独特的目的，设计一个算法，这些对象分配给这4个图表4次，因此4个赋值中图上的重复邻居数为最小化为。例如，如果对象A和B在一个赋值中的4个图中的1个上是邻居，则在最佳情况下为，A和B将为而不是在其他3个赋值中再次为邻居。

显然，这种最小化的程度取决于给定的具体图结构。但是我对这里的一个通用解决方案更感兴趣，所以给定任何4个图结构，这种最小化作为算法的结果得到了保证。

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

来源

2011-06-06 skyork

我可能会遗漏一些东西，但... 24个对象意味着您可以为每个图中的每个节点分配一个不同的对象，从而导致任何给定邻居不超过一次。 – Chowlett 2011-06-06 14:57:32

@Chowlett，是的，但这只是一项任务（即将24个对象总共分配给4 x 6个节点）。我在这里感兴趣的是超过4个作业，重复邻居的数量被最小化。 – skyork 2011-06-06 15:02:17

啊，我遵循。我很困惑，因为有4个图表和4个分配，但是这些数字实际上是无关的。 – Chowlett 2011-06-06 15:22:24

表示：

你有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 =（A1，... xa24）

E1 ... E24是单位矢量（1,0 ...，0）到（0， 0 ...1）

注意到有关操作 ''：

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

上有一些限制A，... X与这些符号：

Xii在{0,1} 和

（Xa1，xb1，... Xx1）= 1 ... Sum（Xa24，Xb24，... Xx24）= 1 ... Sum（Xxi）= 1

Sum（Xa1， 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-3的整数定义为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））+萨姆（IsneigborInGraph （A，i）中，i的L（A））

...

N（X）= ...该算法

开始的

说明与初始位置 A = E1 ... X = E24

具体化L（A），L（B）... ...你（X）

解决这个（用solveur，ampl为为例将工作我想，因为它是一个非线性优化问题）：

目标函数

分钟（萨姆（N（Z）中，Z = A至X）

限制条件：

萨姆（赛）= 1 ... Sum（Xxi）= 1

Sum（Xa1，xb1，... Xx1）= 1 ... 总和（Xa24，XB24，... Xx24）= 1

你得到最佳的解决方案

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

来源

2011-06-13 14:04:46

感谢您的建议。但是，你能详细解释一下，你的意思是e1，e2等，你是指N个元素A，B，...，X及其表示（xa1，xa2 ... xa24）是什么意思？ – skyork 2011-06-16 22:02:44

@Skyork，我更新了这篇文章，我添加了段**表示法** – 2011-06-17 06:36:20

假设您不想循环所有组合并每次计算总和并选择最小值，则可以实现最小问题（根据您的约束使用线性规划求解器即symplex算法引擎或非线性规划求解器非线性求解器，在时间方面谈得多），并根据路径的形状对变量（24）进行约束。你也可以使用像LINGO/LINDO这样的免费软件来快速创建一个决策理论模型并测试它的正确性（你需要决策理论的概念）

来源

2011-06-06 19:01:55

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

来源

2011-06-10 21:07:52 Fantius

如果所有四个图都是K_6，那么你可以做的最好的选择是将24个对象的4个分区分成4个基数为6的每个集合，这样任意两个集合的成对交集至多有2个基数。通过选择集合分区的Hasse图中最大相距的集合分区来完成此操作，并通过细化给出部分顺序。一般情况下要困难得多，但也许你仍然可以从解决方案的粗略近似开始，然后巧妙地将哪个顶点分配给四个赋值中的哪个对象。

来源

2011-06-10 23:43:44 PengOne

我怀疑为什么这还不是被接受的答案的唯一正当理由，更可能是在'我的头脑'部门比实际答案。如果你能想出一个（部分）这个想法的演示，我认为你会（a）教会我很多（b）在这里得到你更多的赞赏。 – sehe 2011-06-18 19:36:14

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

回答

相关问题