匹配兩個最低錯誤的圖形

Question

我有兩個圖表，我想匹配（我不確定這是我正在尋找的世界）。

在我的第一個圖中，節點代表團隊（節點值代表團隊中的人數），鏈接代表團隊的團隊在1到5的等級上有多接近。兩個團隊共同工作的團隊將比兩個團隊有時​​在一起工作。

在我的第二個圖中，節點表示空間（節點值表示空間中的可用空間），鏈接表示空間有多近。如果兩個空間位於同一樓層，則它們將具有比兩個不在同一樓層上的空間更強的鏈接。

我需要在可用空間中分配球隊，以最大限度地減少每個聯繫球隊之間的距離（例如，兩個有強大聯繫的球隊將位於同一樓層）。

我的第一個問題是：你有一個可以解決這個問題的魔法？我的第二個問題：如果不是，你知道我需要檢查什麼方向（算法可以重寫，講座，文章...）。

非常感謝。 Thoma

Answer 1

與某些人交談後，似乎可能不是最好的解決方案。 我會在求解器的方向上尋找能夠定義約束的方法。

謝謝。

Answer 2

爲了回答這個問題，顯然沒有已知的多項式時間算法來解決這個問題，因爲問題包括graph isomorphism問題作爲子問題。這個問題既不知道是NP完全的，也沒有找到多項式算法。

更準確地說，假設房間圖恰好是團隊圖，其中邊不加權。作爲最佳解決方案將使每個團隊與相應的房間相匹配，問題中的問題算法將能夠識別輸入圖是同構的。