python - 如何确定最佳顺序以最大化影响

Question

免责声明:此问题与算法问题的关系比纯 python 编码(或 Excel 求解器)问题更多

我们目前正在将 600 多个网站迁移到新平台。部分工作是将我们的组件(30 多个)代码移植到新平台。为了完成这项工作，我们盘点了每个站点上每个组件的使用情况:

现在，我们应该找到移植组件的顺序。基本规则如下:只要移植了给定网站使用的所有组件，就可以迁移该网站。

目标是尽可能多地迁移我们可以尽早迁移的站点。

在我的例子中:

• 如果我们从移植 Comp 开始。 B，我们将无法迁移网站，即使 Comp。 B 被大量使用。因此我不会从 Comp 开始。 B.
• 如果我们从移植 Comp 开始。答，我们将能够迁移站点 2 并继续迁移到另一个站点。因此，比较。 A 可能是一个不错的候选人
• 然后，我们可以转到 Comp。 C，比较。 D，最后是 Comp。 B

对于 4 个组件和 5 个站点，这相当容易，但对于我们必须处理的数量来说，这真是一场噩梦。

什么是系统方法？

Answer 1

虽然这是 NP-hard(参见 question for a proof)，但只有 30 个组件，您应该能够通过使用 the Held-Karp algorithm 的变体来暴力破解所有组合。对于旅行商问题。

主要思想是计算一个分数，不是针对每个排列(因为排列太多)，而是针对您构建的每组组件。

会有2^N套，比N!排列。

为了计算出每个集合 S 的分数，您迭代了您添加的最后一个组件 x 的选择，并将完成包括 x(和 S 中的其他组件)的所有站点的分数添加到先前计算的分数较小的集合 S-x。对于每个集合，您存储可用的最佳分数，以及应该最后添加哪个组件。

当您计算出添加所有组件的分数后，您可以回溯存储的信息以计算出添加组件的顺序。