基于寻路算法的可变尺寸网格单元格组合高效生成方案咨询

我正在开展一个项目，需从指定起点出发，在N×M网格中生成所有符合要求的单元格组合，需避开无效单元格（黑色填充单元格）。网格中每个单元格宽高可不同，组合形状整体不得超过设定的MAX_WIDTH与MAX_HEIGHT，移动方向支持上、右、下、左四个方向。当前尝试DFS递归实现，但仅适用于小型网格，希望寻求高效生成所有组合或仅最大组合的方案，考虑采用Dijkstra、A*等寻路算法，也可根据顶点数量等维度为形状打分。

CombinationCreator类 #

public class CombinationCreator
{
    /// <summary>
    /// 包含单元格二维数组的网格
    /// </summary>
    private readonly Grid _grid; 
    /// <summary>
    /// 当前单元格组合形状的状态，用于递归函数
    /// </summary>
    private List<Cell> CurrentState { get; set; } = new List<Cell>();

    /// <summary>
    /// 扫描单元格时使用的方向列表
    /// </summary>
    private readonly List<(int row, int column)> Directions = new List<(int row, int column)>()
    {
        (0, 1), // 右
        (1, 0), // 下
        (0, -1), // 左
        (-1, 0) // 上
    };

    /// <summary>
    /// 所有可能的组合列表
    /// </summary>
    public List<List<Cell>> Results { get; set; } = new List<List<Cell>>();

    public CombinationCreator(Grid grid)
    {
        _grid = grid;
    }

    /// <summary>
    /// 获取单元格的i、j索引（作为起始索引）
    /// </summary>
    public List<List<Cell>> GetCombinations(int i, int j)
    {
        double MAX_WIDTH = 4;
        double MAX_HEIGHT = 7;
        List<List<Cell>> result = new List<List<Cell>>;
        return GenerateCombination(i, j, MAX_WIDTH, MAX_HEIGHT);
    }

    /// <summary>
    /// 通过扫描网格生成所有可能单元格组合的递归函数
    /// </summary>
    private void GenerateCombinations(int i, int j, double maxWidth, double maxHeight, int depth = 0, double minX = double.MaxValue,
        double maxX = double.MinValue, double minY = double.MaxValue, double maxY = double.MinValue)
    {
        if (depth > 50)
        { // 防止无限递归
            return;
        }

        if (ShouldSavePreviousState(i, j, maxWidth, maxHeight, minX, maxX, minY, maxY))
        { // 如果当前单元格会超出maxWidth和maxHeight，则保存之前的状态
            Results.Add(new List<Cell>(CurrentState));
        }
        else
        {
            if (i >= 0 && i < _grid.Cells.GetLength(0) &&
                j >= 0 && j < _grid.Cells.GetLength(1))
            {
                Cell currentCell = _grid.Cells[i, j];

                if (!currentCell.Marked && currentCell.Valid && !currentCell.IsUsed)
                {
                    currentCell.Marked = true;
                    CurrentState.Add(currentCell);

                    minX = Math.Min(minX, currentCell.TopLeft.x);
                    maxX = Math.Max(maxX, currentCell.BottomRight.x);
                    minY = Math.Min(minY, currentCell.BottomRight.y);
                    maxY = Math.Max(maxY, currentCell.TopLeft.y);

                    foreach (var direction in Directions)
                    { // 遍历所有方向
                        int newRow = i + direction.row;
                        int newCol = j + direction.column;

                        GenerateCombinations(newRow, newCol, maxWidth, maxHeight, depth + 1, minX, maxX, minY, maxY);
                    }

                    CurrentState.RemoveAt(CurrentState.Count - 1);
                    currentCell.Marked = false;
                }
            }
        }
    }

