0

考虑将两组整数值划分为多个子集。这两组存在相同的一组值，但顺序和划分为子集不同。这个想法是将来自第一组的子集与来自第二组的子集链接起来，这样第一组的每个子集中的每个单独的值都链接到第二组的子集的相同单独的值。任何价值都不能与另外两个联系起来。在一个链接步骤中，可以在第一组的仅一个子集与第二组的仅一个子集之间链接多个值。目标是尽可能减少链接步骤的数量。

问题是：是否有算法可以尽可能优化这种链接？

我在线性规划、整数规划、组合优化和运筹学等数学优化的几个领域做了一些研究，但似乎没有一个算法能涵盖这个问题。你们有什么想法、领域或算法来优化这些问题并让我朝着正确的方向前进吗？

例如：

具有两个子集的两组整数：

[[1, 2, 2] [2, 3, 3]]

和

[[1, 2, 3] [2, 2, 3]]。

现在，第一个链接集可以将第一个集 1[1] 的第一个子集与第二个集 2[1] 的第一个子集链接起来。

这是一个步骤，导致 1 - 1 - 1 和 2 - 1 - 1 之间的链接以及 1 - 1 - 2 和 2 - 1 - 2 之间的链接。现在集合将如下所示：

[[ 1, 2 , 2] [2, 3, 3]]

和

[[ 1, 2 , 3] [2, 2, 3]]。

下一步可能是将 1[1] 与 2[2] 链接，从而导致 1 - 1 - 3 和 2 - 2 - 1 之间的链接，集合将如下所示：

[[ 1, 2, 2 ] [2, 3, 3]]

和

[[ 1, 2 , 3] [ 2 , 2, 3]]。

第三步可能是将 1[2] 与 2[1] 链接。导致：

[[ 1, 2, 2 ] [2, 3 , 3]]

和

[[ 1、2、3 ] [ 2、2、3 ]]。

然后第四步可以将 1[2] 链接到 2[2]。导致：

[[ 1, 2, 2 ] [ 2, 3, 3 ]]

和

[[ 1, 2, 3 ] [ 2, 2, 3 ]]，这意味着每个值都是链接的。该解决方案需要四个步骤。

当有更大的集合时，所有子集都可以链接到另一个集合的所有其他子集，但这会导致很多步骤。是否有一种算法可以优化步数？

4

1 回答 1

0

即使这不是答案，但我认为这是定义问题以找到解决方案的一步。

注意：以下输入/输出示例是一个编辑。我不同意拒绝投票，我敦促大家在投票批准或拒绝任何编辑之前仔细阅读。

这将引发关于未仔细投票的讨论。仍然是一个建设性的讨论，但这里不是它的位置。

考虑以下示例：使用第一个列表的第三个子集比使用第二个和第五个子集成本更低（使用子集更少）。 优化链接的例子

算法：

  1. 定义较小的列表：List #2
  2. 创建列表 #2 的所有子列表中所有项目的计数列表。
  3. 您将拥有此计数列表 {[item:count]}：{[1:3], [2:2], [3:1], [4:2], [5:1]}。
  4. 现在，您的问题不是链接（即依赖于索引）子集。它是找到列表#1 的最小子集数。他们的项目将给出计数列表的计数。
  5. 对每种可能的组合进行简单的尝试肯定会得到答案。但我认为从第 4 点开始，我们可以想到一个更好的解决方案，其中包含一些条件来最小化组合尝试。

希望这个建议有助于提示找到解决方案。

于 2018-04-11T07:16:45.153 回答