c# - 从 3d 空间中的一组点移动到具有最短可能累积距离的另一组点

Question

我们有 2 个列表（黑色和红色），每个列表都包含 3d 空间中的多个点。我们必须将每个黑点移动到一个红点，并且这样做的方式是使移动的总距离尽可能小。列表可以有不同的大小。

二维空间中的简单正确解：

不正确的解决方案：

---

如果列表的大小不同，那么我们必须将点堆叠在一起，或者将一个点拆分为多个点。

拆分示例：

堆叠示例：

---

我们对这个问题的最佳尝试遵循以下一般步骤：

1. 如果红点多于黑点，则选择距离所有红点最远的黑点，并将其与最接近其位置且尚未匹配的红点匹配。

2. 重复步骤 1，直到所有黑点都匹配。

3. 遍历剩余的红点并将每个红点与它们各自最近的黑点相匹配，从而将它们堆叠起来。结果将如下所示：

4. 注意：如果黑点多于红点，则第一步将寻找最远的红点并将其与最近的黑点匹配，然后按照相同的颜色交换颜色。

一些 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);
        }
}

此方法适用于立方体等简单形状。

但是，当立方体位置在 3d 空间中从一组点到另一组重叠时，它开始起作用。

它甚至可以用更复杂的点做更时髦的东西：

我不确定为什么会出现这种情况，而且我无法想出一个简单的 2D 示例来说明这种方法出错的地方。

我们在 3 天很长的时间里尝试了 3 种不同的方法，但似乎无法找到解决这个看似简单的问题的方法。

标签： c#algorithmgraph-theorygraph-algorithmgraph-traversal

Answer 1

您可以将此解释为分配问题，其中黑点是“代理”，红点是“任务”（反之亦然），它们之间的距离是成本。

问题实例有许多代理和许多任务。可以分配任何代理来执行任何任务，产生的成本可能会因代理任务分配而异。需要通过为每个任务准确分配一个代理并为每个代理准确分配一个任务来执行所有任务，以使分配的总成本最小化。

分配问题可以使用匈牙利算法在多项式时间内解决。问题的变体涉及比代理更多的任务，您可以将其应用于列表大小不同的特殊情况。