将胶带切成梯形时计算零浪费

Question

任务是想出一种算法，将磁带切成给定数量的梯形，并且不浪费。废物是给定梯形位置的截止表面的面积。

梯形高度相同，点A总是(0,0)

n -梯形数

bx - b点的x坐标

cx - c点的x坐标

dx -点d的x坐标

从文件中指定梯形，格式为:

n
b1x c1x d1x
...
bnx cnx dnx
Example:
10
-100 0 500
-900 -100 500
-1400 -400 500
-500 -400 500
-900 -400 500
-1300 500 500
0 400 500
-800 -800 500
-900 -900 500
-600 -300 500

Program.cs

using Minimization;
const int h = 10;
decimal StartArea(int bx)
{
return Math.Abs(bx) * h / 2;
}
decimal EndArea(int cx, int dx)
{
return Math.Abs(cx - dx) * h / 2;
}
decimal Area(int cx, int dx, int bx)
{
return (cx < dx && bx < 0) || (cx > dx && bx > 0) ?
(Math.Abs(cx - dx) - Math.Abs(bx)) * h / 2 :
(Math.Abs(cx - dx) + Math.Abs(bx)) * h / 2;
}
var path = @"c:tests9.txt";
var trapezoids = FileUtilities.GetTrapezoids(path);
List<(int bx, int cx, int dx, int index)> startCandidates = new();
for (var i = 0; i < trapezoids.Length; i++)
{
if (StartArea(trapezoids[i].bx) == 0)
startCandidates.Add((trapezoids[i].bx, trapezoids[i].cx, trapezoids[i].dx, i));
}

var candidates = new Dictionary<int, HashSet<int>>();
for (var i = 0; i < trapezoids.Length; i++)
{
candidates[i] = new HashSet<int>();
for (var j = 0; j < trapezoids.Length; j++)
{
if (i == j) continue;
if (Area(trapezoids[i].cx, trapezoids[i].dx, trapezoids[j].bx) == 0)
candidates[i].Add(j);
}
}
var res = new List<int>();
foreach (var (bx, cx, dx, index) in startCandidates)
{
var currentIndex = index;
var currentList = new List<int> { currentIndex };
res = PossibleList(currentIndex, currentList, trapezoids);
if (res != null)
{
break;
}
}
List<int>? PossibleList(int currentIndex, List<int> currentList, Span<(int bx, int cx, int dx)> trapezoids)
{
var nextCandidates = Except(candidates[currentIndex], currentList);
if (nextCandidates.Count == 0)
if (currentList.Count == candidates.Count && EndArea(trapezoids[currentIndex].cx, trapezoids[currentIndex].dx) == 0)
return currentList;
else
return null;
foreach (var candidate in nextCandidates)
{
var nextList = currentList.ToList();
nextList.Add(candidate);
var possible = PossibleList(candidate, nextList, trapezoids);
if (possible != null)
return possible;
}
return null;
}
HashSet<int> Except(HashSet<int> candidates, List<int> currentList)
{
var res = new HashSet<int>();
foreach (var candidate in candidates)
{
if (!currentList.Contains(candidate))
res.Add(candidate);
}
return res;
}

我使用递归算法来找到下一个点，但是对于文件

中的大量梯形，它运行缓慢。我怎样才能更有效率地做这件事?

Answer 1

我想我可以"证明";通过将问题转换为"定向的"问题，问题是np困难的。旅行推销员问题:

我真的不明白a和b是否总是在顶部，还是a和c。无论如何，这并不重要，你可以标准化，使a, b, c和d是点的x坐标左上，右上，左下和右下。那么我们可以定义重叠overlap(x, y)如下:

public int overlap(int x, int y) {
int dX = x.a - x.b;
int dY = y.c - y.d;
if (dX <= 0) {
if (dY >= 0)
return 0;
return Math.max(dX, dY);
} else {
if (dY <= 0)
return 0;
return -Math.min(dX, dY);
}
}

注意，重叠是0或负的，通常重叠(a, b) !=重叠(b, a)。所以我们可以创建一个有向图，梯形作为顶点，重叠作为边。让我们引入一个新的节点，它与所有其他节点之间的距离为0。现在这个问题对应于一个"定向的"问题。旅行推销员问题:找到通过所有顶点的最短路径，每个顶点访问一次，并在我们开始的同一个顶点结束。所有的解决方案都是找到的最短路线。为了得到梯形的顺序，我们只需要从最短的路径开始和结束(忽略)引入的节点。最短路径的(绝对)长度将是与切割每个梯形的边界框相比节省的胶带量。