如何確定最好以擴大影響

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，並刪除所有總計縱向和橫向