为图分配节点的算法设计
我有一个图论（也与组合学相关）问题，如下所示，我想知道设计解决该问题的算法的最佳方法是什么。
给定 6 个节点的 4 个不同图（不同，我指的是不同的结构，例如星形、线形、完整等）和 24 个独特的对象，设计一个算法将这些对象分配给这 4 个图 4 次，以便在 4 次分配中图上重复邻居的数量最小化。例如，如果对象 A 和 B 在一项作业中的 4 个图表中的 1 个上是邻居，那么在最好的情况下，A 和 B 在该任务中将不会再次成为邻居。其他3项作业。
显然，这种最小化的程度取决于给定的具体图结构。但我更感兴趣的是这里的通用解决方案，以便给定任意 4 个图结构，算法的结果可以保证这种最小化。
欢迎任何解决此问题的建议/想法，并且一些伪代码可能足以说明设计。谢谢。
I have a graph-theoretic (which is also related to combinatorics) problem that is illustrated below, and wonder what is the best approach to design an algorithm to solve it.
Given 4 different graphs of 6 nodes (by different, I mean different structures, e.g. STAR, LINE, COMPLETE, etc), and 24 unique objects, design an algorithm to assign these objects to these 4 graphs 4 times, so that the number of repeating neighbors on the graphs over the 4 assignments is minimized. For example, if object A and B are neighbors on 1 of the 4 graphs in one assignment, then in the best case, A and B will not be neighbors again in the other 3 assignments.
Obviously, the degree to which such minimization can go is dependent on the specific graph structures given. But I am more interested in a general solution here so that given any 4 graph structures, such minimization is guaranteed as the result of the algorithm.
Any suggestion/idea of solving this problem is welcome, and some pseudo-code may well be sufficient to illustrate the design. Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
表示：
您有 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}
并且
Sum(Xai)=1 ... Sum(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1
因为一个元素可以是只分配给一个节点。
我将通过定义每个节点的邻居关系来定义一个图，假设节点 8 有邻居节点 7 和节点 10，
以检查 A 和 B 是否是节点 8 上的邻居，例如：
A.e8=1 和 B.e7或 B.e10 =1 那么我只需要
函数 isNeighborInGraphs(A,B) 中的 A.e8*(B.e7+B.e10)==1 我测试每个节点，然后得到一个或为零，具体取决于邻居。
符号：
（第一张图为 1 到 6，等等...）
算法描述
A=e1... X=e24
我想这个例子会起作用，因为它是
非线性优化
问题）：
目标函数
约束：
您将得到最佳解
4.重复步骤 2 和 3，再重复 3 次。
Representation:
You have 24 elements, I will name this elements from A to X (24 first letters).
Each of these elements will have a place in one of the 4 graphs. I will assign a number to the 24 nodes of the 4 graphs from 1 to 24.
I will identify the position of A by a 24-uple =(xA1,xA2...,xA24), and if I want to assign A to the node number 8 for exemple, I will write (xa1,Xa2..xa24) = (0,0,0,0,0,0,0,1,0,0...0), where 1 is on position 8.
We can say that A =(xa1,...xa24)
e1...e24 are the unit vectors (1,0...0) to (0,0...1)
note about the operator '.':
There are some constraints on A,...X with these notations :
Xii is in {0,1}
and
Sum(Xai)=1 ... Sum(Xxi)=1
Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1
Since one element can be assign to only one node.
I will define a graph by defining the neighbors relation of each node, lets say node 8 has neighbors node 7 and node 10
to check that A and B are neighbors on node 8 for exemple I nedd:
A.e8=1 and B.e7 or B.e10 =1 then I just need A.e8*(B.e7+B.e10)==1
in the function isNeighborInGraphs(A,B) I test that for every nodes and I get one or zero depending on the neighborhood.
Notations:
(1 to 6 for first graph, etc...)
Description of the algorithm
A=e1... X=e24
exemple will work I guess since it's
a nonlinear optimization
problem):
Objective function
Constraints:
You get the best solution
4.Repeat step 2 and 3, 3 more times.
如果所有四个图都是
K_6，那么您能做的最好的事情就是选择 24 个对象的 4 个集合划分为 4 个集合，每个集合的基数为 6，这样任意两个集合的成对交集的基数最多为 2您可以通过选择在具有细化给出的偏序的集合分区的哈斯图中相距最大的集合分区来完成此操作。一般情况要困难得多，但也许您仍然可以从解决方案的粗略近似开始，然后巧妙地在四个分配中为哪个顶点分配哪个对象。If all four graphs are
K_6, then the best you can do is choose 4 set partitions of your 24 objects into 4 sets each of cardinality 6 so that the pairwise intersection of any two sets has cardinality at most 2. You can do this by choosing set partitions that are maximally far apart in the Hasse diagram of set partitions with partial order given by refinement. The general case is much harder, but perhaps you can still begin with this crude approximation of a solution and then be clever with which vertex is assigned which object in the four assignments.假设您不想循环所有组合并每次计算总和并选择最低的，您可以实现一个最小问题（根据您的约束使用线性规划求解器即复杂算法引擎或非线性求解器来解决，就时间而言更难谈论），并且根据路径的形状对变量（24）进行限制。您还可以使用 LINGO/LINDO 等免费软件快速创建决策理论模型并测试其正确性（不过您需要决策理论概念）
Assuming you don't want to cycle all combinations and calculate the sum every time and choose the lowest, you can implement a minimum problem (solved depending on your constraints using either a linear programming solver i.e. symplex algorithm engines or a non-linear solver, much harder talking in terms of time) with constraints on your variables (24) depending on the shape of your path. You can also use free software like LINGO/LINDO to create rapidly a decision theory model and test its correctness (you need decision theory notions though)
如果这与现实世界有任何关系，那么您不太可能绝对必须有一个真正的最小值的解决方案。接近最小值应该就足够了，对吧？如果是这样，您可以重复随机地进行 4 项作业并检查结果，直到您用完时间或找到足够好的解决方案或似乎已停止改进您的最佳解决方案。
If this has anything to do with the real world, then it's unlikely that you absolutely must have a solution that is the true minimum. Close to the minimum should be good enough, right? If so, you could repeatedly randomly make the 4 assignments and check the results until you either run out of time or have a good-enough solution or appear to have stopped improving your best solution.