从二维数组寻找最短元素集合的算法优化问询

问题描述 #

给定二维数组（示例如下），需找到最短元素集合，确保集合包含数组每一行的至少一个元素：

A  B  C  D  E
   --------------
1 | 0  2  3  4  5
2 | 1  2  4  5  6
3 | 1  3  4  5  6
4 | 2  3  4  5  6
5 | 1  2  3  4  5

示例情况：

• 选取每行首元素得到集合 {0,1,1,2,1}，去重后长度为3；
• 选取 {1B,2A,3A,4A,5A} 得到集合 {2,1,1,2,1}，去重后长度为2；
• 最优解如选取 {1D,2C,3C,4C,5D}，对应元素均为4，集合长度为1。

对于大规模数组（如495行×28列），暴力遍历所有列组合（共28^495种）完全不可行，必须采用高效算法。

问题本质与高效解法 #

该问题属于**击中集（Hitting Set）**问题，是NP-hard问题，不存在多项式时间精确解法，但针对每行元素数量少（仅28个）的场景，可采用以下实用方案：

1. 贪心算法（快速近似最优解） #

核心逻辑：每次选择覆盖最多未覆盖行的元素，重复至所有行被覆盖。时间复杂度为O(R×E)（R为行数，E为不同元素数量），解长度不超过最优解的log(R)倍，适合大规模数据快速求解。

2. 二分查找+回溯（精确最优解） #

核心逻辑：通过二分查找确定最小集合大小k，再用回溯法验证是否存在大小为k的集合覆盖所有行。针对较小的k（如1、2）验证效率极高；k较大时，可通过剪枝策略（如剩余元素不足以覆盖未覆盖行时终止分支）提升速度。

示例代码 #

贪心算法实现（C#） #

using System;
using System.Collections.Generic;
using System.Linq;

public class HittingSetSolver
{
    public static HashSet<long> FindGreedyHittingSet(List<List<long>> matrix)
    {
        var uncoveredRows = new HashSet<int>(Enumerable.Range(0, matrix.Count));
        var solution = new HashSet<long>();

        while (uncoveredRows.Any())
        {
            // 统计每个元素覆盖的未被覆盖行数
            var elementCoverage = new Dictionary<long, int>();
            foreach (var rowIndex in uncoveredRows)
            {
                foreach (var element in matrix[rowIndex])
                {
                    elementCoverage.TryAdd(element, 0);
                    elementCoverage[element]++;
                }
            }

            // 选择覆盖行数最多的元素
            var bestElement = elementCoverage.OrderByDescending(kv => kv.Value).First().Key;
            solution.Add(bestElement);

            // 标记包含该元素的行为已覆盖
            var rowsToRemove = uncoveredRows.Where(rowIndex => matrix[rowIndex].Contains(bestElement)).ToList();
            foreach (var rowIndex in rowsToRemove)
                uncoveredRows.Remove(rowIndex);
        }

        return solution;
    }

    // 测试示例
    public static void Main()
    {
        var matrix = new List<List<long>>
        {
            new List<long> {0,2,3,4,5},
            new List<long> {1,2,4,5,6},
            new List<long> {1,3,4,5,6},
            new List<long> {2,3,4,5,6},
            new List<long> {1,2,3,4,5}
        };

        var result = FindGreedyHittingSet(matrix);
        Console.WriteLine("贪心算法得到的最短集合：");
        foreach (var elem in result)
            Console.Write(elem + " ");
        // 输出：4（符合最优解）
    }
}

精确解法（二分查找+回溯）片段 #

using System;
using System.Collections.Generic;
using System.Linq;

public class ExactHittingSetSolver
{
    private static HashSet<long> _bestSolution;
    private static List<List<long>> _matrix;
    private static int _targetSize;

    public static HashSet<long> FindExactHittingSet(List<List<long>> matrix)
    {
        _matrix = matrix;
        var allElements = matrix.SelectMany(row => row).Distinct().ToList();
        _bestSolution = new HashSet<long>(allElements); // 初始最优解为所有元素

        // 二分查找最小k
        int left = 1, right = allElements.Count;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            _targetSize = mid;
            Backtrack(0, new HashSet<long>(), new HashSet<int>(Enumerable.Range(0, matrix.Count)));
            
            if (_bestSolution.Count <= mid)
                right = mid - 1;
            else
                left = mid + 1;
        }

        return _bestSolution;
    }

    private static void Backtrack(int elementIndex, HashSet<long> currentSet, HashSet<int> uncoveredRows)
    {
        // 剪枝：当前集合已不优于最优解，或剩余元素不足以凑够目标大小
        if (currentSet.Count >= _bestSolution.Count || 
            currentSet.Count + (_matrix.SelectMany(row => row).Distinct().Count() - elementIndex) < _targetSize)
            return;

        // 所有行已覆盖，更新最优解
        if (!uncoveredRows.Any())
        {
            if (currentSet.Count < _bestSolution.Count)
                _bestSolution = new HashSet<long>(currentSet);
            return;
        }

        var allElements = _matrix.SelectMany(row => row).Distinct().ToList();
        if (elementIndex >= allElements.Count)
            return;

        // 选择当前元素
        long element = allElements[elementIndex];
        var newUncovered = new HashSet<int>(uncoveredRows.Where(row => !_matrix[row].Contains(element)));
        currentSet.Add(element);
        Backtrack(elementIndex + 1, currentSet, newUncovered);
        currentSet.Remove(element);

        // 不选择当前元素
        Backtrack(elementIndex + 1, currentSet, uncoveredRows);
    }
}

说明 #

• 贪心算法适合大规模数据快速求解，结果接近最优；
• 精确解法能找到最优解，但k较大时耗时较长，可根据需求选择；
• 可结合两者：先用贪心算法得到初始最优解，再用回溯法尝试寻找更小解，减少剪枝负担。

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