충격

Question

면책 조항을 극대화하는 최적의 순서를 결정하는 방법 :이 문제는 (또는 Excel 해결사) 질문을 코딩 순수한 파이썬보다 알고리즘 질문에 더 관련이 우리는 현재 새로운 플랫폼으로 600 개 웹 사이트를 마이그레이션하는

. 이 작업의 일부는 구성 요소 코드 (30+)를 새 플랫폼으로 이식하는 것입니다. 는이 일을 해결하기 위해, 우리는 각 사이트에서 각 구성 요소의 사용을 목록 화 한 :

이제, 우리는 우리가 구성 요소 포트로 이동하는 순서대로 찾아야한다. 기본 규칙은 다음과 같습니다. 주어진 웹 사이트에서 사용되는 모든 구성 요소가 포팅 되 자마자 웹 사이트를 이전 할 수 있습니다.

가능한 한 빨리 마이그레이션 할 수있는 사이트의 수를 최대화하는 것이 목표입니다. 내 예에서

:

• 우리가 경화제를 포팅하여 시작합니다. B와 비교해도 사이트를 이전 할 수는 없습니다. B가 많이 사용됩니다. 그러므로 나는 Comp로 시작하지 않을 것이다. B.
• 우리가 Comp. A를 통해 사이트 2를 이전하고 다른 사이트와 함께 이동할 수 있습니다. 따라서 Comp. A는 아마 좋은 후보 일 것입니다.
• 그러면 우리는 Comp. C, Comp. D와 마지막으로 Comp. B

이것은 4 개의 구성 요소와 5 개의 사이트에서 상당히 쉽지만 처리해야 할 금액으로는 정말 악몽입니다.

체계적인 접근 방식은 무엇입니까?

Answer 1

나는 구성 요소의 수를 N ("N"구성 요소)으로 일반화합니다. 구성 요소 리펙터의 순서가 해당 시간 인스턴스에 배포 할 수있는 사이트의 양에 영향을 미치기 때문에 이것은 순열의 극대화가됩니다. 당신이 4 개 구성 요소는 구성 요소 리팩토링의 순서 24 별개의 순열을해야합니다있는 경우

크기 N의 집합에 대한 순열의 양은 N!, 또는

factorial(N)입니다. 여기에서 각 순열 순서에 따라 마이그레이션 될 수있는 가능한 사이트의 양을 계산할 수 있습니다.

"최적의"결과를 결정하십시오. 첫 번째 구성 요소 리팩터 또는 구성 요소 리펙터의 합으로 가장 많은 마이그레이션을 생성하는 결과를 선택하여 최대화하십시오. 그것은 비즈니스 로직에 전적으로 의존합니다.

Answer 2

NP 하드 (참조 : question for a proof)이지만 30 개 구성 요소 만 있으면 여행 판매원 문제에 변형 the Held-Karp algorithm을 사용하여 모든 조합을 무차별 적으로 수행 할 수 있어야합니다.

주요 개념은 각 순열이 아니라 (순열이 너무 많기 때문에) 점수를 계산하는 것이지만, 사용자가 만든 각 구성 요소 집합에 대해 점수를 계산하는 것입니다.

N^2 세트보다 훨씬 작은 2^N 세트가 있습니다. 순열.

각 세트 S에 대한 점수를 계산하려면 추가 한 마지막 구성 요소 x의 선택을 반복하고 x (및 S의 다른 구성 요소)가 포함 된 모든 사이트를 완성하기위한 점수를 이전에 계산 된 점수에 추가하십시오 더 작은 집합 Sx에 대해서. 각 세트에 대해 사용 가능한 최상의 점수와 마지막에 추가해야하는 구성 요소를 저장합니다.

모든 구성 요소를 추가하기 위해 점수를 계산 한 후에는 저장된 정보를 추적하여 구성 요소 추가 순서를 해결합니다.

Answer 3

두 알고리즘 :

첫 당신이 당신의 예에서 주로 설명하는 하나. 이것은 가장 효율적으로 제공하고, 모든 사이트에 가장 빠른 마이그레이션을 완료,하지만

• 그들 (ComponentSiteUsageCount)를 사용하여 사이트의 수 모든 구성 요소를 정렬 선행 더 많은 사이트를주는 일하지 않을 수 있습니다.
• 계획 구성 요소가 ComponentSiteUsageCount의 내림차순으로 마이그레이션됩니다.
• 각 구성 요소 마이그레이션 배달 날짜를 지정하십시오 (CompomentMigrationDate)

• 일단 각 구성 요소에 데이터가 제공되면 사이트 마이그레이션 계획을 세웁니다. 모든 구성 요소를 마이그레이션 할 때 사이트는 마이그레이션 할 수 있습니다 :

  을 - 각 사이트에 대해 지난 ComponentMigrationDate에 의해 시작 ComponentMigrationDate 모든 구성 요소를 통해 반복. 반복하면서 사이트에 해당 구성 요소가 있는지 확인하고 사이트에있는 첫 번째 구성 요소가 SiteMigrationDate인지 확인합니다.

두 번째는 더 많은 사이트를 생성 할 가능성이 더 빨리

• 모든 구성 요소의 목록을 생성합니다 마이그레이션. 목록의 각 구성 요소에 대해이 구성 요소 (SitesPendingOn)에 대한 종속성이 남아있는 사이트 수만 생성하십시오. 가장 많은 것을 가지고 그것을 MigrationOrder (오름차순 번호)로 지정하십시오. 해당 구성 요소가 목록에 남아 있지 않은 경우 남아있는 각 마이그레이션 순서 (마이그레이션 순서가 지정되지 않음)에 대한 사이트 사용 개수를 생성합니다 (ComponentSiteUsageCount). 가장 많은 것을 가지고 그것을 다음 MigrationOrder로 지정하십시오. 모든 구성 요소가 MigrationOrder를 할당 할 때까지 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로 변환하고 모든 합계를 수직 및 수평으로 제거하십시오.