如何确定最佳秩序以最大限度地发挥影响

免责声明：这个问题更多的是与纯Python代码（或Excel求解器）问题相关的algorithm问题

我们目前正在将600多个网站迁移到新平台。 部分工作是将组件（30+）的代码移植到新平台。 为了解决这个问题，我们已经对每个站点上的每个组件的使用情况进行了清点：

现在，我们应该find我们要以何种顺序移植组件。 基本规则如下：一旦给定网站使用的所有组件被移植，网站就可以被移植。

目标是尽可能最大限度地提高我们可以迁移的地点的数量。

在我的例子中：

• 如果我们开始移植比较。 B，即使比较，我们也无法迁移网站。 B被大量使用。 所以我不会从Comp开始的。 B.
• 如果我们开始移植比较。 A，我们将能够迁移站点2并与其他站点一起前进。 因此，Comp。 A可能是一个很好的候选人
• 那么，我们可以转向Comp。 C，Comp。 D和最后比较。 乙

这是相当容易的4个组件和5个网站，但是与我们必须处理的数额是一个真正的噩梦。

什么将是一个系统的方法？

Answer 1

虽然这是NP难的（见这个问题的certificate ），只有30个组件，你应该能够通过使用旅行推销员问题的Held-Karpalgorithm的变体来蛮横强制所有组合。

主要思想是计算一个分数，而不是为每个排列（因为排列太多），而是为每一组你已经build立的组件。

会有2 ^ N套，这比N小得多！ 排列。

为了计算每个集合S的分数，你迭代你添加的最后一个分量x的select，并且将包含x（和S中的其他分量）的所有站点的分数加到先前计算的较小集合的分数上SX。 对于每个集合，您存储可用的最佳分数，以及最后应添加哪个分量。

当您计算出添加所有组件的分数时，您可以通过存储的信息追溯以确定添加组件的顺序。

Answer 2

我将把你有的组件数量概括为N （“N”个组件）。 由于组件重构的顺序影响可以在该时间段内部署的站点的数量，所以这成为排列的最大化。

一组大小为N!的排列的数量是N! ，或factorial(N)

如果你有4个组件，你将有24个不同的排列顺序的组件重构。 从那里，您可以计算每个排列顺序可能迁移的网站数量。

您决定哪个是“最佳”结果。 通过select产生具有第一个组件重构的最多迁移的结果或组件重构的总和来最大化它。 这完全取决于您的业务逻辑。

Answer 3

两种algorithm：

第一个你主要在你的例子中描述的那个。 这样做效率最高，而且所有网站的迁移速度都是最快的，但是可能不会提供更多的网站

• 按照使用它们的站点数（ComponentSiteUsageCount）排列所有组件。
• 计划组件以ComponentSiteUsageCount的降序进行迁移。
• 为每个组件迁移交付（CompomentMigrationDate）

• 一旦给出每个组件的数据，规划站点迁移。 迁移所有组件时，可以迁移站点：

  – 对于每个站点，从最后一个ComponentMigrationDate开始，通过ComponentMigrationDate迭代所有组件。 在迭代时，检查网站是否具有该组件，并且网站具有的第一个组件是SiteMigrationDate。

第二个可能会产生更多迁移速度更快的网站

• 生成所有组件的列表。 对于列表中的每个组件，产生只剩下依赖于该组件（SitesPendingOn）的站点的计数。 以最多的一个，并分配一个MigrationOrder（升序号码）。 如果列表中没有剩余此类组件，则为每个剩余（未分配的迁移订单）生成站点使用的计数：ComponentSiteUsageCount。 以最多的一个，并为其分配下一个MigrationOrder。 对未分配MigrationOrder的组件重复循环以获取SitesPendingOn，直到所有组件都已分配MigrationOrder

• 对于每个站点，从最后一个ComponentMigrationDate开始，通过ComponentMigrationDate迭代所有组件。 在迭代时，检查网站是否具有该组件，并且网站具有的第一个组件是SiteMigrationDate。

第二个algorithm代码 “

 import pandas as pd def get_pending_sites(site_components, component, components): count = 0 for index, site in site_components.iterrows(): #print('site ...', site['Site']) if site[component] > 0. and components[component][0] == 0: #print('site uses component') other_dependent = False for site_component in list(site_components.columns.values)[1:]: if site_component != component: if site[site_component] > 0. and components[site_component][0] == 0: #print('site uses other components') other_dependent = True break if other_dependent == False: count += 1 #print('count', count) return count def get_used_sites(site_components, component): count = len(site_components[site_components[component] > 0.]) print ("Component: ", component, " used in sites: ", count) return count def get_most_pending_sites(components): most_count = 0 most_component = None for component in components: if components[component][0] == 0: count = components[component][1] if count > most_count: most_component = component most_count = count elif (count == most_count) and (most_component != None): if components[component][2] > components[most_component][2] : most_component = component return most_component def get_most_used_sites(components): most_count = 0 most_component = None for component in components: if components[component][0] == 0: count = components[component][2] if count > most_count: most_component = component most_count = count return most_component migration_order = 1 site_components = pd.read_csv('site_components.csv') #print(site_components.describe()) components = dict.fromkeys(list(site_components.columns.values)[1:]) for component in components: components[component] = [0, 0, 0] components[component][2] = get_used_sites(site_components, component) #print(components) while True: print("Components: ", components) for component in components: if components[component][0] == 0: print('starting .....', component) components[component][1] = get_pending_sites(site_components, component, components) print('finished .....', component, components[component][1], components[component][2]) while True: most_pending_sites_component = get_most_pending_sites(components) print('most pending sites components: ', most_pending_sites_component) if most_pending_sites_component != None: components[most_pending_sites_component][0] = migration_order migration_order = migration_order + 1 else: break most_used_sites_component = get_most_used_sites(components) if most_used_sites_component != None: components[most_used_sites_component][0] = migration_order migration_order = migration_order + 1 else: break # order of migration in [0] print("Components: ", components) 

假设 ：迁移组件所花费的时间在所有组件中是一致的注意 ：将包含网站和组件的电子表格保存为csv，并将所有总计垂直和水平