2
我有一个二部图，其中每个节点都有不同长度的连接（边）到另一个分区中的节点。我想要选择边使得长度的总和尽可能小，但是受制于每个节点应该只有一个选定边的约束条件（如果两个分区中的节点数相等 - 如果没有，一个或多个节点将没有选定的边缘）。双向图，最短连接？
我想尽可能快地找到匹配，但直到现在我才发现尝试每种可能性的蛮力方法，这给我一个O（n！）算法 - 这是不可行的。有人建议采取更好的方法吗？
我的具体问题如下：我观察到或多或少随机移动3D粒子在两个不同的时间点。我想知道每个粒子在哪里移动，即跟踪每个粒子，假设它们的总移动尽可能短。
确切的答案将是一个由@tjhighley建议。如果你可以用一个“足够好”的算法来生活，你可以从一个天真的匹配开始，然后将其用于[*退火*]（https://en.wikipedia.org/wiki/Simulated_annealing）。 –