2
我有一個二部圖，其中每個節點都有不同長度的連接（邊）到另一個分區中的節點。我想要選擇邊使得長度的總和儘可能小，但是受制於每個節點應該只有一個選定邊的約束條件（如果兩個分區中的節點數相等 - 如果沒有，一個或多個節點將沒有選定的邊緣）。雙向圖，最短連接？
我想盡可能快地找到匹配，但直到現在我才發現嘗試每種可能性的蠻力方法，這給我一個O（n！）算法 - 這是不可行的。有人建議採取更好的方法嗎？
我的具體問題如下：我觀察到或多或少隨機移動3D粒子在兩個不同的時間點。我想知道每個粒子在哪裏移動，即跟蹤每個粒子，假設它們的總移動儘可能短。
確切的答案將是一個由@tjhighley建議。如果你可以用一個「足夠好」的算法來生活，你可以從一個天真的匹配開始，然後將其用於[*退火*]（https://en.wikipedia.org/wiki/Simulated_annealing）。 –