集合选取算法优化咨询：问题命名与高效解法探讨

问题背景 #

我正在解决以下问题：

• 拥有若干含重复元素的阻塞集合（blocked sets）；
• 需从每个阻塞集合中选取指定数量的元素以解除其阻塞；
• 仅能选取同时存在于选取集合（picking set）中的元素；
• 从阻塞集合移除元素时，必须同时从选取集合中移除该元素；
• 选取集合的元素数量可能多于或少于需求值。

示例说明 #

最简示例 #

//阻塞集合语法：
//名称（需选取元素数量）：{集合元素}

//选取集合语法：
//名称：{集合元素}

BS1 (1): {0, 1}
BS2 (1): {1, 2}
Picking Set: {1, 2}

可行解：

BS1 (1): {0, 1}     <- take 1
BS2 (1): {1, 2}     <- take 2
Picking Set: {1, 2} <- remove 1, 2

若从BS2中选取1，则问题无解：选取集合将变为{2}，而BS1仅含{0,1}，无法完成后续选取。

复杂场景 #

BS1 (1): {1, 2, 4} 
BS2 (2): {2, 3, 4} 
BS3 (3): {1, 3, 4, 4} 
Picking Set: {1, 2, 3, 4, 4, 4}

可行解：

BS1 (1): {1, 2, 4}              <- take 1
BS2 (2): {2, 3, 4}              <- take 2, 4 
BS3 (3): {1, 3, 4, 4}           <- take 3, 4, 4
Picking Set: {1, 2, 3, 4, 4, 4} <- remove all

该场景存在多种可行解，但部分选取会导致死局：

BS1 (1): {1, 2, 4}              <- take 1
BS2 (2): {2, 3, 4}              <- take 2, 3 
BS3 (3): {1, 3, 4, 4}           <- take 4, 4, and then dead end
Picking Set: {1, 2, 3, 4, 4, 4} <- remove all but one 4

现有解法 #

我编写了递归暴力算法，测试所有选取组合及后续集合的组合，虽可行但速度慢。组合数会随着规模扩大爆炸式增长，不过约半数分支可成功找到解，因此希望找到能直接构造有效解的启发式或其他更高效方法。

疑问 #

1. 该问题是否有标准命名？
2. 构造有效解的最快方式是什么？
3. 是否存在优于暴力法的方案（无需试错即可生成有效解）？

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