我们有2个列表(黑色和红色),每个列表包含3d空间中的多个点。我们必须将每个黑点移动到一个红点,并以这样的方式进行,即移动的总距离是最小的。列表可以具有不同的大小。
在2D空间中简单正确的解决方案:qazxsw poi
如果列表的大小不同,那么我们必须将点堆叠在彼此之上或将一个点分成多个点。
我们对此问题的最佳尝试遵循以下一般步骤:
一些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种不同的方法,似乎无法找到解决这个看似简单问题的方法。
您可以将其解释为,其中黑点是“代理”,红点是“任务”(反之亦然),它们之间的距离是成本。
问题实例有许多代理和许多任务。可以分配任何代理来执行任何任务,从而产生一些可能因代理 - 任务分配而异的成本。需要通过为每个任务准确分配一个代理并为每个代理分配一个任务来执行所有任务,从而最大限度地降低分配的总成本。
分配问题可以使用the Assignment problem在多项式时间内求解。问题的变化涉及The Hungarian algorithm,您可以将其应用于列表大小不同的特殊情况。
如果你想要一个应该给出不错的结果的“快速'脏”解决方案,可以考虑将你当前的算法调整为概率算法。根据距离黑点的距离对每个附近的红点进行加权,然后根据它们的权重随机选择一个红点。你可能想要对距离进行平方(甚至是立方体),以阻止选择更远的点。总的来说,它应该选择许多与原始算法相同的点,但这里和那里有一些差异。尽可能多地重复,并选择最佳结果。
如果你想要一些不那么浪漫的东西,可以考虑将问题建模为不对称的旅行商问题。将每个黑点连接到每个红点,其重量的方向边缘与它们之间的欧氏距离成比例。然后将每个红点连接到每个黑点,使用权重为0的方向边。然后使用现有的非对称TSP求解器求解,然后根据需要添加额外的节点+连接。但是请注意,这将丢弃许多有用的信息(例如,我们并不特别关心我们下一步连接哪个黑色节点),以换取能够使用现有软件和经过验证的启发式和优化。