求解最小化子集跨度问题：适配的经典算法咨询

给定一组正整数集合的列表，需从每个集合中选取一个数组成新列表，使得该列表的最大值与最小值的差值（跨度）尽可能小。

示例：

numbers = [
  (0, 4, 9),
  (3, 5),
  (7, 8, 9)
]

满足条件的选取结果为 [4, 5, 7]，对应的跨度为 3。

现有思路 #

我已构思两种基础解法，均从第一个集合开始逐步构建结果列表：

• 深度优先搜索（DFS）遍历所有可能的选取路径，同时记录当前找到的最小跨度，一旦当前路径的潜在跨度超过已记录的最小值，就终止该路径的搜索。
• 通过二分查找，为每个集合筛选出与前一个选中数最接近的两个数（一个大于、一个小于该数），缩小搜索空间后再进行深度优先搜索，但不确定这种方法能否得到全局最优解。

我认为该问题可映射至某类经典搜索算法，但无法确定最优解法，想请教哪些现有算法适合解决这类问题？

1. 分支定界法（Branch and Bound） #

你提到的第一种DFS思路其实是分支定界的雏形，核心是通过剪枝避免无效搜索：

• 维护全局最小跨度，当正在构建的路径中，已选数的当前max-min已经大于等于这个最小值时，直接停止该分支的搜索。
• 可进一步优化：进入下一个集合前，先计算该集合的最小和最大值，预判若选取该集合的数，新的max-min是否可能小于当前最优值，若不可能则直接剪枝。

2. 滑动窗口+优先队列法 #

先将每个集合单独排序，再用小顶堆（优先队列）配合滑动窗口的思路求解，适合集合数量或元素较多的场景：

• 初始时，把每个集合的第一个元素加入堆，同时记录当前堆中元素的max和min，计算初始跨度。
• 每次弹出堆中最小的元素，从它所在的集合取下一个元素加入堆，更新当前的max和min，计算新跨度并更新全局最小值。
• 当某个集合已无下一个元素时，停止循环。这种方法能高效遍历所有可能的“候选最优组合”，时间复杂度优于暴力DFS。

3. 动态规划（DP） #

用DP记录每一步的可能取值范围及对应的跨度，通过状态压缩优化搜索空间：

• 定义dp[i]为处理完前i个集合后，所有可能选取结果的(当前最小值, 当前最大值)对。
• 对于第i+1个集合的每个数num，遍历dp[i]中的每一对(curr_min, curr_max)，计算新的new_min = min(curr_min, num)、new_max = max(curr_max, num)，以及新跨度new_max - new_min。
• 对dp[i+1]去重优化：若存在两对(m1, M1)和(m2, M2)，其中m2 >= m1且M2 <= M1，则丢弃(m1, M1)——因为它的跨度更大，不可能得到更优解。

关于第二种思路的说明 #

你提到的二分筛选后DFS的方法无法保证全局最优。比如可能存在某个集合中，选一个看似偏离前一个数的元素，后续集合能选到更合适的数，最终整体跨度更小的情况。这种局部最优的筛选会错过全局最优路径。

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