У нас есть 2 списка (черный и красный), каждый из которых содержит несколько точек в трехмерном пространстве.Мы должны переместить каждую черную точку в красную точку и сделать это таким образом, чтобы общее расстояние, на которое можно было сделать ходы, было наименьшим.Списки могут быть разных размеров.
Простое правильное решение в 2D-пространстве: 
Неправильное решение: 
Если размеры списков различаются, мы должны либо сложить точки друг над другом, либо разбить одну точку на несколько точек.
Пример разделения: 
Пример стека: 
Наша лучшая попытка решить эту проблему состоит из следующих общих шагов:
Если красных точек больше, чем черных, выберите черную точку, наиболее удаленную от всей красной точки, и сопоставьте ее с красной точкой, которая находится ближе всего к ее положению и еще не сопоставлена.
Повторяйте шаг 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);
}
}
Этот метод работает для простых фигуркак кубики.
Однако он начинает действовать, когда позиции куба пересекаются в трехмерном пространстве от одного набора точек к другому.
И это делает еще более забавные вещи с более сложными точками: 
Я не совсем уверен, почему это сломается, и я не мог придуматьпростой 2D-пример, где этот подход идет не так, как надо.
Мы испробовали 3 различных метода в течение 3 очень долгих дней и, похоже, не можем найти решение этой, казалось бы, простой проблемы.