如何找到連接兩組點的最小費用

Question

我得到了兩組點S和V，都是n的大小。我想鏈接兩個集合，使得S中的每個點都鏈接到V中的一個且僅有一個點。鏈接兩個點的成本定義爲兩點之間的歐幾里德距離。應該有n！可能的聯繫方式。那麼如何找到最低成本的方式呢？ （以有效的方式）

Answer 1

這是一個分配問題。你可以用Hungarian Method來解決它。在python中有這樣的實現。你也可以用任何線性規劃求解器來解決這個問題。 LP公式總是會給你一個整數解。