如何确定最好以扩大影响

Question

免责声明：这个问题更关系到比纯Python编码（或Excel的求解器）问题的算法问题

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

，我们应该在我们要端口，以便部件找到。 基本规则如下：只要给定网站使用的所有组件都移植完毕，就可以迁移该网站。

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

在我的例子：

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

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

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

Answer 1

我将推广到N（“N”组件）的组件数量。由于组件重构的顺序影响可以在该时间段内部署的网站数量，因此这会成为排列的最大化。

排列的一组尺寸N的量N!，或factorial(N)

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

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

Answer 2

虽然这是NP-hard（请参阅此question for a proof），只有30个组件，您应该能够通过使用the Held-Karp algorithm的变体对旅行推销员问题强制所有组合。

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

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

要计算每个集合S的分数，您需要遍历所添加的最后一个分量x的选择，并将包含x（和S中其他分量）的所有网站的分数添加到先前计算的分数中对于较小的集合Sx。对于每组存储可用的最高分数，以及最后应添加哪个组分。

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

Answer 3

两种算法：

第一你在你的例子大多描述的一个。这给出了最有效的，并完成所有站点最快的迁移，但可能不是一个，让更多站点的前期

• 使用它们（ComponentSiteUsageCount）安排由网站的数量所有组件。
• 计划组件按ComponentSiteUsageCount的降序迁移。
• 给出每个组件移植交付的日期（CompomentMigrationDate）

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

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

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

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

• 对于每个站点，通过ComponentMigrationDate由最后ComponentMigrationDate开始的所有组件进行迭代。在迭代过程中，检查网站是否具有该组件，并且该网站具有的第一个组件是SiteMigrationDate。保存具有电子表格：它需要迁移一个组件是所有组件的统一 注意时间：

对于第二种算法 '

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，并删除所有总计纵向和横向