我们有两个列表（黑色和红色），每个列表包含三维空间中的多个点我们必须把每一个黑点移到一个红点上，这样移动的总距离是最小的。列表可以有不同的大小。
二维空间中的简单正确解：
错误的解决方案：
如果列表的大小不同，那么我们要么将点堆叠在一起，要么将一个点拆分为多个点。
拆分示例：
堆叠示例：
我们对这个问题的最佳尝试遵循以下一般步骤：
如果红色点多于黑色点，请选择距离所有红色点最远的黑色点，并将其与最接近其位置且尚未匹配的红色点匹配。
重复步骤1，直到所有黑点匹配。
在剩余的红色点上迭代，并将每个点与它们各自最近的黑色点匹配，从而将它们叠加。结果如下：
注意：如果黑点比红点多，那么第一步将寻找最远的红点，并将其与最接近的黑点匹配，然后继续所有相同的颜色交换。
一些C代码：
private void SaveFrames(List<List<Vector3>> frameList) {
List<Dictionary<Vector3, List<Vector3>>> resultingPairs = new List<Dictionary<Vector3, List<Vector3>>>();
for (int iFrame = 0; iFrame < frameList.Count+1; iFrame++) {
List<Vector3> currentFrame = frameList[iFrame % frameList.Count];
List<Vector3> nextFrame = frameList[(iFrame + 1) % frameList.Count];
int maxIterations = Mathf.Min(currentFrame.Count, nextFrame.Count);
Dictionary<Vector3, List<Vector3>> pairs = new Dictionary<Vector3, List<Vector3>>();
HashSet<Vector3> takenRed = new HashSet<Vector3>();
HashSet<Vector3> takenBlack = new HashSet<Vector3>();
HashSet<Vector3> takenDestination = new HashSet<Vector3>();
bool moreRed = currentFrame.Count < nextFrame.Count;
if (moreRed) {
for (int i = 0; i < maxIterations; i++) {
// Find furthest black point from any red point
float distance = 0;
Vector3 furthestBlack = Vector3.zero;
foreach (Vector3 black in currentFrame) {
if (takenBlack.Contains(black)) continue;
foreach (var red in nextFrame) {
if (Vector3.Distance(black, red) > distance) {
distance = Vector3.Distance(black, red);
furthestBlack = black;
}
}
}
// Find the closest red point to the furthest black point
distance = float.MaxValue;
Vector3 closestRed = Vector3.zero;
foreach (var red in nextFrame) {
if (takenRed.Contains(red)) continue;
if (Vector3.Distance(furthestBlack, red) < distance) {
distance = Vector3.Distance(furthestBlack, red);
closestRed = red;
}
}
if (!pairs.ContainsKey(furthestBlack)) {
pairs[furthestBlack] = new List<Vector3>();
}
if (!takenDestination.Contains(closestRed)) {
pairs[furthestBlack].Add(closestRed);
takenBlack.Add(furthestBlack);
takenRed.Add(closestRed);
takenDestination.Add(closestRed);
}
// Debug.Log("Pair: " + furthestBlack.ToString() + " to " + closestRed.ToString());
}
} else {
for (int i = 0; i < maxIterations; i++) {
// Find furthest red point from any black point
float distance = 0;
Vector3 furthestRed = Vector3.zero;
foreach (Vector3 red in nextFrame) {
if (takenRed.Contains(red)) continue;
foreach (Vector3 black in currentFrame) {
if (Vector3.Distance(black, red) > distance) {
distance = Vector3.Distance(black, red);
furthestRed = red;
}
}
}
// Find the closest black point to the furthest red point
distance = float.MaxValue;
Vector3 closestBlack = Vector3.zero;
foreach (var black in currentFrame) {
if (takenBlack.Contains(black)) continue;
if (Vector3.Distance(furthestRed, black) < distance) {
distance = Vector3.Distance(furthestRed, black);
closestBlack = black;
}
}
if (!pairs.ContainsKey(closestBlack)) {
pairs[closestBlack] = new List<Vector3>();
}
if (!takenDestination.Contains(furthestRed)) {
pairs[closestBlack].Add(furthestRed);
takenBlack.Add(closestBlack);
takenRed.Add(furthestRed);
takenDestination.Add(furthestRed);
}
// Debug.Log("Pair: " + closestBlack.ToString() + " to " + furthestRed.ToString());
}
}
if (currentFrame.Count < nextFrame.Count) {
// For every nextFrame[i], find the closest black point and pair it.
for (int i = currentFrame.Count; i < nextFrame.Count; i++) {
float distance = float.MaxValue;
Vector3 closestBlack = Vector3.zero;
foreach (var black in currentFrame) {
if (Vector3.Distance(nextFrame[i], black) < distance) {
distance = Vector3.Distance(nextFrame[i], black);
closestBlack = black;
}
}
if (!pairs.ContainsKey(closestBlack)) {
pairs[closestBlack] = new List<Vector3>();
}
if (!takenDestination.Contains(nextFrame[i])) {
pairs[closestBlack].Add(nextFrame[i]);
takenDestination.Add(nextFrame[i]);
}
// Debug.Log("Pair: " + closestBlack.ToString() + " to " + nextFrame[i].ToString());
}
}
if (currentFrame.Count > nextFrame.Count) {
// For every currentFrame[i], find the closest red point and pair it.
for (int i = nextFrame.Count; i < currentFrame.Count; i++) {
float distance = float.MaxValue;
Vector3 closestRed = Vector3.zero;
foreach (var red in nextFrame) {
if (Vector3.Distance(currentFrame[i], red) < distance) {
distance = Vector3.Distance(currentFrame[i], red);
closestRed = red;
}
}
if (!pairs.ContainsKey(currentFrame[i])) {
pairs[currentFrame[i]] = new List<Vector3>();
}
if (!takenDestination.Contains(closestRed)) {
pairs[currentFrame[i]].Add(closestRed);
takenDestination.Add(closestRed);
}
// Debug.Log("Pair: " + currentFrame[i].ToString() + " to " + closestRed.ToString());
}
}
resultingPairs.Add(pairs);
}
}
此方法适用于立方体等简单形状。
但是，当立方体位置从一组点到另一组点在三维空间重叠时，它开始起作用。
更有趣的是，它有更复杂的点：
我不太清楚为什么会出现这种情况，我无法想出一个简单的二维例子来说明这种方法哪里出错。
我们在三天的时间里尝试了三种不同的方法，似乎找不到解决这个看似简单问题的办法。
最佳答案
您可以将其解释为the Assignment problem，其中黑色点是“代理”，红色点是“任务”（反之亦然），它们之间的距离是成本。
问题实例具有多个代理和多个任务。任何代理都可以被分配来执行任何任务，这会产生一些成本，这些成本可能因代理任务的分配而异。执行所有任务时，需要为每个任务分配一个代理，并为每个代理分配一个任务，这样分配的总成本就最小化了。
指派问题可以用The Hungarian algorithm在多项式时间内求解。问题的变化涉及more tasks than agents，您可以将其应用于列表大小不同的特殊情况。
关于c# - 从3d空间中的一组点移动到具有最短累积距离的另一组点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54700983/