    /// <summary>
    /// 检查当前单元格是否会超出maxWidth和maxHeight，或者处于边界，若是则保存之前的状态
    /// </summary>
    private bool ShouldSavePreviousState(int i, int j, double maxWidth, double maxHeight, double minX = double.MaxValue,
        double maxX = double.MinValue, double minY = double.MaxValue, double maxY = double.MinValue)
    {
        double currentWidth = maxX - minX;
        double currentHeight = maxY - minY;

        if (i >= 0 && i < _grid.Cells.GetLength(0) &&
            j >= 0 && j < _grid.Cells.GetLength(1))
        {
            Cell currentCell = _grid.Cells[i, j];

            if (!currentCell.Marked && currentCell.Valid && !currentCell.IsUsed)
            {
                double nextMinX = Math.Min(minX, currentCell.TopLeft.x);
                double nextMaxX = Math.Max(maxX, currentCell.BottomRight.x);
                double nextMinY = Math.Min(minY, currentCell.BottomRight.y);
                double nextMaxY = Math.Max(maxY, currentCell.TopLeft.y);

                double nextWidth = nextMaxX - nextMinX;
                double nextHeight = nextMaxY - nextMinY;

                if (nextHeight > maxHeight || nextWidth > maxWidth)
                {
                    return true;
                }
            }

            if (!currentCell.Valid || currentCell.IsUsed)
            {
                if (currentHeight > maxHeight || currentWidth > maxWidth)
                {
                    return false;
                }
                return true;
            }
        }

        return false;
    }
}

Cell类 #

public class Cell
{
    public bool Marked { get; set; } // 标记单元格是否已在扫描中访问过
    public bool Valid { get; set; } // 标记单元格是否可用（白色单元格）
    public bool IsUsed { get; set; } // 标记单元格是否已被其他形状使用
    public Point TopLeft { get; set; } // 左上角坐标点
    public Point BottomRight { get; set; } // 右下角坐标点
}

一、仅生成最大组合的方案 #

1. A*启发式搜索 #

• 状态定义：每个状态包含当前选中的单元格集合、组合边界（minX/maxX/minY/maxY）、已选单元格数量（核心优先级指标）。
• 启发函数：估算当前状态可扩展的最大单元格数，比如统计当前边界内剩余的有效未使用单元格数量，或基于连通性做乐观估计。
• 优先级队列：优先扩展已选单元格数量最多的状态，一旦找到无法再扩展的状态，即可作为候选最大组合，后续直接剪枝所有已选数量小于该值的分支。

2. 分支限界法 #

• 维护当前找到的最大组合的单元格数maxCount，搜索过程中若当前状态已选数量+剩余可添加最大数量 < maxCount，直接剪枝该分支。
• 剩余可添加最大数量可提前预处理：比如计算每个单元格所在连通区域的有效单元格总数，或基于当前边界统计剩余有效单元格。

二、生成所有组合的优化方案 #

1. 记忆化与状态去重 #

• 用哈希表记录已处理过的状态（比如用单元格坐标集合的哈希值作为键），避免重复处理相同组合；若无需区分旋转/翻转的相同组合，可进一步简化状态表示。
• 优化状态存储：不用保存完整单元格列表，改用起始点+已选单元格相对坐标集合，或二进制掩码（网格规模适中时）。

2. 迭代式DFS替代递归 #

• 递归深度限制会丢失部分组合，改用栈模拟递归过程的迭代式DFS，避免栈溢出，同时更灵活控制遍历逻辑。

3. 强化剪枝策略 #

• 提前计算单元格加入后的尺寸变化，在进入搜索前过滤掉会超出MAX_WIDTH/MAX_HEIGHT的方向。
• 对搜索方向排序：优先选择组合尺寸增长较慢的方向，或优先填充密集区域，减少无效分支。

三、通用优化点 #

• 预处理网格：提前计算每个有效单元格的连通区域，仅在连通区域内搜索，避免跨无效单元格的无效遍历。
• 尺寸计算优化：在状态中维护当前组合的边界值，添加单元格时直接更新，减少重复计算。

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