匹配误差最低的两个图

Question

我有两个要匹配的图表（我不确定这就是我要寻找的世界）。

在我的第一个图表中，节点代表团队（节点值代表团队中的人数），links 代表团队在 1 到 5 的范围内有多接近。两个团队一起工作很多link 将比有时一起工作的两个团队更强大。

在我的第二个图中，节点代表 spaces（节点值代表 space 中的可用位置），links 代表 spaces 的距离.如果两个 space 位于同一楼层，则它们的 link 将比两个不在同一楼层的 space 更强。

我需要在可用的 space 秒内分配团队，尽量减少每个 linked 团队之间的距离（两个拥有强大 link 的团队将在同一楼层例如）。

我的第一个问题是：您有解决这个问题的妙方吗？ 我的第二个问题：如果没有，你知道我需要检查的方向是什么（可以修改的算法、讲座、文章......）。

非常感谢。 托马斯

Answer 1

为了部分回答这个问题，显然没有已知的多项式时间算法来解决这个问题，因为这个问题包括 graph isomorphism 问题作为一个子问题。这个问题既不知道是 NP 完全问题，也没有找到多项式算法。

更准确地说，假设房间图就是团队图，其中边没有加权。由于最佳解决方案会将每个团队匹配到相应的房间，因此问题中问题的算法将能够识别输入图是同构的。

Answer 2

和一些人谈过后，似乎这可能不是最好的解决方案。 我将着眼于求解器的方向，以便能够定义约束。

谢谢。