如何优化胶带切割为梯形的零损耗递归算法性能？

需设计算法将胶带切割为指定数量的梯形，实现零损耗（损耗定义为梯形放置时切割面的面积）。所有梯形高度一致，点A固定为(0,0)，参数说明：

• n：梯形数量
• bx：点B的x坐标
• cx：点C的x坐标
• dx：点D的x坐标

梯形数据从文件读取，文件格式如下：

n
b1x c1x d1x
...
bnx cnx dnx

示例：

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

使用C#递归算法寻找符合要求的切割顺序，代码如下：

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:\tests\9.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;
}

当前递归算法在处理大量梯形数据时运行速度缓慢，请问如何优化该算法以提升效率？

优化方案 #

1. 用位掩码替代列表记录已使用梯形 #

用整数（int/long/ulong，根据n的大小选择）的二进制位标记梯形是否被使用：第k位为1表示第k个梯形已选中。

• 判断梯形是否已使用的时间复杂度降为O(1)
• 传递状态无需复制列表，直接传整数，开销极小

2. 加入记忆化缓存 #

缓存(当前节点, 已使用掩码)的计算结果，避免重复处理相同状态。比如用Dictionary<(int currentIndex, int usedMask), List<int>?>存储每个状态是否有解，已计算过的状态直接返回结果。

3. 替换低效集合操作 #

原Except方法遍历候选集并调用List.Contains（O(n)时间），改用位运算后，直接通过(usedMask & (1 << candidate)) == 0判断候选是否未被使用，无需创建新HashSet。

4. 提前剪枝 #

递归过程中提前排除不可能的路径：

• 若剩余需选择的梯形数量 > 当前节点可达的未使用节点数，直接返回null
• 预处理所有符合结束条件的节点，若当前节点无法到达任何结束节点，直接返回null

5. 迭代替代递归（可选） #

递归在n较大时易出现栈溢出，且调用开销高，可改为迭代式DFS/BFS，用栈/队列保存状态，更可控。

优化后核心代码示例 #

private static Dictionary<(int, int), List<int>?> _memo = new();

List<int>? PossibleList(int currentIndex, int usedMask, Span<(int bx, int cx, int dx)> trapezoids)
{
    var state = (currentIndex, usedMask);
    if (_memo.TryGetValue(state, out var cachedResult))
        return cachedResult;

    var totalCount = trapezoids.Length;
    // 检查是否完成所有选择且符合结束条件
    if (usedMask == (1 << totalCount) - 1)
    {
        var result = EndArea(trapezoids[currentIndex].cx, trapezoids[currentIndex].dx) == 0 ? new List<int> { currentIndex } : null;
        _memo[state] = result;
        return result;
    }

    foreach (var candidate in candidates[currentIndex])
    {
        if ((usedMask & (1 << candidate)) != 0)
            continue; // 已使用过，跳过

        var nextMask = usedMask | (1 << candidate);
        var subPath = PossibleList(candidate, nextMask, trapezoids);
        if (subPath != null)
        {
            subPath.Insert(0, currentIndex);
            _memo[state] = subPath;
            return subPath;
        }
    }

    _memo[state] = null;
    return null;
}

// 调用示例
foreach (var (bx, cx, dx, index) in startCandidates)
{
    var usedMask = 1 << index;
    res = PossibleList(index, usedMask, trapezoids);
    if (res != null)
        break;
}

额外优化点 #

• 预处理所有起始节点（StartArea为0）和结束节点（EndArea为0），避免递归中重复计算
• 对候选集按出度从小到大排序，优先选择分支少的节点，更快找到有效路径
• 若n超过32位，改用ulong或BitArray实现位掩码

内容的提问来源于stack exchange，提问作者Qbic