匹配两个最低错误的图形

Question

我有两个图表，我想匹配（我不确定这是我正在寻找的世界）。

在我的第一个图中，节点代表团队（节点值代表团队中的人数），链接代表团队的团队在1到5的等级上有多接近。两个团队共同工作的团队将比两个团队有时​​在一起工作。

在我的第二个图中，节点表示空间（节点值表示空间中的可用空间），链接表示空间有多近。如果两个空间位于同一楼层，则它们将具有比两个不在同一楼层上的空间更强的链接。

我需要在可用空间中分配球队，以最大限度地减少每个联系球队之间的距离（例如，两个有强大联系的球队将位于同一楼层）。

我的第一个问题是：你有一个可以解决这个问题的魔法？我的第二个问题：如果不是，你知道我需要检查什么方向（算法可以重写，讲座，文章...）。

非常感谢。 Thoma

Answer 1

与某些人交谈后，似乎可能不是最好的解决方案。 我会在求解器的方向上寻找能够定义约束的方法。

谢谢。

Answer 2

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

更准确地说，假设房间图恰好是团队图，其中边不加权。作为最佳解决方案将使每个团队与相应的房间相匹配，问题中的问题算法将能够识别输入图是同构的。