我不知道这是一个众所周知的问题还是可以简化为一个问题，但这是我最近几天以来一直在努力解决的问题。
令 X_1, X_2, X_3 .. X_n 为整数集。
在每个集合 X_i 中，我们有 m 个（对所有集合相等）元素 x_i,j：j = 1...m。
我的目标是从每个集合中选择一个元素，以使所有选定元素之间的成对差异之和最小。
我从一个稍微不同的问题开始，即最小化序列差异之和（即，从连续集合中选择的元素之间的差异之和）。DP 中的前向计算如下：
令 F(i, j) 为从集合 i 中选择元素 j 的成本。
F(i, j) = min_k F(i - 1, k) + |x(i-1,k) - x(i, j)|
也就是说，我们在前一个集合中选择第 k 个元素，然后评估在当前集合中选择第 j 个元素的成本。当前步骤的成本等于集合 i-1 中的第 k 个元素与集合 i 中的第 j 个元素之间的绝对差。
但是，我真正的问题并不取决于集合 X_1，... X_n 的顺序。从本质上讲，动态规划给了我一些东西，但正如我所说，这是一个相关但不同的问题，即从每个集合中找到元素的“链”，以使“串行”差异的总和最小化。
从基本分析来看，我看到这个问题的一个简单的解决方案是生成 n 个集合的所有排列，然后对每个排列使用动态规划来解决它。这是棘手的，但是当 n 足够小时 - 我们甚至可以采用这种愚蠢的穷举方法。
我无法弄清楚这个问题是否可以使用多项式算法来解决，或者是否可以将其简化为已知的 NP-hard/complete 问题之一，在这种情况下，我将通过对其建模来寻求近似算法作为一个二次程序。
请给我建议或指点我一些阅读材料。
谢谢。
[编辑 1]
为了方便讨论，这里添加一个例子：
X = [[11, 24, 38], [12, 21, 33], [13, 22], [15, 23]]
解决方案是 24、21、22、23（可能无关紧要，但我的 DP 给了我 11、12、13、15，我特别构建了这个示例以使我的 DP 失败。）。
[编辑 2]
我想这不是一个NP完全问题。我们可以从 DP 扩展的解决方案如下[不确定是否正确，但似乎是这样]：
该解决方案至少包含每组中的一个元素。
因此，让我们选择任何一组（最好是最小的，如果大小不同），然后将其从列表中删除。
让我们称它为 X\Xp，其中 Xp 是移除的集合。
现在对于 \Xp 中的每个元素 x，构造一个新集合 X' = X\Xp U {x}。
我们求解 DP m 次并计算目标函数（成对距离之和），然后我们可以从中选出最好的。
DP 本身需要 O(nm^2) 并且我们运行这个 m 次，所以我们有 O(nm^3)。