我不知道这是一个众所周知的问题，还是可以归结为一个问题，但这是我最近几天一直在努力解决的问题。
设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_kF（i-1，k）+|x（i-1、k）-x（i，j）|
也就是说，我们选择前一集中的第k个元素，然后评估选择当前集中的第j个元素的成本。当前步骤的成本等于集合i-1中的第k个元素和集合i中的第j个元素之间的绝对差。
然而，我真正的问题并不取决于集合X_1，…的阶。。。X_ n。从本质上讲，动态编程给了我一些东西，但正如我所说，这是一个相关但不同的问题，即从每个集合中找到一个元素的"链"，从而使"串行"差异的总和最小化。
从一个基本的分析中，我看到这个问题的一个简单的解决方案是生成n个集合的所有排列，然后对每个排列使用动态规划来解决它。这很难解决，但当n足够小时，我们甚至可以采取这种愚蠢的穷举方法。
我无法弄清楚这个问题是否可以使用多项式算法来解决，或者是否可以将其简化为已知的NP难/完全问题之一，在这种情况下，我将通过将其建模为二次规划来寻求近似算法。
请给我建议或给我指一些阅读材料。
谢谢。
[编辑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）。
这可以减少以在加权图中找到最小权重团。不同集合中的任何两个节点的权重都等于其差值的绝对值。
我不认为这是NP完全的，因为我认为我们最多可以用O（n^2m^2）个猜测来找到和识别一个解。
为了不担心平局，从整数到实数，添加少量抖动。我认为这是随机的，但我认为你可以选择确定性抖动来达到同样的效果。
把这个问题想象成从布置在实线上的彩色点集合中进行选择，以便从每种颜色中选择一个点，并将它们之间的绝对差异之和最小化。
我只考虑n为偶数的情况。解算点集的中值出现在两个中心点之间。对于解集中的每个点，在它和两个中心点之间都没有相同颜色的点（或者我们可以改进解）。出于同样的原因，如果我们将其从解集中移除，则每个点都是该颜色与我们得到的n-1个点的中值最近的点。
使用我们的（nm）^2猜测，我们猜测解集中两个中心点的同一性。这给我们留下了n-2个点，我们可以将每种颜色的可能性减少到两个，最接近这两个点两侧两个中心点的点。
现在考虑通过从解集中移除一个点而形成的中值。如果我们移除的点在两个中心点的右侧，则中值在这两个点的左侧。如果我们移除的点在左侧，则中值在这两个点的右侧。在一个解集中，我们刚刚删除的点比该颜色的任何其他点都更接近新的中值，而新的中值是离它两个中心点中更远的一个。因此，我们可以将它与同一颜色的其他候选点区分开来-它是两者中最接近两个中心点中更远的那个。
因此，通过最多进行O（n^2*m^2）次猜测，我们可以为每个get找到一个可能的解集，并从这些解集中选择目标最小的解集来获得全局最小值。每个猜测都需要一些工作——也许O（m），所以这很可能是一个O（n^2m^3），有一个完全天真的实现——也许主要是一种理论方法。
也许这太好了，不可能是真的，但我们能把它变成一个简单地检查数据中的每个点以及最接近它的其他颜色的点的证据吗？一个论点是，如果我们有两个点，并且我们可以识别出解中的每个点最接近这两个点中最远的一个，那么这个点也必须最接近这对中的另一个点。因此，猜测这对中的任何一点并找到最接近它的点可能会奏效。这开始看起来很像Evgeny Kluev的解决方案的证明